[Haskell-beginners] Graham Scan exercise from Chapter 3 RWH -Spoilers. Don't read if you want to do this exercise.

[Stephen Tetley]

On 3 September 2010 11:57, Jürgen Doser <jurgen.doser at gmail.com> wrote:

> It is tempting to use some kind of map or foldr for this. Unfortunately,
> there isn't a really nice way. Such a "sliding window" map is
> occasionally useful, but there is no pre-defined function for it in the
> libraries.

Though not in Data.List, paramorphism is the standard 'sliding window' fold.


-- paramorphism (generalizes catamorphism i.e. foldr)
--
para :: (a -> ([a], b) -> b) -> b -> [a] -> b
para phi b = step
  where step []     = b
        step (x:xs) = phi x (xs, step xs)


With a paramorphism the 'lookahead' is left-to-right, but the list
itself is processed from the right (as per a right-fold). This can
sometimes make it a little tricky to use.