在Haskell中,concat懒惰地建立一个列表,但我自己的版本有一个扭曲,但没有

Question

我正在尝试制作一个相对简单的功能,它几乎是连续的,但有一点点扭曲.它应该是二进制或每个列表的最后和第一个元素,并在过程中组合它们.我正在努力学习编写可以利用Data.List.Stream中的Stream Fusion功能的代码

我检查了base中的concat做了什么需要并且懒惰地构建列表,但是,我创建的这个版本没有.在基数中,concat指定如下:

concat :: [[a]] -> [a]
concat = foldr (++) []

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

这是我的代码:

bconcat :: [[Word8]] -> [Word8]
bconcat = foldr1 bappend

bappend :: [Word8] -> [Word8] -> [Word8]
bappend as bs = init as ++ (last as .|. head bs) : tail bs

我的问题是,如何编写这个列表是懒惰的？我甚至尝试通过模仿基础中的(++)定义来编写bappend,但它没有什么区别.

目前,我使用以下代码,它按照我想要的方式工作,但性能落后于concat.此外,它使用我想避免的显式递归.

bconcat :: [[Word8]] -> [Word8]
bconcat (a:b:xs) = init a ++ bconcat ((bappend (last a) b):xs)
bconcat (a:[]) = a
bconcat [] = []

bappend :: Word8 -> [Word8] -> [Word8]
bappend !a bs = (a .|. head bs) : tail bs

所以,我的问题是,我如何编写这段代码,以便它懒惰地构建列表而没有明确的递归？

感谢您的时间.

编辑:

目前,我的主要兴趣是使用标准组合器制作干净,简洁和可靠的代码.我仍然是一个具有功能性思维的初学者,并且希望看到一种合理有效的方式将它们用于此处.

Answer 1

你的定义对我来说看起来很严格。例如，尝试评估

length $ bconcat [[1,2,3],[4,undefined,6]]

但你可能会为 .| 建立 thunks。表达。也许你想强迫这样做。

如果东西不能自动很好地融合，你总是可以自己融合：

 bconcat [] = error "bconcat: empty outer list"
 bconcat (xs:xss) = loop xss xs
   where loop [] ys = ys
         loop ((x:xs):xss) [y] = let z = x .|. y in seq z $ z : loop xss xs
         loop ([]:_) _ = error "bconcat: empty inner list"
         loop xss (y:ys) = y : loop xss ys