Haskell

Question 1

What is a functor?

Answer 1

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.

Question 2

Defining a functor instance for a data type

Answer 2

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)

Question 3

Defining a functor instance for the data type “data Tree a = Leaf a | Node (Tree a) a (Tree a) (Tree a)”

Answer 3

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)

Question 4

What do tail and init do, and what is their syntax?

Answer 4

tail [1, 2, 3, 4, 5] = [2, 3, 4, 5]
init [1, 2, 3, 4, 5] = [1, 2, 3, 4]

Question 5

What does zip do?

Answer 5

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)]

Question 6

What does zipWith do?

Answer 6

zipWith (op) a b

zips the lists a and b, and then performs the operation on each pair

Question 7

Concatenating two lists

Answer 7

Use the ++ operator
Example: map (y*) x ++ mymult x ys

Question 8

Example of patterns in function definition

Answer 8

mymult x [] = []
mymult x (y:ys) = map (y*) x ++ mymult x ys

Question 9

Using zipWith to work out the differences between consecutive numbers in a list

Answer 9

zipWith (-) vge (tail vge))
Calculates A_i - A_i+1

Question 10

Using length to calculate the number of items in myList which satisfy “condition”

Answer 10

length [x | x <- myList, condition]

Question 11

Haskell if statement syntax

Answer 11

if <condition>
then <action>
else <action></action></action></condition>

if var rem 2 == 0
then putStrLn “Even”
else putStrLn “Odd”

Question 12

Syntax for writing a function definition with multiple cases

Answer 12

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)

Question 13

AND, OR, NOT, not equal operators

Answer 13

AND = &&
OR = ||
NOT = not (e.g. (not True) = False)
not equal = =

Question 14

Prepending an item to a list

Answer 14

Use the “:” operator
1 : [2, 3, 4] = [1, 2, 3, 4]

Question 15

What is lambda calculus?

Answer 15

Rule system for describing computations solely via function abstraction and application. It’s the simplest known Turing-complete programming language.

Question 16

Definition of a λ-expression

Answer 16

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).

Question 17

λ-expression associativity rules

Answer 17

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))

Question 18

Bound and free variables

Answer 18

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.

Question 19

Beta-reduction

Answer 19

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

Question 20

Alpha-conversion

Answer 20

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.

Question 21

What is a functional?

Answer 21

A function that returns another function.

Question 22

What is currying?

Answer 22

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.

Question 23

Constructing nameless function

Answer 23

“\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

Question 24

What do the backtick and brackets do?

Answer 24

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.

Question 25

Time complexity of list operations

Answer 25

O(n) for reversing and getting length
O(1) for “:” and getting the head or tail

Question 26

Using lists for pattern matching in function definitions

Answer 26

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.

Question 27

Syntax for typeclass restrictions

Answer 27

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).

Question 28

Syntax for generating a list with guards

Answer 28

[x | x <- [1..5], x mod 2 == 0]
= [2, 4]

Question 29

Syntax for generating a sequence of numbers

Answer 29

[a..b]
Example: [1..5]

Question 30

Syntax for generating a list of tuples using multiple generators

Answer 30

[(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

Question 31

What is a side effect?

Answer 31

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

Question 32

What is a functional programming language?

Answer 32

A functional programming language supports and encourages a programming style with function application and composition as basic building blocks.

Question 33

Why do we need types?

Answer 33

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

Question 34

What is parametric polymorphism?

Answer 34

Where we write a single implementation of a function which applies generically and identically to values of any type

Question 35

What is a class?

Answer 35

A collection of types that support specified, overloaded operations called methods. Overloaded means “having at least one class constraint”

Question 36

Linear recursive function

Answer 36

One with only one self-reference, as opposed to a multiple recursive function

Question 37

Tail recursive

Answer 37

The last thing the function does is call itself

Question 38

What is a fold?

Answer 38

“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.

Question 39

What is lazy evaluation?

Answer 39

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.