RFC: general sequences

[Benjamin Franksen]

On Monday 23 May 2005 17:35, Ross Paterson wrote:
> On Mon, May 23, 2005 at 01:48:14PM +0100, Adrian Hey wrote:
> > I'd like to know about the space behaviour of the folds and
> > whether or not you need more fold variants.
>
> Hmm, there are a number of choices just for foldr:
>
> 	foldr_l :: (a -> b -> b) -> b -> Seq a -> b
> 	foldr_l f z xs = case viewL xs of
> 		EmptyL -> z
> 		x :< xs' -> x `f` foldr_l f z xs'
>
> 	-- same result as foldr_l, but different performance
> 	foldr_r :: (a -> b -> b) -> b -> Seq a -> b
> 	foldr_r f z xs = case viewR xs of
> 		EmptyR -> z
> 		xs' :> x -> foldr_r f (x `f` z) xs'
>
> 	-- strict version
> 	foldr_r' :: (a -> b -> b) -> b -> Seq a -> b
> 	foldr_r' f z xs = case viewR xs of
> 		EmptyR -> z
> 		xs' :> x -> let z' = x `f` z in z' `seq` foldr_r' f z' xs'
>
> The current definition is equivalent to the first (but operates
> directly on the internal structure).  I can't think of a situation
> where I'd want the second.  The strict version would be useful, and
> probably a monadic version too (of which strictness could be a
> special case).

I wonder: Can a compiler optimize the above so that it is as efficient 
as the 'real' version? If not, why? If yes, everybody could easily 
create their own folds.

BTW, this module (or at least something similar) should definitely be in 
the standard libs.

Ben