RFC: general sequences

[Ross Paterson]

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).