[Haskell-cafe] Lists concatenation being O(n)

[Yves Parès]

Wow, I don't get core haskell, but I get you point.
It's indeed odd foldl' doesn't use foldr (and sum doesn't use foldl' instead
of foldl as (+) is strict (*)) if foldr permits loop fusion.

(*) Anyway, is there a place where foldl is preferable over foldl' ? Never
happened to me, I always use right-folding if I want lazy evaluation, to
benefit from guarded recursion.

2011/10/14 Bas van Dijk <v.dijk.bas at gmail.com>

> On 13 October 2011 20:53, Albert Y. C. Lai <trebla at vex.net> wrote:
> > The number of new cons cells created in due course is Θ(length xs).
>
> I was actually surprised by this because I expected: length(xs++ys) to
> fuse into one efficient loop which doesn't create cons cells at all.
>
> Unfortunately, I was mistaken since length is defined recursively.
>
> length :: [a] -> Int
> length l =  len l 0#
>  where
>    len :: [a] -> Int# -> Int
>    len []     a# = I# a#
>    len (_:xs) a# = len xs (a# +# 1#)
>
> However, if we would define it as:
>
> length = foldl' (l _ -> l+1) 0
>
> And implemented foldl' using foldr as described here:
>
> http://www.haskell.org/pipermail/libraries/2011-October/016895.html
>
> then fuse = length(xs++ys) where for example xs = replicate 1000000 1
> and ys = replicate 5000 (1::Int) would compile to the following
> totally fused core:
>
> fuse :: Int
> fuse = case $wxs 1000000 0 of ww_srS {
>         __DEFAULT -> I# ww_srS
>       }
>
> $wxs :: Int# -> Int# -> Int#
> $wxs = \ (w_srL :: Int#) (ww_srO :: Int#) ->
>    case <=# w_srL 1 of _ {
>      False -> $wxs (-# w_srL 1) (+# ww_srO 1);
>      True  -> $wxs1_rs8 5000 (+# ww_srO 1)
>    }
>
> $wxs1_rs8 :: Int# -> Int# -> Int#
> $wxs1_rs8 =
>  \ (w_srA :: Int#) (ww_srD :: Int#) ->
>    case <=# w_srA 1 of _ {
>      False -> $wxs1_rs8 (-# w_srA 1) (+# ww_srD 1);
>      True  -> +# ww_srD 1
>    }
>
> Bas
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20111014/2d578817/attachment.htm>