[Haskell-beginners] Is there an "unscan" function?
AntC
anthony_clayden at clear.net.nz
Thu Jan 19 03:46:42 CET 2012
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
More information about the Beginners
mailing list