list - 在haskell中将列表转换为带有折叠的列表列表

Question

我有这个代码：

fromList :: Int -> [Int] -> [[Int]]
fromList y = takeWhile (not.null) . map (take y) . iterate (drop y) 

这样做的一个例子： -> fromList 4 [1..19]

[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16],[17,18,19]]

如何使用折叠制作此代码？

Answer 1

这是一个非常优雅的解决方案，使用foldr：

fromList :: Int -> [a] -> [[a]]
fromList n = foldr (\v a ->
    case a of
        (x:xs) -> if length x < n then (v:x):xs else [v]:a
        _ -> [[v]]
    ) []

本质上，累加器是最终值，对于列表中的每个值，它会检查是否还有空间将其放入现有块中，如果没有，则将其放入新块中。可悲的是，由于使用foldr，额外的元素被放在左侧而不是右侧。foldl这可以通过使用（或）稍慢（可能更难看）的方法来解决foldl'：

fromList :: Int -> [a] -> [[a]]
fromList _ [] = []
fromList n (x:xs) = reverse $ foldl (\a@(y:ys) v ->
    if length y < n
        then (y ++ [v]):ys
        else [v]:a
    ) [[x]] xs

Answer 2

这是一种方法。

foo :: Int -> [t] -> [[t]]
foo k xs | k > 0  =  foldr cons [] .
          zip xs . cycle $ (False <$ [2..k]) ++ [True]
  where
  cons (a,True)   ys  =  [a] : ys
  cons (a,False)  ys  =  (a:x) : zs
                         where
                         (x,zs) | null ys   = ([], [])
                                | otherwise = (head ys, tail ys)

-- > foo 3 [1..10]
-- => [[1,2,3],[4,5,6],[7,8,9],[10]]

-- > take 4 . foo 3 $ [1..]
-- => [[1,2,3],[4,5,6],[7,8,9],[10,11,12]]

-- > take 3 . map (take 2) . foo 3 $ [1..8] ++ undefined
-- => [[1,2],[4,5],[7,8]]

它按照您的描述创建输出，并且以一种足够懒惰的方式进行，因此它也适用于无限列表。

（编辑：根据Daniel Fischer的想法，让它变得更加懒惰，以便最后一个例子可以工作）