Paramorphisms / Data.Scanable?
Ross Paterson
ross at soi.city.ac.uk
Sun Feb 4 04:11:13 EST 2007
On Sat, Feb 03, 2007 at 11:36:13PM -0500, Jim Apple wrote:
> I understand that it may not be possible to give simple types to
> anamorphisms or hylomorphisms, but I don't see there can't be a
> Data.Scannable with paramorphisms.
>
> class Scannable t where
> scanr :: (a -> b -> b) -> b -> t a -> t b
> scanl :: (a -> b -> a) -> a -> t b -> t a
> scanr1 :: (a -> a -> a) -> t a -> t a
> scanl1 :: (a -> a -> a) -> t a -> t a
scanr and scanl produce lists one longer than the input, i.e. results
of a different shape. Variants more suitable for generalization would
be
scanr' :: (a -> b -> b) -> b -> t a -> (b, t b)
scanl' :: (a -> b -> a) -> a -> t b -> (t a, a)
(The other element of the pair being the foldr or foldl respectively.)
Then the left-to-right functions could be implemented using Traversable
and a state monad. The right-to-left variants could use Traversable
with the mirror image applicative functor.
I don't think this is the same thing as paramorphisms (primitive
recursion), though.
More information about the Libraries
mailing list