laziness in `length'

[Denys Rtveliashvili]

Hi Daniel,

Thank you very much for the explanation of this issue.

While I understand the parts about rewrite rules and the big thunk, it
is still not clear why it is the way it is.

Please could you explain which Nums are not strict? The ones I am aware
about are all strict.

Also, why doesn't it require building the full thunk for non-strict
Nums? Even if they are not strict, an addition requires both parts to be
evaluated. This means the thunk will have to be pre-built, doesn't it?

With kind regards,
Denys


> On Monday 14 June 2010 16:25:06, Serge D. Mechveliani wrote:
> > Dear people and GHC team,
> >
> > I have a naive question about the compiler and library of  ghc-6.12.3.
> > Consider the program
> >
> >   import List (genericLength)
> >   main = putStr $ shows (genericLength [1 .. n]) "\n"
> >          where
> >          n = -- 10^6, 10^7, 10^8 ...
> >
> > (1) When it is compiled under  -O,  it runs in a small constant space
> >     in  n  and in a time approximately proportional to  n.
> > (2) When it is compiled without -O,  it takes at the run-time the
> >     stack proportional to  n,  and it takes enormousely large time
> >     for  n >= 10^7.
> > (3) In the interpreter mode  ghci,   `genericLength [1 .. n]'
> >     takes as much resource as (2).
> >
> > Are the points (2) and (3) natural for an Haskell implementation?
> >
> > Independently on whether  lng  is inlined or not, its lazy evaluation
> > is, probably, like this:
> >  lng [1 .. n] =
> >  lng (1 : (list 2 n)) =  1 + (lng $ list 2 n) =
> >  1 + (lng (2: (list 3 n))) = 1 + 1 + (lng $ list 3 n) =
> >  2 + (lng (3: (list 4 n)))   -- because this "+" is of Integer
> >  = 2 + 1 + (lng $ list 4 n) =
> >  3 + (lng $ list 4 n)
> >  ...
> > And this takes a small constant space.
> 
> Unfortunately, it would be
> 
> lng [1 .. n]
> ~> 1 + (lng [2 .. n])
> ~> 1 + (1 + (lng [3 .. n]))
> ~> 1 + (1 + (1 + (lng [4 .. n])))
> ~>
> 
> and that builds a thunk of size O(n).
> 
> The thing is, genericLength is written so that for lazy number types, the 
> construction of the result can begin before the entire list has been 
> traversed. This means however, that for strict number types, like Int or 
> Integer, it is woefully inefficient.
> 
> In the code above, the result type of generic length (and the type of list 
> elements) is defaulted to Integer.
> When you compile with optimisations, a rewrite-rule fires:
> 
> -- | The 'genericLength' function is an overloaded version of 'length'.  In
> -- particular, instead of returning an 'Int', it returns any type which is
> -- an instance of 'Num'.  It is, however, less efficient than 'length'.
> genericLength           :: (Num i) => [b] -> i
> genericLength []        =  0
> genericLength (_:l)     =  1 + genericLength l
> 
> {-# RULES
>   "genericLengthInt"     genericLength = (strictGenericLength :: [a] -> 
> Int);
>   "genericLengthInteger" genericLength = (strictGenericLength :: [a] -> 
> Integer);
>  #-}
> 
> strictGenericLength     :: (Num i) => [b] -> i
> strictGenericLength l   =  gl l 0
>               where
>                 gl [] a     = a
>                 gl (_:xs) a = let a' = a + 1 in a' `seq` gl xs a'
> 
> which gives a reasonabley efficient constant space calculation.
> 
> Without optimisations and in ghci, you get the generic code, which is slow 
> and thakes O(n) space.
> 
> > Thank you in advance for your explanation,
> >
> > -----------------
> > Serge Mechveliani
> > mechvel at botik.ru
> 
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/glasgow-haskell-users/attachments/20100615/13787ed6/attachment.html