[Haskell-beginners] Is there an "unscan" function?

[AntC]

Christian Maeder <Christian.Maeder <at> dfki.de> writes:

> 
> Am 13.01.2012 19:19, schrieb Stephen Tetley:
> > unscan :: (a ->  a ->  b) ->  [a] ->  [b]
> > unscan f (a:b:bs) = f a b : unscan f (b:bs)
> > unscan _ _        = []
> >
> 
> "putting the second element back" can be avoided by @-Patterns!
> 
>    unscan f (a : bs@(b : _)) = f a b : unscan bs
> 

And if Stephen or Christian had gone that little extra step to actually run 
their code they would find:
    unscan (flip (-)) [1,3,6,10]   ===> [2,3,4]

This is not what the OP asked for. (Because [1,3,6,10] is the result of scanl1 
(+) [1,2,3,4]. Where did the 1 go?)

The reason? The suffix-1 family of list combinators expect their list to 
contain at least one element, which they treat specially. So to unscanl1 we 
need to put the 'zeroeth' element back where scanl1 takes it from -- that is, 
on the front of the result.

To follow the style in the Prelude:
    unscanl1 :: (a -> a -> a) -> [a] -> [a]
    unscanl1 _ [] = []                         -- error-trap for empty lists
    unscanl1 f (x0: xs) = x0: unscanl f x0 xs  -- zeroeth element on the front

    unscanl :: (a -> a -> b) -> a -> [a] -> [b]
    unscanl f x0 (x:xs) = f x0 x : unscanl f x xs
    unscanl _ _ _ = []

Then:
    unscanl1 (flip (-)) [1,3,6,10]   ===> [1,2,3,4]

(I think that style of definition is the clearest to understand. You could 
possibly avoid repeating 'x' using @-patterns or a helper function (go) or a 
sub-case (per the Prelude), but I doubt it would make much difference to 
efficiency.)


AntC