CODEWITHSUNDEEP
haskell
A.B.
A.B.

Reputation: 16630

How do I split a list into sublists at certain points?

How do I manually split [1,2,4,5,6,7] into [[1],[2],[3],[4],[5],[6],[7]]? Manually means without using break.

Then, how do I split a list into sublists according to a predicate? Like so

f even [[1],[2],[3],[4],[5],[6],[7]] == [[1],[2,3],[4,5],[6,7]]

PS: this is not homework, and I've tried for hours to figure it out on my own.

Upvotes: 0

Views: 2461

Answers (3)

Will Ness
Will Ness

Reputation: 71070

First:

map (: [])

Second:

f p xs = 
  let rs = foldr (\[x] ~(a:r) -> if (p x) then ([]:(x:a):r) else ((x:a):r))
           [[]] xs
  in case rs of ([]:r) -> r ; _ -> rs

foldr's operation is easy enough to visualize: 

foldr g z [a,b,c, ...,x] = g a (g b (g c (.... (g x z) ....)))

So when writing the combining function, it is expecting two arguments, 1st of which is "current element" of a list, and 2nd is "result of processing the rest". Here,

g [x] ~(a:r) | p x    = ([]:(x:a):r)
             | otherwise = ((x:a):r)

So visualizing it working from the right, it just adds into the most recent sublist, and opens up a new sublist if it must. But since lists are actually accessed from the left, we keep it lazy with the lazy pattern,     ~(a:r). Now it works even on infinite lists:

Prelude> take 9 $ f odd $ map (:[]) [1..]
[[1,2],[3,4],[5,6],[7,8],[9,10],[11,12],[13,14],[15,16],[17,18]]

The pattern for the 1st argument reflects the peculiar structure of your expected input lists.

Upvotes: 2

firefrorefiddle
firefrorefiddle

Reputation: 3805

To answer your first question, this is rather an element-wise transformation than a split. The appropriate function to do this is

map :: (a -> b) -> [a] -> [b]

Now, you need a function (a -> b) where b is [a], as you want to transform an element into a singleton list containing the same type. Here it is:

mkList :: a -> [a]
mkList a = [a]

so

map mkList [1,2,3,4,5,6,7] == [[1],[2],...]

As for your second question: If you are not allowed (homework?) to use break, are you then allowed to use takeWhile and dropWhile which form both halves of the result of break.

Anyway, for a solution without them ("manually"), just use simple recursion with an accumulator:

f p [] = []
f p (x:xs) = go [x] xs
    where go acc [] = [acc]
          go acc (y:ys) | p y = acc : go [y] ys
                        | otherwise = go (acc++[y]) ys

This will traverse your entire list tail recursively, always remembering what the current sublist is, and when you reach an element where p applies, outputting the current sublist and starting a new one.

Note that go first receives [x] instead of [] to provide for the case where the first element already satisfies p x and we don't want an empty first sublist to be output.

Also, this operates on the original list ([1..7]) instead of [[1],[2]...]. But you can use it on the transformed one as well:

> map concat $ f (odd . head) [[1],[2],[3],[4],[5],[6],[7]]
[[1,2],[3,4],[5,6],[7]]

Upvotes: 3

bennofs
bennofs

Reputation: 11963

For the first, you can use a list comprehension:

>>> [[x] | x <- [1,2,3,4,5,6]]
[[1], [2], [3], [4], [5], [6]]

For the second problem, you can use the Data.List.Split module provided by the split package:

import Data.List.Split

f :: (a -> Bool) -> [[a]] -> [[a]]
f predicate = split (keepDelimsL $ whenElt predicate) . concat

This first concats the list, because the functions from split work on lists and not list of lists. The resulting single list is the split again using functions from the split package.

Upvotes: 2

Related Questions