交换Haskell中的列表列表

Question

我想知道如何在Haskell中编写一个将列表列表交织到单个列表中的函数,例如,如果我有一个函数调用

interleavelists :: [[a]] -> [a]

它应该能够交错元素.

示例:[[1,2,3] [4,5,6] [7,8]] --> [1,4,7,2,5,8,3,6].

列表可以是有限的也可以是无限的...我可以使用foldr吗？

Answer 1

写它的最快方法是使用transposefrom Data.List.

import Data.List

interleavelists :: [[a]] -> [a]
interleavelists = concat . transpose

transpose选择其参数的每个非空列表的第一个元素,将它们放入一个列表中,然后是参数元素transpose的tails 列表.concat根据需要设置列表transpose的结果会对列表进行交错.如果某些元素列表是无限的,它可以工作,但如果列表列表本身具有无限多个元素,它当然永远不会超过heads 列表.但无论如何处理这种情况是有问题的.

使用foldr交错列表并非易事.假设你有

interleavelists xss = foldr something zero xss

interleavelists []应该产生[],所以这就是zero价值.和

interleavelists [xs] = xs

看起来很自然,所以

something xs [] = xs

但如果第二个论点不是[]呢？然后,您希望将something不同距离的第一个参数的元素插入到第二个参数中.但在哪个距离？如果所有列表具有相同的长度,则每个列表的距离都是常量,那么您可以将距离作为另一个参数传递,

interleavelists = snd . foldr insertAtDistance (0, [])
  where
    insertAtDistance xs (d, ys) = (d+1, helper d xs ys)
    helper _ [] ws = ws
    helper k (b:bs) cs = b : us ++ helper k bs vs
      where
        (us,vs) = splitAt k cs

这不是很漂亮,如果列表不是全部相同的长度将产生可能不是所需的输出.但是如果列表都具有相同的长度,那么它就完成了工作.

Answer 2

简单的递归版本：

inter :: [[a]] -> [a]
inter [] = []
inter xs = inter2 (filter (\x -> not (null x)) xs)
   where inter2 xs = map head xs ++ inter (map tail xs)

现在，关于文件夹...

Answer 3

早在 SICP（以及后来的合理方案）的欢乐时光中，交错列表的“标准”（或者可能是著名的）方式是

infixr 5 ++/

[]     ++/ ys = ys
(x:xs) ++/ ys = x:(ys ++/ xs)

它可以与foldr、

*Main> foldr (++/) [] [[1,2,3],[4,5,6],[7,8]]
[1,4,2,7,3,5,8,6]

这显然不会按照您想要的顺序产生结果，但是当列表的输入列表是无限时，它会正常工作。我认为没有办法同时满足这两个要求，因为我们无法知道输入列表是否是无限的。

如果修改为始终在 ,而不是 的距离处插入，上面的结果是Daniel 答案insertAtDistance中的函数将产生的结果：1d+1

insertAtDistance xs (d, ys) = (1, helper d xs ys)

当定义d+1它时，它会产生“平坦”交错，而foldr (++/) []产生倾斜交错：

*Main> take 20 $ foldr (++/) [] [cycle[i] | i<-[1..]]
[1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3]