Greaters function define

Question

I would like to define a greaters function, which selects from a list items that are larger than the one before it.

For instance:

greaters [1,3,2,4,3,4,5] == [3,4,4,5]
greaters [5,10,6,11,7,12] == [10,11,12]

The definition I came up with is this :

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

Things I tried so far:

greaters (x:xs) = group [ d | d <- xs, x < xs ]

Any tips?

Answer 1

We can derive a foldr-based solution by a series of re-writes starting from the hand-rolled recursive solution in the accepted answer:

greaters :: Ord a => [a] -> [a]
greaters [] = []
greaters (x:xs) = go x xs          -- let's re-write this clause
  where
    go _ [] = []
    go last (act:xs)
      | last < act  =  act : go act xs
      | otherwise   =        go act xs

greaters (x:xs) = go xs x          -- swap the arguments
  where
    go [] _ = []
    go (act:xs) last
      | last < act  =  act : go xs act 
      | otherwise   =        go xs act 

greaters (x:xs) = foldr g z xs x   -- go ==> foldr g z
  where
    foldr g z [] _ = []
    foldr g z (act:xs) last
      | last < act  =  act : foldr g z xs act 
      | otherwise   =        foldr g z xs act 

greaters (x:xs) = foldr g z xs x
  where                          -- simplify according to
    z _ = []                     --   foldr's definition
    g act (foldr g z xs) last 
      | last < act  =  act : foldr g z xs act 
      | otherwise   =        foldr g z xs act 

Thus, with one last re-write of foldr g z xs ==> r,

greaters (x:xs) = foldr g z xs x
  where
    z = const []
    g act r last
      | last < act  =  act : r act 
      | otherwise   =        r act 

The extra parameter serves as a state being passed forward as we go along the input list, the state being the previous element; thus avoiding the construction by zip of the shifted-pairs list serving the same purpose.

Answer 2

I would start from here:

greaters :: Ord a => [a] -> [a]
greaters [] = []
greaters (x:xs) = greatersImpl x xs
    where
        greatersImpl last [] = <fill this out>
        greatersImpl last (x:xs) = <fill this out>