Proposal: Strict scanl, scanl1 and mapAccumL

Takano Akio aljee at hyper.cx
Tue Nov 13 11:06:11 CET 2012


Hi,

On Mon, Nov 12, 2012 at 12:02:28PM +0100, Bas van Dijk wrote:
> On 12 November 2012 11:34, Bas van Dijk <v.dijk.bas at gmail.com> wrote:
> > I just realized that mapAccumL' is not needed since the caller has the
> > ability to force the accumlator. So please ignore that part of my
> > proposal. This leaves just scanl' and scanl1' as orignally proposed by
> > Niklas Hambüchen.
> 
> Oops scrap that. After thinking about it more and testing it I realize
> the caller really doesn't have control over the evaluation order in
> the function passed to mapAccumL. So please consider my original
> proposal again.

scanl' and scanl1' can be naturally defined using their non-strict
counterparts like:

scanl' :: (b -> a -> b) -> b -> [a] -> [b]                                                                                                                                          
scanl' f z xs = headStrict $ scanl f z xs                                                                                                                                           
                                                                                                                                                                                    
scanl1' :: (a -> a -> a) -> [a] -> [a]                                                                                                                                              
scanl1' f xs = headStrict $ scanl1 f xs                                                                                                                                             
                                                                                                                                                                                    
headStrict :: [a] -> [a]                                                                                                                                                            
headStrict = foldr (\x y -> seq x (x : y)) []

So the `headStrict' function could be exported from Data.List instead. A
nice thing about it is that it can also be used with other
list-generating functions like `iterate' to make it strict.

It's also possible to define mapAccumL' in terms of mapAccumL, but the
corresponding forcing function would not look as nice as `headStrict'
above, so I would think providing mapAccumL' is a good idea.

Regards,
Takano Akio




More information about the Libraries mailing list