Lazy list length

To get the length of a list like

length [1..10] == 10

You have to walk the whole list to check that it’s indeed of length 10.

Another way is to define a natural number in peano arithmetic style:

data Nat = Zero | Add1 Nat
  deriivng (Ord, Eq)

So

-- 0 = Zero
-- 1 = Add1 Zero
-- 2 = Add1 (Add1 Zero)
-- 3 = Add1 (Add1 (Add1 Zero))

We define a trivial instance of Num for it:

instance Num Nat where
  Zero + y = y
  Add1 x + y = x + (Add1 y)
  fromInteger 0 = Zero
  fromInteger n = Add1 (fromInteger (n - 1))

Now we can use genericLength on a list like this. Equal-sized lists:

> genericLength [1..3] == (genericLength [1..3] :: Nat)
True

With infinite lists:

> genericLength [1..3] < (genericLength [1..] :: Nat)
True
> genericLength [1..3] == (genericLength [1..] :: Nat)
False
> genericLength [1..3] > (genericLength [1..] :: Nat)
False

We didn’t have to walk the whole list to compare its length with a finite number. That’s pretty cool.