SICP stream examples in Haskell

1. A function that multiplies the squares of the odd elements of a list
2. A function that sums the odd fibonacci numbers up to n

So here's how we implement them in a unified way:

• In Haskell, there is syntax for enumerating the integers from 1 to n into a list: [1..n].
• To select the elements of a list xs satisfying condition p, use filter p xs.
• To apply a function f to every element of a list xs, returning a new list, using map f xs. The result is [(f x1), (f x2), ... (f xn)].
• To accumulate the elements of a list xs using binary function f, starting with z, use foldl f z xs. The result is (((z f x1) f x2) ... xn).

square x = x*x
mul_odd_squares xs = foldl (*) 1 (map square (filter odd xs))

fib x = if (x < 2) then x else (fib (x-1)) + (fib (x-2))
sum_odd_fibs n = foldl (+) 0 (filter odd (map fib [1..n]))

Now if we want to, say, compute the product of the squares of the first n fibonacci numbers:

mul_sqr_fibs n = foldl (*) 1 (map square (map fib [1..n]))

To really get into functional style, we can use the composition operator:

mul_odd_squares = (foldl (*) 1) . (map square) . (filter odd)
sum_odd_fibs n = ((foldl (+) 0) . (filter odd) . (map fib)) [1..n]

An example of delayed evaluation is creating the infinite list of fibonacci numbers:

add_lists x y = zipWith (+) x y
fibs = 0:1:(add_lists (tail fibs) fibs)

Haskell's list comprehension syntax makes it easy to do nested mappings:

prime_sum_pairs n = [(i,j,i+j) | i <- [1..n], j <- [1..i], prime (i+j)]

-- implementing the "prime" predicate, however, is a bit tricky:
multipleOf x y = (mod y x) == 0   -- True if y is a multiple of x
prime :: Int -> Bool
prime n = let find_prime (x:xs) | (square x) > n = True
              find_prime (x:xs) | multipleOf x n = False
              find_prime (x:xs) = find_prime xs
          in  find_prime primes

-- two definitions of the infinite list of primes:
primes = 2:(filter prime [3..])

primes = sieve [2..]
sieve (x:xs) = x:(sieve (filter (not . (multipleOf x)) xs))  -- Ratso's sieve

remove x = filter (/= x)
permutations [] = [[]]
permutations xs = [x:p | x <- xs, p <- permutations (remove x xs)]