Haskell Flashcards
What is a functor?
A functor is a container which provides a function fmap which allows us to transform its values using a function, while keeping the structure of the container the same.
Defining a functor instance for a data type
If the data type declaration is
“data TypeName a = Fizz a | Buzz (TypeName a) a”
The functor instance is
instance Functor TypeName where
fmap f (Fizz a) = Fizz (f a)
fmap f (Buzz b a) = TypeName (fmap f b) (f a)
Defining a functor instance for the data type “data Tree a = Leaf a | Node (Tree a) a (Tree a) (Tree a)”
instance Functor Tree where
fmap f (Leaf a) = Leaf (f a)
fmap f (Node left a mid right) = Node (fmap f left) (f a) (fmap f mid) (fmap f right)
What do tail and init do, and what is their syntax?
tail [1, 2, 3, 4, 5] = [2, 3, 4, 5]
init [1, 2, 3, 4, 5] = [1, 2, 3, 4]
What does zip do?
It turns a pair of lists into a list of pairs, up until the length of the shorter pair
Example:
zip [1, 2, 3, 4] [5, 6, 7] = [(1,5),(2,6),(3,7)]
What does zipWith do?
zipWith (op) a b
zips the lists a and b, and then performs the operation on each pair
Concatenating two lists
Use the ++ operator
Example: map (y*) x ++ mymult x ys
Example of patterns in function definition
mymult x [] = []
mymult x (y:ys) = map (y*) x ++ mymult x ys
Using zipWith to work out the differences between consecutive numbers in a list
zipWith (-) vge (tail vge))
Calculates A_i - A_i+1
Using length to calculate the number of items in myList which satisfy “condition”
length [x | x <- myList, condition]
Haskell if statement syntax
if <condition>
then <action>
else <action></action></action></condition>
if var rem 2 == 0
then putStrLn “Even”
else putStrLn “Odd”
Syntax for writing a function definition with multiple cases
functionName <pattern>
| <condition> = <value>
| <condition> = <value>
| otherwise = <value></value></value></condition></value></condition></pattern>
partitionHelper (x:xs) n (y:ys)
| sameSign n x == True = partitionHelper xs x ((x:y):ys)
| sameSign n x == False = partitionHelper xs x ([x]:y:ys)
AND, OR, NOT, not equal operators
AND = &&
OR = ||
NOT = not (e.g. (not True) = False)
not equal = =
Prepending an item to a list
Use the “:” operator
1 : [2, 3, 4] = [1, 2, 3, 4]
What is lambda calculus?
Rule system for describing computations solely via function abstraction and application. It’s the simplest known Turing-complete programming language.
Definition of a λ-expression
A variable v is a λ-expression
If M is a λ-expression, then (λv.M) is too. This is abstraction: defining a function with parameter v and body M.
If M and N are λ-expressions, then (MN) is a λ-expression (this is the application of M to N).
λ-expression associativity rules
Application is left-associative, meaning MNP = ((MN)P)
Abstraction is right-associative
Application has precedence over abstraction, meaning that λx.λy.xy = λx.(λy.(xy))
Bound and free variables
A variable is bound if it occurs in a function that takes a variable of the same name as input, so λx.x is bound. The opposite of bound is free, like the x in λy.x.
Beta-reduction
Beta-reduction allows us to substitute the argument of an abstraction with the value of an application ((λx.M[x])N) => (M[x := N]).
Example: (λx.x)a = a
Alpha-conversion
Allows us to resolve name conflicts by renaming bound variables like this: (λx.M[x]) => (λy.M[y])
This prevents us from capturing free variables when beta-reducing expressions.
What is a functional?
A function that returns another function.
What is currying?
Turning a function of n arguments into a function of n-1 arguments.
We create a function that takes 1 input and returns a function which takes n-1 arguments and takes 1 input, which in turn returns a function which…
Currying allows for functions with multiple arguments in languages like Haskell which only support unary functions.
Constructing nameless function
“\x -> x + x” is a nameless function for computing f(x) = 2x
“\x -> (\y -> x + y)” is a nameless function for computing f(x, y) = x+y
What do the backtick and brackets do?
Backtick turns a function name into an infix operator. mod 3 2 = 3 mod 2.
Brackets turn an infix operator into a function. 1 + 2 = (+) 1 2.
Time complexity of list operations
O(n) for reversing and getting length
O(1) for “:” and getting the head or tail
Using lists for pattern matching in function definitions
startsWithA :: [Char] -> Bool
startsWithA [‘a’, _, _] = True
startsWithA _ = False
# Matches 3-element lists starting with “a”
startsWithA :: [Char] -> Bool
startsWithA (‘a’:_) = True
startsWithA _ = False
# Matches any list of length at least 1 whose first entry is a.
Use [] when there’s a limited number of items and () when it can be any length. “_” represents anything.
Syntax for typeclass restrictions
sumTwo :: Num a => [a] -> a
This means that the function only works on a list of values of type “a”, which is any member of the Num typeclass (includes Int and Integer).
Syntax for generating a list with guards
[x | x <- [1..5], x mod 2 == 0]
= [2, 4]
Syntax for generating a sequence of numbers
[a..b]
Example: [1..5]
Syntax for generating a list of tuples using multiple generators
[(x, y) | x <- [1..3], y <- [x..3]]
Guards and generators can even be interspersed, but guards can only refer to variables on their left
What is a side effect?
A hidden state change that results from a function modifying or relying upon objects external to its parameter list. A pure function is one without side effects
What is a functional programming language?
A functional programming language supports and encourages a programming style with function application and composition as basic building blocks.
Why do we need types?
They tell us how to interpret a variable, provide restrictions on valid operations, and are required if you want to know what a bit pattern means
What is parametric polymorphism?
Where we write a single implementation of a function which applies generically and identically to values of any type
What is a class?
A collection of types that support specified, overloaded operations called methods. Overloaded means “having at least one class constraint”
Linear recursive function
One with only one self-reference, as opposed to a multiple recursive function
Tail recursive
The last thing the function does is call itself
What is a fold?
“foldr” takes a function of two variables, a value, and a list. It applies the function to the value and the last item of the list, and then it applies it to the second to last item and that result, and so on. “foldl” does the same thing but starting from the beginning.
What is lazy evaluation?
Deferring computation until strictly necessary. Expressions are not evaluated when they are bound to variables, instead their evaluation is only done when their result is needed by other computations.
