这个名为“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作用？它以 tuple 的形式返回从列表中选择一个元素的所有可能方式，(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)这个列表。

-- 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]

Answer 2

在许多情况下，手动扩展表达式会有所帮助：

picks [1..4] = (1, [2..4]) : [(y, 1:ys) | (y, ys) <- picks [2..4]]

  -- continuing with picks [2..4]
  picks [2..4] = (2, [3..4]) : [(y, 2:ys) | (y, ys) <- picks [3..4]]

    -- continuing with picks [3..4]
    picks [3, 4] = (3, [4]) : [(y, 3:ys) | (y, ys) <- picks [4]]

      -- continuing with picks [4]
      picks [4] = (4, []) : [(y, 4:ys) | (y, ys) <- picks []]
                = (4, []) : [(y, 4:ys) | (y, ys) <- []]
                = (4, []) : []
                = [(4, [])]

    picks [3, 4] = (3, [4]) : [(y, 3:ys) | (y, ys) <- [(4, [])]]
                 = (3, [4]) : [(4, 3:[])]
                 = (3, [4]) : [(4, [3])]
                 = [(3, [4]), (4, [3])]

-- and so one

Answer 3

无需大脑破解，解释起来很简单（但 Eq a =>），执行时间大约慢 1.7 倍

mypicks :: Eq a => [a] -> [(a,[a])]
mypicks [] = []
mypicks lst = [ zsplit x lst | x <- lst]

zsplit :: Eq a => a -> [a] -> (a,[a])
zsplit z lst = esplit z lst []
    where
        esplit :: Eq a => a -> [a] -> [a] -> (a, [a])
        esplit e [] lr = (e, lr)
        esplit e (x:xs) lr
            | e == x    = (e, reverse lr ++ xs)
            | otherwise = esplit e xs (x:lr)

--- using
perms2 [] = [[]]
perms2 xs = [x:zs | (x,ys) <- picks xs, zs <- perms2 ys]

perms2' [] = [[]]
perms2' xs = [x:zs | (x,ys) <- mypicks xs, zs <- perms2' ys]
--- and
T.measureTime $ length $ perms2  [1..9]
T.measureTime $ length $ perms2' [1..9]
--- delivers:
e: 362880
Computation time: 0.075562000 sec.
e: 362880
Computation time: 0.125598000 sec.