RFC: general sequences
benjamin.franksen at bessy.de
Mon May 23 13:24:50 EDT 2005
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.
More information about the Libraries