inits

[Donald Bruce Stewart]

ross:
> On Mon, Apr 10, 2006 at 06:00:59PM +0100, Chris Kuklewicz wrote:
> > Ross Paterson wrote:
> > > On Mon, Apr 10, 2006 at 03:54:09PM +0100, Chris Kuklewicz wrote:
> > >> If the goal is speed, then this definition is running over 10% faster with ghc
> > >> -O2 on my powerbook for (sum $ map length $ inits [1..10000])
> > >>
> > >> inits' = helper id
> > >>     where helper f [] = (f []):[]
> > >>           helper f (x:xs) = (f []):helper (f.(x:)) xs
> > > 
> > > I rather like
> > > 
> > > 	inits = map ($ []) . scanl (.) id . map (:)
> > 
> > That takes 3 times longer than the helper function definition.
> 
> Sorry, I meant it appeals to my perverse sense of aesthetics.  It is of
> course the de-fused version of helper.
> 
> > > 	inits = map reverse . scanl (flip (:)) []
> > 
> > I would never try "reverse" when looking for performance, but that runs at the
> > same speed as the helper and allocates the same amount of space.
> 
> It's not really surprising: the nested composition built by helper is
> essentially a list, which is traversed by ($ []).  If scanl were defined
> using build it might run a tiny bit faster.

Ah! Looks like a bit like DList code, from a lib by Manuel Chakravarty:

    -- | a difference list is a function that given a list returns the original
    -- contents of the difference list prepended at the given list
    type DList a = [a] -> [a]

    -- | open a list for use as a difference list
    openDL :: [a] -> DList a
    openDL  = (++)

    -- | create a difference list containing no elements
    zeroDL :: DList a
    zeroDL  = id

    -- | create difference list with given single element
    unitDL :: a -> DList a
    unitDL  = (:)

    -- | append a single element at a difference list
    snocDL      :: DList a -> a -> DList a
    snocDL dl x  = \l -> dl (x:l)

    -- | appending difference lists
    joinDL :: DList a -> DList a -> DList a
    joinDL  = (.)

    -- | closing a difference list into a normal list 
    closeDL :: DList a -> [a]
    closeDL  = ($[])

Which I've used on occasion to write faster code when doing lots of appends.

-- Don