Magic.org

Magic

It’s folklore that if you’re summing a list of numbers, then you should always use strict foldl. Is that really true though? foldr is useful for lists when the function we use is lazy in its second argument. For (+) :: Int -> Int -> Int this is tyically not the case, but in some sense that’s because Int is “too strict”. An alternative representation of numbers is to represent them inductively. If we do this, sumation can be lazy, and foldr can do things that foldl simply can’t!

First, let’s define natural numbers inductively, and say how to add them:

data Nat = Zero | OnePlus Nat deriving Show

one :: Nat
one = OnePlus Zero

(+) :: Nat -> Nat -> Nat
Zero      + n = n
OnePlus m + n = OnePlus (m + n)

One useful Nat-producing function is the length of a list, so let’s write a way to calculate that. This is just text book foldr!

length :: [a] -> Nat
length = foldr (const (one +)) Zero

We can also compare natural numbers for their ordering:

(>) :: Nat -> Nat -> Bool
OnePlus _ > Zero      = True
OnePlus m > OnePlus n = m > n
Zero      > _         = False

So we can put all of this together, and see if there is at least one number bigger than 42:

length (filter (> 42) [1..]) > 10

Plug this all into GHCI and you should be greeted with the answer True. We compared the length of an infinite list and got an answer. That, my friends, is