list - 这个名为 "picks"的函数背后的逻辑是什么？

Question

picks :: [a] -> [(a, [a])]
picks [] = []
picks (x:xs) = (x,xs) : [(y,x:ys)| (y,ys) <- picks xs]

picks [1..4] = [(1,[2,3,4]),(2,[1,3,4]),(3,[1,2,4]),(4,[1,2,3])]这个 Haskell 函数就像一个魅力，但为什么呢？列表中的前两个元组很明显，但其余的如何建立，只是让我的大脑崩溃。

Answer 1

picks 是什么意思做？它以元组 (choice, rest) 的形式返回从列表中选择一个元素的所有可能方式, 其中 choice是您选择的项目和rest是你没有选择的元素。请注意 [choice] ++ rest总是包含与原始列表相同的元素，尽管不一定以相同的顺序。
那么picks工作？当参数为空时，很简单:没有办法选择一个元素，所以我们返回空列表。

picks [] = []

当参数不为空时，我们可以做两件事之一。 x是元组的第一个元素，或者它是第二个元素的一部分。最简单的方法是选择第一个元素；我们用 (x:xs) 解压列表并生产 (x, xs) .

picks (x:xs) = (x, xs) : ?

我们可以做的另一件事是不选择 x ，而是从 xs 中选择一个元素.如何从 xs 中选择一个元素?我们使用 picks !这一次， picks返回 x 的元组列表既不是第一个元素，也不是第二个元素的成员。我们只是结合 (x, xs)有了这份 list 。

-- x != y, x `elem` ys == False
picks (x:xs) = (x, xs) : [ (y, ?) | (y, ys) <- picks xs]

但是 x确实需要成为第二个元素的成员，因为它不是第一个元素。所以我们必须把它放回去。最容易放的地方是 ys的开头在每种情况下:

picks (x:xs) = (x, xs) : [ (y, x:ys) | (y, ys) <- picks xs]