laziness in `length'

[Daniel Fischer]

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