Haskell and FP Notes
1. Execution Priorities
Haskell functions have highest priority in execution.
2. Function Infixing and Operator Prefixing
Haskell functions can be infixed and used like an operator with
`fn`, and operators can be prefixed and used like a function with
(+ a b).
3. Everything is an Expression
Haskell is declarative, hence everything has to return a value (an expression). In Haskell, there must be an else paired with if (think
a if COND else b expression in Python).
' is a Valid Character for Varialbe Names
In Haskell, single quotation
' is usually used to denote either a strict (non-lazy) version of a function, or a slightly modified version of a function. For example,
foldl' in the
Data.List package is the eager version of
foldl that avoids stack overflow and stack allocation overhead through eager execution.
1. Lists are Homogenous
Haskell lists are homogenous, meaning they only accept one type.
"abc"is just a syntactical sugar for
2. List Concatenation and Prepend
List concatenation uses the
(++) :: [a] -> [a] -> [a] operator, and prepending one element uses the
(:) :: a -> [a] -> [a] operator.
Conventionally, no space is put around the
: operator, and space is put around the
++ operator, but functionally space doesn’t matter here.
[1,2,3]is actually just syntactic sugar for
3. Indexing and Comparing
You can index a list using
(!!) :: [a] -> Int -> a.
You can use comparison operators like
== with lists. Comparison starts from the leftmost of both lists, and continues right if both lists have equal elements, and returns the comparison value when either the elements are different or the last element is reached.
4. Common Functions
head :: [a] -> a
get first element
tail :: [a] -> [a]
rest of elements (except first)
last :: [a] -> a
get last element
init :: [a] -> [a]
all elements except for last
length :: [a] -> Int
null :: [a] -> Bool
check if list is empty
elem :: a -> [a] -> Bool
check if element is in the list, usually used in infix form
reverse :: [a] -> [a]
reverses a list
take :: Int -> [a] -> [a]
prefix of first n elements
drop :: Int -> [a] -> [a]
suffix after first n elements
maximum :: [a] -> a
get maximum element
minimum :: [a] -> a
get minimum element
sum :: [a] -> a
get sum of elements (equivalent to
foldl' (+) 0)
product :: [a] -> a
get product of elements (equivalent to
foldl' (*) 1)
5. Ranges and Infinite Lists
[A,B..C] will generate the range starting from
A (inclusive), ending at
C (inclusive), with the second element being
B (defining a step
fromEnum B - fromEnum A).
C is absent, then it will be an infinite list.
Note, it’s inadvisable to use Float in range, as it is prone to precision issues.
Some useful functions includ:
cycle :: [a] -> [a]
cycles through the list to create an infinite list
repeat :: a -> [a]
repeats the element infinitely to create an infinite list
replicate :: Int -> a -> [a]
creates a list of length n of that element, defined as
replicate n s = take n (repeat s)
6. List Comprehension
Similar to list comprehension in Python, but in a more mathematical syntax.
[ expr | var <- lst, COND ] will return a list of results of the expression
expr where the variable
var is a value in the list
lst that satisfies the condition
COND. Note that there can be multiple conditions and variable assignments, all separated by comma.
Tuples are also similar to Python tuples, and contrary to lists, tuples accept different types to be mixed together.
However, each tuple has its own type. For example, a tuple
(3, 'a', "abc") has type
(Num, Char, [Char]). So we cannot mix up different types of tuples in, for example, lists.
For pairs of tuples, we can use the functions
fst :: (a, b) -> a and
snd :: (a, b) -> b to get the first and second element.
You can also zip together two lists (like in Python) using
zip :: [a] -> [b] -> [(a,b)]. Note that Haskell will use the shorter of the two lists as the length of the zipped list.
- Use at least 2 methods to get the first 20 odd numbers starting from 1 (inclusive, ascending order).
A few solutions:
- Generate an odd infinite list from 1 and take first 20
- Generate an infinite list of integers starting from 1 and filter it, only keeping odd numbers, and then take first 20 of that infinite list
- Generate an infinite list of integers starting from 1 and filter it, only keeping numbers that are not even, and then take first 20 of that infinite list
- Calculate the last element of the desired odd list (1 + 2 * 19), and generate an odd list from 1 to (1 + 2 * 19)
- Calculate the last element of the desired odd list (1 + 2 * 19), and generate an odd list from (1 + 2 * 19) to 1, and then reverse it
- Given a list of integers, find all positive integers under 100 (inclusive) that is not a multiple of any of those integers. You can use
mod :: Int -> Int -> Int, usually used in its infixed form. You can also use
and :: [Bool] -> Boolto find whether all boolean values in a list are true.
Starred answers use patterns/functions/ideas that are not yet introduced.
A few solutions:
- Generate a list of integers from 1 to 100, and then use list comprehension to generate a list of booleans of whether each number in that list is not divisible by each number in
ns, and use the
andof those booleans as a condition to filter out numbers that are products of any number in
- You can use a filter function with a lambda condition function instead of the outer list comprehension, otherwise, same as Answer 1.
- You can also define a recursive function to do filtering for each element in
- Implement a function that checks if all elements of a list is smaller or equal to another list. A simple example of function declaration is
functionName paramA paramB = expressionUsingParams.
A few solutions:
- You can use the zip function to zip the two arrays together and check if all first elements (from a) are smaller or equal to all second elements (from b) in corresponding pairs.
- You can use the same idea, but write zip yourself through generating appropriate indices list. Don’t forget to use the minimum length of the two lists.
- Need to know how to write recursive functions
compare' -> (Int -> Int -> Boolean) -> [Int] -> [Int] -> Booleanthat makes comparison between two lists of integers given a comparison function (for example, prefixed functions
(<)). Match the list comparison functionality with the built-in one in Haskell. Note that the comparison function only works for
Syntactic sugar for function composition in Haskell is
f $ g x is equivalent to
f (g x).
First, we zip
b together, and then we compare each pair from the first. If at the current pair is the last pair (tail is empty list), we should return the results of the comparison on the current pair. Only when all but the last pair are equal does this branch gets triggered. If the pair is equal, we should check the next pair. If the comparison succeeded (returns true), we should return true and exit the recursive loop. If this is not the last pair, the pair isn’t equal, and the comparison failed, we should return false, as the first failed comparison (first different pair in zipped pairs failed) would indicate the whole comparison should return false.