Contents

Learning Haskell

Haskell and FP Notes

Language Rules

1. Execution Priorities

Haskell functions have highest priority in execution.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
-- ghci
succ 9 + max 5 4 + 1 -- eqluivalent to: (succ 9) + (max 5 4) + 1
-- output
16
-- ghci
succ 9 * 10
-- output
100
-- ghci
succ (9 * 10)
-- output
91

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

Tip
Even though we are calling them operators vs functions, they are both technically functions. They are slightly different syntactically from its origins in mathematical notations, whereas some functional languages that does not inherit the notations mathematics exlusively prefix the function (usually languages with parenthesis-based syntax). Lisp dialects such as Common Lisp, Clojure, Racket, and Scheme, for example, all notate addition with (+ a b).
1
2
3
4
5
6
7
fn A B
-- equivalent to
A `fn` B

A op B
-- equivalent to
(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.

Tip
Strings in haskell are lists of characters, and using "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.

Tip
Lists in Haskell are linked lists, and [1,2,3] is actually just syntactic sugar for 1:2:3:[].
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
-- ghci
[2,3] ++ [4,5]
-- output
[2,3,4,5]
-- ghci
2:[3,4,5]
-- output
[2,3,4,5]
-- ghci
2 ++ [3,4,5]
-- ERROR

3. Indexing and Comparing

You can index a list using (!!) :: [a] -> Int -> a.

1
2
3
4
5
6
7
8
-- ghci
[2,3,4,5] !! 1
-- output
3
-- ghci
(!!) [2,3,4,5] 1
-- output
3

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
-- ghci
[1,2,3] < [1,2,3]
-- output
False
-- ghci
[1,2,3] < [1,2,5]
-- output
True
-- ghci
[1,2,3] < [0,9,7]
-- output
False
-- ghci
[1,2,3] < [2,0,0]
-- output
True

4. Common Functions

Get Element(s)

  • 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
Warning
These functions will fail when the provided list is empty
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
-- ghci
head [1,2,3,4]
-- output
1
-- ghci
tail [1,2,3,4]
-- output
[2,3,4]
-- ghci
last [1,2,3,4]
-- output
4
-- ghci
init [1,2,3,4]
-- output
[1,2,3]

List Infos

  • length :: [a] -> Int
    gets length
  • null :: [a] -> Bool
    check if list is empty
  • elem :: a -> [a] -> Bool
    check if element is in the list, usually used in infix form
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
-- ghci
length [1,2,3,4]
-- output
4
-- ghci
null [1,2,3,4]
-- output
False
-- ghci
null []
-- output
True
-- ghci
5 `elem` [1,2,3,4]
-- output
False
-- ghci
3 `elem` [1,2,3,4]
-- output
True

List Ops

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

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

1
2
3
4
5
6
7
-- Get all elements in product set A x B
-- ghci
let a = [1,2,3]
let b = [4,5,6]
[ [x,y] | x <- a, y <- b ]
-- output
[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]

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.

1
2
3
4
5
6
-- ghci
[(1,2),(1,2,3)]
-- ERROR
-- ghci
[(1,2),(1,'a')]
-- ERROR

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.

1
2
3
4
5
6
7
-- ghci
fst ('a','b')
-- output
'a'
snd ('a','b')
-- output
'b'

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
-- ghci
zip "abc" [1,2,3]
-- output
[('a',1),('b',2),('c',3)]
-- ghci
zip "abc" [1,2,3,4,5,6,7]
-- output
[('a',1),('b',2),('c',3)]
zip [(1,2),(3,4)] "abcde"
-- output
[((1,2),'a'),((3,4),'b')]

Practice

  1. Use at least 2 methods to get the first 20 odd numbers starting from 1 (inclusive, ascending order).
Answer

A few solutions:

  1. Generate an odd infinite list from 1 and take first 20
  2. 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
  3. 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
  4. Calculate the last element of the desired odd list (1 + 2 * 19), and generate an odd list from 1 to (1 + 2 * 19)
  5. 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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
-- Answer 1
take 20 [1,3..] -- starting with 0 also works
-- Answer 2
take 20 [ x | x <- [1..], odd x ] -- starting with 0 also works
-- Answer 3
take 20 [ x | x <- [1..], not (even x) ] -- starting with 0 also works
-- Answer 4
[1,3..1+2*19]
-- Answer 5
reverse [1+2*19,1+2*18..1]
  1. 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] -> Bool to find whether all boolean values in a list are true.
Answer

Starred answers use patterns/functions/ideas that are not yet introduced.

A few solutions:

  1. 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 and of those booleans as a condition to filter out numbers that are products of any number in ns.
  2. You can use a filter function with a lambda condition function instead of the outer list comprehension, otherwise, same as Answer 1.
  3. You can also define a recursive function to do filtering for each element in ns.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
ns = [4,9,21]
-- Answer 1
[ x | x <- [1..100], and [ x `mod` y /= 0 | y <- ns ] ]
-- Answer 2*
filter (\ x -> and [ x `mod` y /= 0 | y <- ns ]) [1..100]
-- Answer 3*
-- if you are using ghci
filterMultipleOf n = filter (\ x -> x `mod` n /= 0 )
filterMultiplesInList (n:ns) nums = if (null ns) then (filterMultiple n nums) else (filterMultiplesInList ns (filterMultiple n nums))
-- if you are writing to a .hs file and loading in ghci with `:load FileName`
filterMultipleOf n = filter (\ x -> x `mod` n /= 0 )
filterMultiplesInList (n:ns) nums
  | null ns = filterMultipleOf n nums
  | otherwise = filterMultiplesInList ns (filterMultipleOf n nums)
-- ghci
filterMultiplesInList ns [1..100]
  1. 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.
Answer

A few solutions:

  1. 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.
  2. 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.
1
2
3
4
-- Answer 1
smallerEq a b = and [ fst pair <= snd pair | pair <- zip a b ]
-- Answer 2
smallerEq a b = and [ a !! i <= b !! i | i <- [0..minimum [length a,length b]-1]]
  1. Need to know how to write recursive functions
    Implement compare' -> (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 for Int, not [Int].
Answer

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.

1
2
3
4
5
6
7
8
9
-- .hs module
compare' cmp a b = cmpPair $ zip a b where
                     cmpPair (pair:pairs)
                     | null pairs = cmp (fst pair) (snd pair)
                     | fst pair == snd pair = cmpPair pairs
                     | cmp (fst pair) (snd pair) = True
                     | otherwise = False
-- ghci
compare' cmp a b = cmpPair $ zip a b where cmpPair (pair:pairs) | null pairs = cmp (fst pair) (snd pair) | fst pair == snd pair = cmpPair pairs | cmp (fst pair) (snd pair) = True | otherwise = False