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