9
\$\begingroup\$

I'm very new to Haskell. I did try it for a few days, a few years ago... but other than that, this is my second day. I'm equally unused to functional programming, by the way.

After much trial and error, I managed to write this function:

chunk :: Int -> [a] -> [[a]]
chunk n xs = chunk' n [] xs
    where
    chunk' _ results [] = results
    chunk' n results xs
        | length xs >= n = chunk' n (results ++ [take n xs]) $ tail xs
        | otherwise = chunk' n results []

This creates a list of all possible length n sub-lists, like so:

*Main> chunk 3 [1..7]
[[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7]]
*Main> chunk 5 [1..7]
[[1,2,3,4,5],[2,3,4,5,6],[3,4,5,6,7]]

How can this be improved (in readability, performance, brevity etc.)?

\$\endgroup\$
4
\$\begingroup\$

Using ++ to concatenate lists is a bad idea for performance, and it's a sign that you are not using recursion smartly.

Here's what I came up with:

chunk :: Int -> [a] -> [[a]]
chunk n xs =  
  if   length chunk' < n then []
  else (chunk' : chunk n (tail xs))
    where chunk' = take n xs
\$\endgroup\$
4
\$\begingroup\$

Some hints: Most importantly, your algorithm is O(n^2), and for 2 reasons:

  1. At every step you compute length xs, which is O(n).
  2. And at every step you also append to results from right, which is also O(n).

Try to make the function in such a way so that it doesn't need to traverse the whole list to produce a part of its output, so that it works also on infinite lists.


In particular, when recursively operating on lists, there are two approaches: left-fold-like and right-fold-like.

  • (Left) foldl processes the top-most operation (see the linked page with the diagram) using the last element of the list, so it needs to traverse the whole list before it actually starts to compute the result. Therefore, foldl should be used only in very specific cases, like:
    • The result operation is a value that doesn't have an internal structure, so in order to produce it, everything must be traversed anyway. Then using strict foldl' prevents creating huge thunks, like in sum' = foldl' (+) 0.
    • You actually want to reverse a list, as in foldl (flip (:)) []
  • (Right) foldr uses the first element of a list and its recursive call to produce a value; and if the operation is lazy in the recursive call, this makes the whole foldr lazy.

As a simpler example, consider two implementations of map :: (a -> b) -> [a] -> [b]:

  • Left fold:

    mapL f = map' []
      where
        map' results []     = results
        map' results (x:xs) = map' (results ++ [f x]) xs
    

    It is inefficient O(n^2) because of results ++ [x], and needs to traverse the whole list in order to compute the head of the resulting list.

  • Right fold, which is suitable for most cases, including yours.

    mapR f [] = []
    mapR f (x:xs) = f x : mapR f xs
    

    It's fully lazy and O(n).

    The key point to observe here is this: The recursive call to mapR is under a data constructor (:). (And the same can be observed in @200_success' example.) This means that after performing a bounded number of operations you produce one result element, and the rest is only computed when you examine the tail of the result. So such a function behaves well even for infinite lists.

    Search for keywords: guarded recursion and codata.


Or, you can also avoid doing recursive operations yourself and instead use existing list functions. Some hints on alternative solutions (which could be good exercises):

  • use zipWith n-times
  • use tails and then transpose the result
\$\endgroup\$
  • \$\begingroup\$ The mapL implementation doesn't take both a function and a list as arguments. I rewrote it based on what I assume you meant, and it's indeed much, much slower than mapR. I'll have to look at the other things you mentioned a bit more closely, also. \$\endgroup\$ – exscape Jun 13 '14 at 13:02
  • \$\begingroup\$ Be careful what you mean by n. I'd say that the original solution is O(L^2 n), where L is the length of the list and n is the chunk size. \$\endgroup\$ – 200_success Jun 13 '14 at 14:09
  • \$\begingroup\$ @200_success Yes, that might have been confusing. I always meant that n is the length of a list, not a chunk size. \$\endgroup\$ – Petr Pudlák Jun 13 '14 at 16:08
  • \$\begingroup\$ @exscape Actually mapL does take the function and the arguments, it's just eta-converted - mapL f xs = map' [] xs is almost identical to mapL f = map' []. \$\endgroup\$ – Petr Pudlák Jun 13 '14 at 16:10
  • \$\begingroup\$ Hmm, in that case I'm using it wrong; how do you use it? "mapL even [1..6]" gives [1, 2, 3, 4, 5, 6], while using mapR instead gives a list of booleans, as I would expect. \$\endgroup\$ – exscape Jun 13 '14 at 16:45
0
\$\begingroup\$

Here is another implementation that is short and even works on infinite lists:

chunk :: Int -> [a] -> [[a]]
chunk n = takeWhile ((== n) . length) . transpose . take n . iterate tail

The idea is to use tail n times, transpose, and take the results which have length n.

You can check that it works on infinite lists by, for instance

take 2 $ chunk 3 [1..]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.