http://www.seas.upenn.edu/~cis194/spring13/hw/04-higher-order.pdf

gistfile1.hs

-- Homework 4 - http://www.seas.upenn.edu/~cis194/spring13/hw/04-higher-order.pdf

import Data.List

-- Exercise 1: Wholemeal programming

fun1 :: [Integer] -> Integer
fun1 []         = 1
fun1 (x:xs)
    | even x    = (x - 2) * fun1 xs
    | otherwise = fun1 xs

fun1' :: [Integer] -> Integer
fun1' = foldl' (\b a -> (a - 2) * b) 1 . filter even

fun2 :: Integer -> Integer
fun2 1             = 0
fun2 n | even n    = n + fun2 (n `div` 2)
       | otherwise = fun2 (3 * n + 1)

fun2' :: Integer -> Integer
fun2' = sum
      . filter even
      . takeWhile (/=1)
      . iterate (\x -> if even x then x `div` 2 else x * 3 + 1)

-- Exercise 2: Folding with trees
data Tree a = Leaf
            | Node Integer (Tree a) a (Tree a)
    deriving (Show, Eq)

treeHeight :: Tree a -> Integer
treeHeight Leaf                = -1
treeHeight (Node height _ _ _) = height

insertNode :: a -> Tree a -> Tree a
insertNode x Leaf                         = Node 0 Leaf x Leaf
insertNode x (Node height left val right)
    | treeHeight left <= treeHeight right = Node (treeHeight newLeft + 1) newLeft val right
    | otherwise                           = Node (treeHeight newRight + 1) left val newRight
    where newLeft  = (insertNode x left)
          newRight = (insertNode x right)

foldTree :: [a] -> Tree a
foldTree = foldr insertNode Leaf

-- Exercise 3: More folds!

xor :: [Bool] -> Bool
xor = foldl1 (/=)

map' :: (a -> b) -> [a] -> [b]
map' f = foldr (\x xs -> f x : xs) []

myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f base xs = foldr (flip f) base (reverse xs)

-- Exercise 4: Finding primes
sieveSundaram :: Integer -> [Integer]
sieveSundaram n = map (\x -> 2*x+1) remainingNumbers
    where remainingNumbers = [1..n] \\ filter (<=n) [i+j+2*i*j | i <- [1..n], j <- [1..i]]