Lazy mode of recursive function

user_17771658 0
Viewed 133

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:

  • n is length of sub-list: Int
  • f is length of skip: Int
  • xs is input list: [a]

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

  • Better solutions for the groupEvery function ?
  • How we can write recursive lazy function that accumulate some data ? In other words is there any structure for this kind of recursive functions that accumulate results and are lazy ?
recursion lazy-evaluation list haskell
2 Answers

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.

user_675790

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