CODEWITHSUNDEEP
listhaskellrecursionlazy-evaluation
S4eed3sm
S4eed3sm

Reputation: 1478

Lazy mode of recursive function

I'm going to find a solution to this problem:

Splitting given list to sublist with given sub-list length and skip length, for example:

groupEvery 3 1 [1..6] = [[1,2,3], [2,3,4], [3,4,5], [4,5,6]]
groupEvery 3 2 "abcdefghij" = [ "abc", "cde", "efg", "ghi", "ij"]

The groupEvery n p l args details are:

Here is my solution:

groupEvery :: Int -> Int -> [a] -> [[a]] -> [[a]]
groupEvery n p xs acc
    | length xs <= n = acc ++ [xs]
    | otherwise = groupEvery n p dropped (acc++[segment])
        where
            dropped = drop p xs
            segment = take n xs

But this solution is not lazy, for example take 3 Lib2.groupEvery 3 1 [1..] [] never finished. My question is about

Upvotes: 2

Views: 282

Answers (2)

Will Ness
Will Ness

Reputation: 71119

Your use of "accumulator" here is vague.

The useful nomenclature is "state passing and building up", "output list creation", "tail recursion", and "guarded recursion" otherwise known as "tail recursion modulo cons" in the strict setting.

Yes, we can create the output list gradually through guarded recursion while simultaneously arranging for passing and accumulating / building up the state from one invocation to the next:

makeList elt next state = go state
  where
  go state = elt state : go (next state)
  --- which is just
  -- go = map elt . iterate next

("guarded" recursion, guarded by a lazy data constructor, here :).

Specifically, your example is

groupEvery n p  =  makeList (take n) (drop p)

up to a termination condition:

> takeWhile (not . null) $ groupEvery 3 2 [1..20]
[[1,2,3],[3,4,5],[5,6,7],[7,8,9],[9,10,11],[11,12,13],
 [13,14,15],[15,16,17],[17,18,19],[19,20]]

Upvotes: 1

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477891

The main problem is that you use an accumulator and only return the list when you walked over the entire input list. Furthermore length l will walk through the entire list. You don't need to calculate the length. This is also inefficient: if the list is long it will each time make a linear run.

You can pattern match on the list and for an empty list return an empty list and for a non-empty list yield the take n xs and recurse with drop p xs.

groupEvery :: Int -> Int -> [a] -> [[a]]
groupEvery _ _ [] = []
groupEvery n p xs = take n xs : groupEvery n p (drop p xs)

This thus produces:

ghci> take 3 (groupEvery 3 1 [1..])
[[1,2,3],[2,3,4],[3,4,5]]

You can further improve the function by combining take n and drop p such that you only walk over the min n p parts of the list once. I leave that as an exercise.

Upvotes: 6

Related Questions