为什么 shuffle' 函数需要一个 Int 参数？

Question

在System.Random.Shuffle,

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

hackage page 提到这个 Int 论点是

..., its length,...

但是，似乎像

这样的简单包装函数

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

应该够了。

Answer 1

可能是给定列表的长度已知，不需要再次计算的情况。因此，它可能被认为是一种优化。

此外，一般来说，生成的列表不需要与原始列表具有相同的大小。因此，此参数可用于设置此长度。

Oleg 的最初想法也是如此（来源 - 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

我认为值得跟进包维护者以了解此功能的契约。

Answer 2

shuffle 通过构建其输入列表的树形式进行操作，包括树大小。 buildTree 函数使用 Data.Function.fix 以一种我还没有完全理解的方式执行此任务。不知何故（我认为由于 inner 的递归，而不是 fix 魔术），它产生了一个平衡树，然后进行对数查找。然后它消耗这棵树，为每个提取的项目重建它。数据结构的优点是它只以不可变的形式保存剩余的项目；延迟更新适用于它。但是树的大小在索引期间是必需的数据，因此无需单独传递它来生成用于构建排列的索引。 System.Random.Shuffle.shuffle 确实没有随机元素——它只是一个排列函数。 shuffle' 的存在是为了给它提供一个随机序列，使用它的内部助手 rseq。所以 shuffle' 接受长度参数的原因似乎是因为他们根本不希望它触及列表参数；它只传递到 shuffle。

首先，该任务似乎不太适合单向链表。我可能会考虑使用 VectorShuffling instead. And I'm baffled as to why rseq isn't among the exported functions, being the one that uses a random number generator to build a permutation... which in turn might have been better handled using Data.Permute。可能原因与历史有关，例如 Data.Permute 是后来编写的，而 System.Random.Shuffle 是基于关于不可变随机访问队列的论文。

Data.Random.Extras 似乎有一个更直接的基于 Seq 的洗牌功能。

为什么 shuffle' 函数需要一个 Int 参数？

Why does the shuffle' function require an Int parameter?

random

haskell

shuffle

list