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

我已经编写了一个函数，该函数接受列表的每两个元素并将其放到子列表中，我想知道这段代码是否可以帮助我解决上述问题：

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 first的前两个参数，尤其是这一行：

  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 = 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`

仍然存在一个问题：列表以错误的顺序返回。为了解决这个问题，我们用差异列表替换列表，并交换追加的顺序。

最后，我们取消对CPS的功能，然后得到了上面的内容。