Почему для функции shuffle требуется параметр Int?

Question

In System.Random.Shuffle,

shuffle' :: RandomGen gen => [a] -> Int -> gen -> [a]

Страница взлома упоминает этот аргумент Int как

..., его длина ,...

Однако, похоже, что такой простой функции-обёртки, как

shuffle'' x = shuffle' x (length x)

, должно быть достаточно.

Answer 1

shuffle работает путем построения древовидной формы своего входного списка, , включая размер дерева .Функция buildTree выполняет эту задачу, используя Data.Function.fix способом, который я не совсем обернул вокруг.Каким-то образом (я думаю, что из-за рекурсии inner, а не магии fix) он создает сбалансированное дерево, которое затем имеет логарифмический поиск.Затем он потребляет это дерево, восстанавливая его для каждого извлеченного предмета.Преимущество структуры данных состоит в том, что она содержит только оставшиеся элементы в неизменяемом виде;Ленивые обновления работают на это.Но размер дерева - это обязательные данные во время индексации, поэтому нет необходимости передавать его отдельно для генерации индексов, используемых для построения перестановки.System.Random.Shuffle.shuffle действительно не имеет случайного элемента - это всего лишь функция перестановки.shuffle' существует, чтобы передать ему случайную последовательность, используя его внутренний помощник rseq.Поэтому причина, по которой shuffle' принимает аргумент длины, заключается в том, что они вообще не хотели, чтобы он касался аргумента списка;это только передано в shuffle.

Во-первых, задача не очень подходит для односвязных списков.Я, вероятно, рассмотрю возможность использования VectorShuffling .И я озадачен тем, почему rseq не входит в число экспортируемых функций, поскольку он использует генератор случайных чисел для построения перестановки ... что, в свою очередь, могло бы быть лучше обработано с использованием Data.Permute..Вероятно, причины связаны с историей, например, Data.Permute, который пишется позже, и System.Random.Shuffle, основанный на статье об неизменяемых очередях произвольного доступа.

Data.Random.Extras , кажется, имеет более прямую функцию перемешивания на основе Seq.

Answer 2

Это может быть случай, когда длина заданного списка уже известна, и ее не нужно вычислять заново.Таким образом, это может рассматриваться как оптимизация.

Кроме того, в общем случае результирующий список не обязательно должен иметь такой же размер, как и исходный.Таким образом, этот аргумент может быть использован для установки этой длины.

Это верно для первоначальной идеи Олега (источник - http://okmij.org/ftp/Haskell/perfect-shuffle.txt):

-- examples

t1 = shuffle1 ['a','b','c','d','e'] [0,0,0,0]
-- "abcde"
-- Note, that rseq of all zeros leaves the sequence unperturbed.

t2 = shuffle1 ['a','b','c','d','e'] [4,3,2,1]
-- "edcba"
-- The rseq of (n-i | i<-[1..n-1]) reverses the original sequence of elements

Однако, это не то же самое дляРеализация пакета 'random-shuffle':

> shuffle [0..10] [0,0,0,0]
[0,1,2,3random-shuffle.hs: [shuffle] called with lists of different lengths

Я думаю, что стоит проконсультироваться с сопровождающими пакетов, чтобы понять контракт этой функции.