Learning Haskell
Haskell and FP Notes
Language Rules
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 (op)
.
(+ 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).
4. '
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.
Lists
1. Lists are Homogenous
Haskell lists are homogenous, meaning they only accept one type.
"abc"
is just a syntactical sugar for ['a','b','c']
.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 1:2:3:[]
.
|
|
3. Indexing and Comparing
You can index a list using (!!) :: [a] -> Int -> a
.
|
|
You can use comparison operators like >
, <
, >=
, <=
, /=
, and ==
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
Get Element(s)
head :: [a] -> a
get first elementtail :: [a] -> [a]
rest of elements (except first)last :: [a] -> a
get last elementinit :: [a] -> [a]
all elements except for last
|
|
List Infos
length :: [a] -> Int
gets lengthnull :: [a] -> Bool
check if list is emptyelem :: a -> [a] -> Bool
check if element is in the list, usually used in infix form
|
|
List Ops
reverse :: [a] -> [a]
reverses a listtake :: Int -> [a] -> [a]
prefix of first n elementsdrop :: Int -> [a] -> [a]
suffix after first n elementsmaximum :: [a] -> a
get maximum elementminimum :: [a] -> a
get minimum elementsum :: [a] -> a
get sum of elements (equivalent tofoldl' (+) 0
)product :: [a] -> a
get product of elements (equivalent tofoldl' (*) 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
).
If 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 listrepeat :: a -> [a]
repeats the element infinitely to create an infinite listreplicate :: Int -> a -> [a]
creates a list of length n of that element, defined asreplicate 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
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.
|
|
Practice
- 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 useand :: [Bool] -> Bool
to 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 theand
of those booleans as a condition to filter out numbers that are products of any number inns
. - 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
ns
.
|
|
- 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
Implementcompare' -> (Int -> Int -> Boolean) -> [Int] -> [Int] -> Boolean
that makes comparison between two lists of integers given a comparison function (for example, prefixed functions(>)
, or(<)
). Match the list comparison functionality with the built-in one in Haskell. Note that the comparison function only works forInt
, not[Int]
.
Syntactic sugar for function composition in Haskell is $
, so f $ g x
is equivalent to f (g x)
.
First, we zip a
and 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.
|
|