CODEWITHSUNDEEP
haskell
user3169543
user3169543

Reputation: 1589

Haskell: Higher Order function to use to group an increasing decreasing list

Given a list [1,2,31,23,22,1,43] Would like to use a higher order function to group elements [[1,2,31], [23,22,1], [43]] . increasing / decreasing list, where the elements initially the elements are in increasing order and then in decreasing order. 

groupIncDec :: Ord a => [a] -> [[a]]

Each element in the output list [[a]] should be either all increasing or all decreasing, like in the example above, first element [1,2,31] is all increasing, second [23,22,1] all decreasing and because the there is a single element left and the previous state was all decreasing, [43] can be classified as all increasing.

Could not figure out if/how to use groupBy . Any hints would be appreciated.

Thanks.

[Edit: added some more description, which will hopefully clarify the question further.]

Upvotes: 1

Views: 532

Answers (2)

K. A. Buhr
K. A. Buhr

Reputation: 50864

Here's another approach. For the moment, let's assume that the list has no adjacent equal elements, like your example. If the list lst is compared with its own tail, element-by-element:

> let lst = [1,2,31,23,22,1,43]
> let dir = zipWith compare lst (tail lst)
> dir
[LT,LT,GT,GT,GT,LT]

then dir represents whether adjacent elements are increasing or decreasing. If we were to repeat the head of this list:

> let dir' = head dir : dir
> dir'
[LT,LT,LT,GT,GT,GT,LT]

then dir' corresponds to how the list [1,2,31,23,22,1,43] should be grouped. By zipping dir' with lst and grouping by the dir' elements, we get:

> import Data.Function  -- for `on`
> let groups = groupBy ((==) `on` fst) (zip dir' lst)
> groups 
[[(LT,1),(LT,2),(LT,31)],[(GT,23),(GT,22),(GT,1)],[(LT,43)]]

which we can filter to:

> map (map snd) groups
[[1,2,31],[23,22,1],[43]]

So, putting this all together, we get a higher-order solution:

groupIncDec' :: Ord a => [a] -> [[a]]
groupIncDec' lst =
  let dir = zipWith compare lst (tail lst)
  in  map (map snd)
      $ groupBy ((==) `on` fst)
      $ zip (head dir : dir) lst

This doesn't work properly on lists with adjacent duplicate elements, but we can take such a list:

lst' = [1,2,31,31,23,22,22,1,43]

and group it:

group lst' = [[1],[2],[31,31],[23],[22,22],[1],[43]]

and then effectively apply the above algorithm before "ungrouping" it again to get the final result. That looks like this:

groupIncDec :: Ord a => [a] -> [[a]]
groupIncDec xs =
  let ys = group xs
      dir = zipWith (comparing head) ys (tail ys)
  in  map (concatMap snd)
      $ groupBy ((==) `on` fst)
      $ zip (head dir : dir) ys

which works like so:

> groupIncDec [1,2,31,23,22,1,43]
[[1,2,31],[23,22,1],[43]]
> groupIncDec [1,2,31,31,23,22,22,1,43]
[[1,2,31,31],[23,22,22,1],[43]]

Upvotes: 4

delta
delta

Reputation: 3818

groupBy is meant to group by equality, not a general binary relation. For example:

Prelude Data.List> groupBy (<) [1,3,2]
[[1,3,2]]

it is a span of first element 1 (as 1<3, 1<2).

I came up with a solution of foldl, but this is not a very clean solution.

groupIncDec :: Ord a => [a] -> [[a]]
groupIncDec = map reverse . reverse . foldl f []
  where f []                 x = [[x]]
        f ([y]:ys)           x = [x,y]:ys
        f (ys@(y1:y2:_):yss) x = if x < y1 && y1 < y2 || x > y1 && y1 > y2
                                 then (x:ys):yss
                                 else [x]:ys:yss

f is of type [[a]] -> a -> [[a]], i.e. the accumulation part.

Because Haskell List is good at dealing the head element (with help of :), so the results are stored backward. Thus map reverse . reverse is needed.

  1. http://hackage.haskell.org/package/base-4.10.0.0/docs/Data-List.html#v:groupBy
  2. http://hackage.haskell.org/package/base-4.10.0.0/docs/Data-List.html#v:foldl

Upvotes: 2

Related Questions