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.
