CODEWITHSUNDEEP
listhaskell
Michael
Michael

Reputation: 85

Segmenting a Haskell list

Given a sorted list in haskell, how can I get segmented lists where the consecutive numbers are placed in the same list. For example if I have a sorted list [1,2,3,4,7,8,10,12,13,15] the result will be [[1,2,3,4],[7,8],[10],[12,13],[15]]

Upvotes: 2

Views: 401

Answers (3)

Chris Kuklewicz
Chris Kuklewicz

Reputation: 8153

This is just a foldr:

q :: (Enum a, Eq a) => [a] -> [[a]]
q = foldr foo []
  where
    foo x (ys@(y:_) : zzs) | succ x == y = (x:ys) : zzs
    foo x t = [x] : t

*Main> q [1,2,3,4,7,8,10,12,13,15]

[[1,2,3,4],[7,8],[10],[12,13],[15]]

Update: It can also be turned into a foldl, here I use "difference lists" to make it go:

type N a = Maybe ( [[a]] -> [[a]], [a] -> [a], a )

p :: (Enum a, Eq a) => [a] -> [[a]]
p = close . foldl bar Nothing
  where
    close :: N a -> [[a]]
    close Nothing = []
    close (Just (f, g, _)) = (f  . (g []:)) []

    bar :: (Enum a, Eq a) => N a -> a -> N a
    bar Nothing x = Just (id, (x:), x)
    bar (Just (f, g, y)) x | succ y == x = Just (f, g . (x:), x)
                           | otherwise = Just ( f . (g []:), (x:), x)

Update 2 : 'f' is a variant that is safe on infinite lists:

f :: (Enum a, Eq a) => [a] -> [[a]]
f [] = []
f (x:xs) = go x xs
  where
    go x xs = let (run, rest) = getRun x xs
              in run : f rest
    getRun x t@(y:ys) | succ x == y = let (run, rest) = getRun y ys
                                      in (x:run, rest)
    getRun x t = (x:[], t)

or the shorter 'f' :

f :: (Enum a, Eq a) => [a] -> [[a]]
f [] = []
f (x:xs) = getRun x xs
  where
    getRun x t@(y:ys) | succ x == y = let (run : rest) = getRun y ys
                                      in (x:run) : rest
    getRun x t = (x:[]) : f t

t3 = [1,2,3,10,11,12] ++ [15..]

*Main> take 3 (map (take 5) (f t3))

[[1,2,3],[10,11,12],[15,16,17,18,19]]

Upvotes: 6

ErikR
ErikR

Reputation: 52057

An outline of a solution:

1- Pair up each element with the next one:

(1,2) (2,3) (3,4) (4,7) (7,8) (8,10) (10,12) (12,13) (13,15) ...

2- Check each pair for being consecutive:

(1,2) (2,3) (3,4) (4,7) (7,8) (8,10) (10,12) (12,13) (13,15) ...
True  True  True  False True  False  False   True    False   ...

3- Break up the list at the False values:

(1,2) (2,3) (3,4) (4,7) | (7,8) (8,10) | (10,12) | (12,13) (13,15) | ...
True  True  True  False | True  False  | False   | True    False   | ...

4- For each segment take the fst of the pairs:

1 2 3 4 | 7 8 | 10 | 12 13

Upvotes: 1

jamshidh
jamshidh

Reputation: 12070

This function can help

addFirstInRun::Int->[Int]->[(Int, Int)]
addFirstInRun _ [] = []
addFirstInRun lowVal (x:y:rest) | y - x > 1 = (lowVal, x):firstInRun y (y:rest)
addFirstInRun lowVal (x:rest) = (lowVal, x):firstInRun lowVal rest

It pairs each value in the list with another number, the "head" of the current bin.

> addFirstInRun 1 [1,2,3,5,6,7,10]

  [(1,1),(1,2),(1,3),(5,5),(5,6),(5,7),(10,10)]

(sorry, you need to put in the first one by hand.... you can write a convenience wrapper to fix this).

Using this, you can use groupBy

groupBy ((==) `on` fst)

And you can clean up the final answer using this

map (map snd)

Putting this all together

> map (map snd) $ groupBy ((==) `on` fst) $ addFirstInRun 1 [1,2,3,5,6,7,10]

  [[1,2,3],[5,6,7],[10]]

(You will need to import Data.Function and Data.List.)

Upvotes: 1

Related Questions