Notes for Week 4 Syntax in Functions

Links:

• Chapter 4 agenda
• Syntax in Functions online chapter

Exercises:

Exercise 1

Define a recursive function mult that takes two positive integers a and b and returns a * b, but only uses addition.

Exercise 2

Rewrite the following function using let statements

roots a b c = ((-b + sqrt(b*b - 4*a*c)) / (2*a), (-b - sqrt(b*b - 4*a*c)) / (2*a))

Exercise 3

Using Guards, define a function named sign that takes a single numeric parameter. The function will return 1 if the parameter is positive, -1 if the parameter is negative or 0 otherwise.

Exercise 4

Euler Problem 1:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. 
The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

Solve Euler Problem 1 using each of the following language constructs:

• Pattern Matching
• Guards
• Where
• Let
• Case

Questions raised during the group:

1. What other operators can you pattern match across in addition to the : operator?
2. What (if any) are the performance benefits of guards versus if/then/else statements?
3. Are nested functions a code smell (as they are hard to test) or idiomatic Haskell?

Answers to Exercises:

mult :: Int -> Int -> Int
mult 0 _ = 0
mult _ 0 = 0
mult a b = a + (a `mult` (b - 1))

Alternative Answer

mult :: Integer -> Integer -> Integer
mult x 0 = 0
mult x y = x + mult x (y - 1)

roots1 a b c = 
let f1 = sqrt(b*b - 4*a*c)
    f2 = 2*a
in ((-b + f1) / f2, (-b - f1)/f2)

roots2 a b c = ((-b + f1) / f2, (-b - f1)/f2)	
  where f1 = sqrt(b*b - 4*a*c) 
        f2 = 2*a	

sign :: (Ord a, Num a) => a -> Int
sign n
  | n < 0 = (-1)
  | n > 0 = 1
  | otherwise = 0

euler1pm :: Int -> Int
euler1pm x =  sum [n | n <- [1 .. (x-1)], (n `mod` 3 == 0 || n `mod` 5 == 0)]

euler1grd :: Int -> Int
euler1grd x = sum [n | n <- [1 .. (x-1)], filter n]
  where filter n
         | n `mod` 3 == 0 || n `mod` 5 == 0 = True
         | otherwise = False
  
euler1whr :: Int -> Int
euler1whr x = sum [n | n <- [1 .. (x-1)], threeOrFive n]
  where threeOrFive y = y `mod` 3 == 0 || y `mod` 5 == 0

euler1let :: Int -> Int
euler1let x = sum [n | n <- [1..(x-1)], let threeOrFive = n `mod` 3 == 0 || n `mod` 5 == 0]

euler1cse :: Int -> Int
euler1cse x = case [n | n <- [1 .. (x -1)], n `mod` 3 == 0 || n `mod` 5 == 0] of [] -> 0
                                                                                 xs -> sum (xs) 

Alternative Answers

three x = x `mod` 3 == 0
five x = x `mod` 5 == 0
five_or_three x = three x || five x

match_total (x:xs) = (if five_or_three x then x else 0) + match_total xs
match_total [] = 0

guard_total (x:xs)
    | null xs = 0
    | five_or_three x = x + guard_total xs
    | otherwise = guard_total xs

where_total (x:xs) = sum [acc x | x <- xs]
    where acc x = (if five_or_three x then x else 0)

let_total (x:xs) =
    let acc x = (if five_or_three x then x else 0)
    in sum [acc x | x <- xs]

case_total xs = 
     case xs of [] -> 0
                (x:xs) -> (if five_or_three x then x else 0) + case_total xs

match_total [1..1000]
where_total [1..1000]
let_total [1..1000]
case_total [1..1000]

Interesting Asides

1. Matt's Haskell/JRuby Game of Life race.
2. Bonobo Monkeys
3. AI Challenge (Katie to explain)
4. Does the JVM have tail-call optimisation
5. if-then-else as a function
6. 404 for Learn You a Haskell - http://learnyouahaskell.com/something
7. Non-empty list http://www.haskell.org/haskellwiki/Non-empty_list
8. Using Ruby Functionally http://experthuman.com/programming-with-nothing
9. "Interesting" addition as a recursive function:

addi x 0 = x

addi x y = 1 + addi x (y - 1)