laziness in `length'
Daniel Fischer
daniel.is.fischer at web.de
Tue Jun 15 11:48:35 EDT 2010
On Tuesday 15 June 2010 16:52:04, Denys Rtveliashvili wrote:
> 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.
There are several implementations of lazy (to different degrees) Peano
numbers on hackage.
The point is that it's possible to have lazy Num types, and the decision
was apparently to write genericLength so that lazy Num types may profit
from it.
Arguably, one should have lazyGenericLength for lazy number types and
strictGenericLength for strict number types (Integer, Int64, Word, Word64,
...).
On the other hand, fromIntegral . length works fine in practice (calling
length on a list exceeding the Int range would be doubtful on 32-bit
systems and plain madness on 64-bit systems).
>
> 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.
Not necessarily for lazy numbers.
> This means the thunk will have to be pre-built, doesn't it?
For illustration, the very simple-minded lazy Peano numbers:
data Peano
= Zero
| Succ Peano
deriving (Show, Eq)
instance Ord Peano where
compare Zero Zero = EQ
compare Zero _ = LT
compare _ Zero = GT
compare (Succ m) (Succ n) = compare m n
min Zero _ = Zero
min _ Zero = Zero
min (Succ m) (Succ n) = Succ (min m n)
max Zero n = n
max m Zero = m
max (Succ m) (Succ n) = Succ (max m n)
instance Num Peano where
Zero + n = n
(Succ m) + n = Succ (m + n)
-- omitted other methods due to laziness (mine, not Haskell's)
fromInteger n
| n < 0 = error "Peano.fromInteger: negative argument"
| n == 0 = Zero
| otherwise = Succ (fromInteger (n-1))
one, two, three, four :: Peano
one = Succ Zero
two = Succ one
three = Succ two
four = Succ three
min two (genericLength [1 .. ])
~> min (Succ one) (genericLength [1 .. ])
~> min (Succ one) (1 + (genericLength [2 .. ]))
~> min (Succ one) ((Succ Zero) + (genericLength [2 .. ]))
~> min (Succ one) (Succ (Zero + (genericLength [2 .. ])))
~> Succ (min one (Zero + (genericLength [2 .. ])))
~> Succ (min (Succ Zero) (Zero + (genericLength [2 .. ])))
~> Succ (min (Succ Zero) (genericLength [2 .. ]))
~> Succ (min (Succ Zero) (1 + (genericLength [3 .. ])))
~> Succ (min (Succ Zero) ((Succ Zero) + (genericLength [3 ..])))
~> Succ (min (Succ Zero) (Succ (Zero + (genericLength [3 .. ]))))
~> Succ (Succ (min Zero (Zero + (genericLength [3 .. ]))))
~> Succ (Succ Zero)
>
> With kind regards,
> Denys
More information about the Glasgow-haskell-users
mailing list