It is best to think of Haskell functions as math functions, not as C or Python functions; likewise, Haskell variables as math variables (for unknowns and constants), not as C or Python variables (mutable state).
Because of this, you will hear me say “f(4) equals/gives 10” not “returns 10”, “codomain” not “return type”, “apply this function to that parameter” (plugging in) not “call this function”. Both angles are correct, you don't have to speak like me, but the algebra angle is better for beginners than the control-flow angle.
favouriteNumber :: Integer -- Type signature. If omitted, the most general
-- type is inferred.
favouriteNumber = 4
isMultipleOf3 :: Integer -> Bool -- Function type, "domain -> codomain"
isMultipleOf3 i = mod i 3 == 0
in HaskellBasics.hs
Most types can be omitted, in which case the computer infers the most general types.
It is still a good idea to write explicit types for important values and functions as a courtesy to your human readers. (It is OK to copy from the inferred type.)
This example takes two integer parameters and gives an integer answer:
diffSq :: Integer -> Integer -> Integer diffSq x y = (x - y) * (x + y)in HaskellBasics.hs
How to use: diffSq 2 1
There is a bit more theory on types like X -> Y -> Z in a
later lecture.
Two ways of local definitions:
diffSqV3a, diffSqV3b :: Integer -> Integer -> Integer
diffSqV3a x y =
let minus = x - y
plus = x + y
in minus * plus
diffSqV3b x y = minus * plus
where
minus = x - y
plus = x + y
in HaskellBasics.hs
The difference:
“let-in” is an expression, can be used
wherever an expression is expected, e.g, 2 * (let x=5 in
x+1)
“where” is not part of an expression, e.g., “2 * (x+1
where x=5)” is illegal. It is part of a definition, e.g., “y =
... where x=5” is legal. There is another place you can use
“where”, shown in slowFib2 in the next section.
Haskell conditional branching includes if-then-else, and additionally pattern matching and guards (nicer syntax for if-then-elseif-etc).
-- Pattern matching.
slowFactorial :: Integer -> Integer
slowFactorial 0 = 1
slowFactorial n = n * slowFactorial (n - 1)
-- if-then-else version.
slowFactorial2 :: Integer -> Integer
slowFactorial2 n = if n == 0
then 1
else n * slowFactorial2 (n - 1)
-- Slow Fibonacci (yawn) to show you can have more pattern matching.
-- "This Fibonacci joke is as bad as the last two you heard combined."
-- https://twitter.com/sigfpe/status/776420034419658752
slowFib :: Integer -> Integer
slowFib 0 = 0
slowFib 1 = 1
slowFib n = slowFib (n-1) + slowFib (n-2)
-- Long form pattern matching---using a "case-of" expression:
slowFib2 :: Integer -> Integer
slowFib2 x = case x of
0 -> 0
1 -> 1
n -> slowFib2 n1 + slowFib2 n2
-- The other place you can use "where". This one is part of "n -> ...".
where
n1 = n - 1
n2 = n - 2
-- Using guards.
slowFib3 :: Integer -> Integer
slowFib3 n | n == 0 = 0
| n == 1 = 1
| otherwise = slowFib3 n1 + slowFib3 n2
-- This "where" is part of the whole "slowFib3 n ...".
where
n1 = n - 1
n2 = n - 2
in HaskellBasics.hs
You will see something like this all the time:
f (x*2 + 1) :: Integer
This is notation for “the type of f (x*2 + 1)
is Integer”. It is used in both actual code and my explanation
prose.
Those two things are called:
f (x*2 + 1) :: Integer ^^^^^^^^^^^ ^^^^^^^ term type
One more example:
h . g :: Char -> Bool ^^^^^ ^^^^^^^^^^^^ term type
“term” is also widely known as “expression”. I like “term” because it is shorter, and because “type” is also called “type expression”.
What about “value”? Answer: 5+4 is a term; the result of
evaluating it, 9, is a value. But I am lax about this.
(How to create code vs how to run code.)
Everyone teaches how to run recursive code. That still doesn't help you with creating. (Probably impedes you actually—hand-running recursive code is distracting.)
I teach you both. I show you that creating recursive code can be easier if you don't try to run it.
Synthesis view (how I write recursive code): Pretend induction = Use induction to prove something that still contains unknowns, ah but during the proof you find out how to solve for the unknowns!
How I coded up slowFactorial:
WTP: For all natural n: slowFactorial n = n!
Base case:
WTP: slowFactorial 0 = 0!
Notice 0! = 1, so if I code up
slowFactorial 0 = 1
I get slowFactorial 0 = 0!
Induction step:
Let natural n ≥ 1 be given.
Induction hypothesis: slowFactorial (n-1) = (n-1)!
WTP: slowFactorial n = n!
Notice
n! = n*(n-1)! = n * slowFactorial (n-1) by I.H.
So if I code up
slowFactorial n = n * slowFactorial (n-1)
I get slowFactorial n = n!
Comments:
The proof structure guides the code structure.
I refuse to imagine “what if I unfold slowFactorial (n-1) by hand?”. The I.H. already tells me the answer so I just use it. This helps me focus.
The catch: I need to make up my mind and carefully write down the specification—the WTP, what answer my function should give. I need the I.H. to be clear, not muddy.
You get both code and correctness proof. BOGO deal of the day! Why don't people do this more?!
Evaluation view (how a computer or an enslaved student runs code): Plug and chug:
slowFactorial 3 → 3 * slowFactorial (3 - 1) → 3 * slowFactorial 2 → 3 * (2 * slowFactorial (2 - 1)) → 3 * (2 * slowFactorial 1) → 3 * (2 * (1 * slowFactorial (1 - 1))) → 3 * (2 * (1 * slowFactorial 0)) → 3 * (2 * (1 * 1)) → 3 * (2 * 1) → 3 * 2 → 6
Is it OK if you write “=” instead of “→”? Yes. I write “→” just for emphasis that the computer does only one direction.
The next example shows recursion/induction on lists. Crash course on Haskell list syntax:
types: [Integer], [Bool], etc.
empty list: []
lists of known items: [4, 1, 6], syntax sugar for
4 : (1 : (6 : []))
Those parentheses are optional, like this: 4 : 1 : 6 : []
Formally (recursive definition as in CSCB36): a list is one of:
[]
These are singly-linked lists. To reach the nth item (or even just the nth node), you need to take Θ(n) time to go through all the nodes from the beginning. These are not arrays.
Implement append to concatenate two lists. It is already
available from the standard library as the “++” operator, but let's
learn how to do it.
But we're doing functional programming with immutable lists, can't modify either input list. Intead: produce a new list that contains the contents of the two input lists.
append :: [Integer] -> [Integer] -> [Integer] -- WTP: append xs ys = concatenation of xs and ys -- = list of elements from xs followed by elements from ys -- Strategy: induction on xs -- Base case: xs is empty, answer is ys append [] ys = ys -- Induction step: Suppose xs has the form x:xt (and xt is shorter than xs). -- E.g., xs = [1,3,5,8] = 1:3:5:8:[] -- so x = 1, xt = 3:5:8:[] -- -- Induction hypothesis: append xt ys = concatenation of xt and ys -- E.g., append (3:5:8:[]) (4:1:6:[]) = 3:5:8:4:1:6:[] -- WTP: append (x:xt) ys = concatenation of x:xt and ys -- E.g., append (1:3:5:8:[]) (4:1:6:[]) = 1 : 3:5:8:4:1:6:[] -- Hey, the "3:5:8:4:1:6:[]" part is already done by I.H.! append (x:xt) ys = x : append xt ysin HaskellBasics.hs
Sometimes the recursion happens in a helper function because you need to
introduce an accumulator parameter. A famous example is reversing a list.
(Already in the standard library as “reverse”, but let's learn
how to do it.)
Note that although this direct recursion is correct, it takes quadratic time.
(Reminder: append xs ys takes time Θ(length of xs).)
rev [] = [] rev (x:xt) = append (rev xt) [x]
Here is a linear-time solution. It needs the help of an accumulator.
rev :: [Integer] -> [Integer] rev xs = revhelper xs [] -- WTP: ∀xs, acc: revhelper xs acc = concatenation of xs reversed and acc -- (I make explicit "∀xs, acc" because it is helpful later.) -- Example: revhelper (4:1:6:[]) (2:5:[]) = 6:1:4:2:5:[] -- Use induction on xs. -- Base case: xs is empty, answer is acc. revhelper [] acc = acc -- Induction step: Suppose xs has the form x:xt (and xt is shorter than xs). -- Induction hypothesis: -- ∀acc: revhelper xt acc = concatenation of xt reversed and acc -- Useful to note: The I.H. holds for any acc you want, not just the "original" acc. -- WTP: -- ∀acc: revhelper (x:xt) acc = concatenation of (x:xt) reversed and acc -- Eureka: -- concatenation of (x:xt) reversed and acc -- = concatenation of xt reversed and (x : acc) -- = revhelper xt (x : acc) revhelper (x:xt) acc = revhelper xt (x : acc)in HaskellBasics.hs