list - 为什么 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

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 的随机播放功能。