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

Stephen Tetley stephen.tetley at gmail.com
Fri Sep 3 08:29:50 EDT 2010

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.

More information about the Beginners mailing list