Paramorphisms / Data.Scanable?

[Ross Paterson]

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.