Transform a list into a list of lists with fold in haskell

Question

I have this code:

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

An example of what this does: -> fromList 4 [1..19]

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

How can I make this code using a fold?

This is really a job for *`unfoldr`*; why do you want to use `foldr`? — chepner, Nov 05 '20 at 13:30
While (I think) either can do the job of the other, folds are for things with the general form `[a] -> a`, and unfolds for `a -> [a]`. (`a` itself can be a list type, accounting for the overlap between the two functions.) — chepner, Nov 05 '20 at 13:56
Consider `fromList n = unfoldr (\x -> if null x then Nothing else Just (take n x, drop n x))`. — chepner, Nov 05 '20 at 14:01

score 3 · Accepted Answer · edited Nov 05 '20 at 16:29

3

Here's a pretty elegant solution using 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]]
    ) []

Essentially, the accumulator is the end value, and for each value in the list it checks if there's still space to put it in an existing chunk, and if there isn't then it puts it in a new chunk. Sadly, due to using foldr, extra elements are put on the left side instead of the right side. This can be fixed by using a slightly slower (and maybe slightly uglier) approach with foldl (or 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

edited Nov 05 '20 at 16:29

Joseph Sible-Reinstate Monica

45,431
5
48
98

answered Nov 05 '20 at 13:11

Aplet123

33,825
1
29
55

I gave 2 possible solutions, the first of which putting the extra chunk on the left, resulting in `[[1], [2, 3, 4], [5, 6, 7], [8, 9, 10]]`, and the second resulting in `[[1, 2, 3], [4, 5, 6], [7, 8, 9], [10]]`, as I stated in my answer. – Aplet123 Nov 05 '20 at 14:54
`a@` means that `a` becomes an alias for `y:ys`. You can just use `y:ys` instead of `a` and get rid of the `a@` if you want. – Aplet123 Nov 05 '20 at 17:39

Will Ness · Answer 2 · 2020-11-09T16:03:43.810

Here's one way.

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

It creates the output as you have described it, and does so in a lazy enough way so that it works with infinite lists as well.

(edit: made it even lazier so that the last example would work, based off the idea by Daniel Fischer)

Transform a list into a list of lists with fold in haskell

2 Answers2

Linked