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.