[Previous entry: "Rosetta Code"] [Next entry: "Four-year-old Drummer"]

12/27/2009: "Learning Haskell"

During Christmas break my project is to learn me Haskell. I've procured the book Real World Haskell and am about halfway through it. RWH is a pretty good book but it could do with another editing pass. For example, the '$' operator is used without ever having been explained.

And I found an interesting paper The Genuine Sieve of Eratosthenes which shows that a common Functional Programming example isn't really true to Eratosthenes' original algorithm.

One form of the standard FP Sieve goes like this (in Haskell):

primes = sieve [2..]
sieve (p : xs) = p : sieve [x | x <− xs, x ‘mod‘ p > 0]


The paper then goes on to show several FP forms that are true to the original algorithm.

I thought this would be a good learning exercise, so I coded up my own version of the Sieve in purely functional Haskell:



-- Find primes up to n 
primes :: Int -> [Int]
primes n = drop 1 $ takeWhile (< n ) $ filter (/=0) $ sieve [0..] 1 $ 
                ceiling $ sqrt $ fromIntegral n 

-- Mark composites up to limit.  All composite numbers will be set to zero 
-- by ANDind with a boolean list of multiples of n.
sieve :: [Int] -> Int -> Int-> [Int]
sieve a n limit | n >= limit  = a
sieve a n limit =  sieve (a `land` (mask n)) next_prime limit 
    -- Next prime will be next non-zero element in the list
    where next_prime = fromJust (find (>n) a)

-- Generate an infinite list of Booleans.  False at multiples of n, starting at n^2 
mask :: Int -> [Bool]
mask 1 = True : mask 1
mask n = (replicate (n^2) True) ++ (rep n)
    where rep n = False:(replicate (n-1) True) ++ (rep n)

-- Merge together a boolean list and an integer list
land :: [Int] -> [Bool] -> [Int]
land (a:as) (b:bs) = (if b then a else 0) : land as bs
land _ _ = [] 



This Haskell code is some of my first, so please be gentle with your comments.

The interesting thing here is the use of Haskell's lazy evaluation. Here, 'lazy' means an expression isn't evaluated until it's needed. For example, the Haskell construct [1..] generates an infinite list of integers. If you attempt to use the entire infinite list to, say, find all the odd integers, Haskell will happily comply: filter odd [1..] and will take an infinite amount of time.

If, however, you just take a finite set of the result: take 10 (filter odd [1..]) then Haskell will return only the first 10 odd integers. This is a powerful concept.