list - Haskell:列表操作

Question

我想编写一个接受输入列表并按以下方式操作它的函数:

第 1 步:将列表的第一个元素和列表的最后一个元素放在一起放在一个子列表中。

第 2 步:将列表的第二个元素和列表的倒数第二个元素放在一起放在下一个子列表中。

第 3 步:取列表的第三个元素和列表的倒数第三个元素列出并将其放在下一个子列表中。

按照相同的方案继续这个(对于 n 个元素的列表)...

如果输入列表的元素个数为奇数，则输入列表的 n/2 个元素将添加为输出列表的最后一个子列表。

例子:

[1,2,3,4,5,6,7]

-- should be transformed to

[[1,7],[2,6],[3,5],[4]]

我已经编写了一个函数，它获取列表中的每 2 个元素并将其放在子列表中，我想知道这段代码是否可以帮助我解决上述问题:

g2 :: [a] -> [[a]]
g2 [] = []
g2 (x1:x2:xs) = [x1,x2]: g2 xs
g2 xs = [xs]

Answer 1

这是一次完成的方法:

pairs :: [a] -> [[a]]
pairs xs = fst (go xs xs) where
  go (x:xs) (_:_:ys) = f x (go xs ys)
  go (x:xs) [_]      = ([[x]],xs)
  go xs     []       = ([],xs)

  f x (xs,y:ys) = ([x,y]:xs,ys)

它是如何工作的？让我们先看看 go 的前两个参数，特别是这一行:

  go (x:xs) (_:_:ys) = f x (go xs ys)

这两个参数都来自同一个列表 (xs)，但是我们从一个中减去 2 个项目，而从另一个中只减去一个。为什么？所以我们知道什么时候到达中点。看看这个函数进行比较:

halfway xs = go xs xs
  where
    go (_:xs) (_:_:ys) = go xs ys
    go xs _ = xs

>>> halfway [1..6]
[4,5,6]

现在，一旦我们到达中间点，我们就需要将它与另一个列表“压缩”在一起。但是需要反过来!我们如何做到这一点？一次反转任何函数的一种简便方法是首先将其写为折叠。这是写成折叠的 zip:

zip = foldr (\x k (y:ys) -> (x,y) : k ys) (const [])

要“反转”它，您只需将它应用为 foldl 而不是 foldr(您还必须翻转闭包)。

对于我们的使用，我们基本上是边做边建立基础(以 k 的形式)。所以我们的函数不是这样的:

pairs :: [a] -> [[a]]
pairs xs = go xs xs (const []) where
  go (y:ys) (_:_:zs) k = go ys zs (f y k)
  go (y:ys) [_]      k = [y] : k ys
  go ys     []       k = k ys

  f x k (y:ys) = [x,y] : k ys -- same `f` as from `zip`

还有一个问题:列表以错误的顺序返回。要解决此问题，我们将列表替换为 difference list , 并交换追加的顺序。

最后，我们对函数进行反CPS，得到上面的结果。