PP 4 - Recursion | Christian's Notes

A list of reflective questions to ask yourself Antifragile Availability bias Black Swan Bottlenecks Cause and Effect Compound Interest Confirmation Bias Create momentum to make progress Emergence Environment Design Every field has some core principles and ideas upon which all other derive Evolution Excellence is mundane Fail Fast So You Can Fix Early Feedback Loop First instinct fallacy Force multiplier Free Rider Problem Friction Gall's Law Hanlon's Razor Haskell Hickam's Dictum Hindsight Bias How to Acquire Mental Models Increase your leverage to become more productive Innovation Multiplier Inversion Leverage Local maxima vs. Global maxima Mario Marketing Mental Models Metcalfe's Law Minimize time getting into position, just go Mise en place Network Effects Not making time for yourself first leads to burnout Occam's Razor Opportunity Cost Overton windows Perverse Incentive Positive Sum Post Hoc Ergo Propter Hoc Fallacy PP 1 - Introduction to Haskell PP 2 - Types and classes PP 3 - Functions and lists PP 4 - Recursion PP 5 - Higher-order functions PP 6 - Declaring types and type classes Premature Optimization Reciprocity Regression to the Mean Sharpen the saw Sherlock Holmes and Mental Models Signal vs. Noise Skin in the Game Stop being ungrateful of having so little life, and be grateful that you were given any at all Survivorship bias Take on the role before you can assume the role The Barbell Strategy The Diderot Effect The Dunning-Kruger Effect The Feature-Positive Effect The Ivy Lee Method for daily planning The Law of Inertia The Lindy Effect The Map Is Not The Territory The Mere-Exposure Effect The Pareto Principle The Pauli Exclusion Principle The Pratfall Effect The QEC method The Red Queen Effect Theory of Constraints To catch a second wind, you have to stay in the game long enough Using notes to advance in life Via Negativa Wittgenstein's Ruler Working on vs. working in Your second brain should actively grow and compound Zero Sum

Learning goals

To understand the structure of a recursive function definition
To be able to read and write recursive function definitions on lists
To be able to read and write recursion definitions that make use of multiple recursion or mutual recursion
To be able to write recursive function definitions in a structured fashion

Advice on Recursion (book, chapt 6.6)

Define the type
Enumerate the cases (write them down)
Define the simple cases
Define the other cases
Generalize and simplify

Recursive Functions

In Haskell, it can be useful to do recursion with pattern matching. E.g.

fac 0 = 1
fac n = n * fac (n-1)

And so it is when you generally define recursions like this one. You have a base case and then the recursive case.

Recursion on Lists

Example

product :: Num a => [a] -> a
product [] = 1
product (n:ns) = n * product ns

Which can be used to define fac, like so: fac n = product [0..n].

Example 2

length :: [a] -> Int
length [] = 0
length (_:xs) = 1 + length xs

Example 3

reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

Multiple Arguments

zip :: [a] -> [b] -> [(a,b)]
zip [] _ = []
zip _ [] = q]
-- Recursive case works by using the cons operator to prepend (x,y) to the list generated by the recursive call.
zip (x:xs) (y:ys) = (x,y) : zip xs ys

drop :: Int -> [a] -> [a]
drop 0 xs = xs
drop _ [] = []
drop n (_:xs) = drop (n-1) xs

(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
-- Similar to zip: prepends x to list created by recursive call with cons operator.
(x:xs) ++ ys = x : (xs ++ ys)

Quicksort

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = quicksort smalls ++ [x] ++ quicksort greats
	where
		smalls = [i | i <- xs, i <= x]
		greats = [j | j <- xs, j > x ]