100 Days Of FP (6 Part Series)
The explicit teaching of thinking is no trivial task, but who said that the teaching of programming is? In our terminology, the more explicitly thinking is taught, the more of a scientist the programmer will become.
I'm always adding the quotes the book adds at the cover of each chapter but never mention anything about them. I really liked this one in particular. Programming is all about thinking. The more we learn to think the better programmers we'll be.
The list datatype in Haskell is defined like this:
data  a =  | a : [a]
There are a few things to point out there.
 Is both the type constructor as well as the data constructor for the empty list. The other constructor (
:), the infix operator called cons, takes a value of type
a and a list of type
[a] and evaluates to
[a]. The data type as a whole is a sum (
|) but the second constructor (
:) is a product. What
a : [a] does is adding
a to the front of the list.
As I already mentioned pattern matching is one of my favorite features of Haskell. And we can do quite some interesting things by pattern matching on lists.
head' :: [a] -> Maybe a head'  = Nothing head' (x : _ ) = Just x tail' :: [a] -> Maybe [a] tail'  = Nothing tail' (_ : xs) = Just xs
I wrote these versions that return the value wrapped in a maybe because
[a] doesn't guarantee that the list will have values. If we try the Prelude version of these functions on empty lists we get and error.
λ> head  *** Exception: Prelude.head: empty list λ> tail  *** Exception: Prelude.tail: empty list
One thing to mention about our
tail'. In case of calling it with a list that has one value, it will return
Just . I think it's fine, since it reflects what the tail of a list with one element is (
a : ). But if we'd want to only return lists with elements we could extend it like so.
tail' :: [a] -> Maybe [a] tail'  = Nothing tail' (_ : ) = Nothing tail' (_ : xs) = Just xs
To write a list of four elements using the constructor we'd have to do use the cons operator 4 times.
(1 : 2 : 3 : 4 : )
Luckily Haskell provides some syntactic sugar to make it easier, which resembles the one in many other languages.
[1, 2, 3, 4]
Another nice thing to work with lists that Haskell provides is the ranges syntax.
λ> [1..10] [1,2,3,4,5,6,7,8,9,10] λ> [2, 4..10] [2,4,6,8,10] λ> [1..] [1,2,3,4,5,6,7,8,9,10,11,12 ...] -- continues infinitely λ> [1, 5..] [1,5,9,13,17,21,25,29,33,37,41,45 ...] -- continues infinitely
Which are equivalent to.
λ> enumFromTo 1 10 [1,2,3,4,5,6,7,8,9,10] λ> enumFromThenTo 2 4 10 [2,4,6,8,10] λ> enumFrom 1 [1,2,3,4,5,6,7,8,9,10,11,12 ...] -- continues infinitely λ> enumFromThen 1 5 [1,5,9,13,17,21,25,29,33,37,41,45 ...] -- continues infinitely
All of these functions require the type being ranged, in other words an
Enum type class.
enumFromTo :: Enum a => a -> a -> [a] enumFromThenTo :: Enum a => a -> a -> a -> [a] enumFrom :: Enum a => a -> [a] enumFromThen :: Enum a => a -> a -> [a]
List comprehensions are a means of generating a new list from a list or lists. They come directly from the concept of set comprehensions in mathematics, including similar syntax. They must have at least one list, called the generator, that gives the input for the comprehension, that is, provides the set of items from which the new list will be constructed. They may have conditions to determine which elements are drawn from the list and/or functions applied to those elements.
Coming from a non-mathematical background (JS, PHP, C++, Go, .etc) this was one of the really new things for me.
[ x^2 | x <- [1..10]]
Give the definition we can guess that we are building a list of all the square numbers from the list of
[1..10]. Or at least I'd guess that because I already read the chapter 😂
λ> [ x^2 | x <- [1..10]] [1,4,9,16,25,36,49,64,81,100]
We can add predicates to ignore certain items. The ones the predicate returns
False for, naturally. For example, we can decide to keep only the numbers divisible by 3.
λ> [x^2 | x <- [1..10], rem x 3 == 0] [9,36,81]
List comprehensions can have multiple generators.
λ> [x^y | x <- [1..5], y <- [2, 3]] [1,1,4,8,9,27,16,64,25,125] λ> [(x, y) | x <- [1..5], y <- [2, 3]] [(1,2),(1,3),(2,2),(2,3),(3,2),(3,3),(4,2),(4,3),(5,2),(5,3)]
Notice that the rightmost generator is exhausted first, then the second one and so on.
Lists are a recursive series of cons cells
a : [a] terminated by the empty list
. Now, it'd be great to find a way to visualize that.
In Haskell we say that some data structures (lists, sequences and trees) have a spine, the connective structure that ties the collection of values together. In lists it's the recursive cons (
1 : 2 : 3 :  or 1 : (2 : (3 : ))
There's a problem with this
1 : 2 : 3 :  representation, it makes it look like
1 exists before the cons cell but actually it contains the two values. Looking more like the following.
: / \ 1 : / \ 2 : / \ 3 
Because of this and the way nonstrict evaluation works, you can evaluate cons cells independently of what they contain. It is possible to evaluate only the spine of the list without evaluating individual values. It is also possible to evaluate only part of the spine of a list and not the rest of it.
Evaluation of a list goes down the spine, while construction goes up. But nothing is evaluated until it is needed to be.
As we said, the spine is the recursive series of cons operators (
:). And in here the
_ would be the non evaluated values.
: <------| / \ | _ : <----| This is the "spine" / \ | _ : <--| / \ _ 
:sprint in GHCi we can see what is evaluated and what isn't.
λ> ls = [1..5] :: [Int] λ> :sprint ls ls = _
ls hasn't been evaluated yet (as
λ> take 1 ls  λ> :sprint ls ls = 1 : _
Now we evaluated the first cons cell and it's first value. Let's take 2 values.
λ> take 2 ls [1, 2] λ> :sprint ls ls = 1 : 2 : _
We can continue like that until the end. We can also evaluate the whole spine with
λ> length ls 5 λ> :sprint ls ls = [1,2,3,4,5]
Wait but I said the spine only 🤔 This is some quirk of GHCi. But we can prove it's only the spine by checking a list of bottom ⊥ (i.e.
λ> undefined *** Exception: Prelude.undefined CallStack (from HasCallStack): error, called at libraries/base/GHC/Err.hs:78:14 in base:GHC.Err undefined, called at <interactive>:1:1 in interactive:Ghci1
As we can see it throws an exception when evaluated. But ...
λ> ls = [undefined, undefined] λ> :sprint ls ls = _ λ> length ls 2 λ> :sprint ls ls = [_,_]
As we can see Haskell only evaluates what it needs and nothing else. The book extends on this a bit more and explains the concepts of normal form and weak head normal form. But I'll get back to those in more depth in the chapter of nonstrictness.
We can use
fmap to transform a list of values, by applying a function to each element and then returning the new list.
map :: (a -> b) -> [a] -> [b] fmap :: Functor f => (a -> b) -> f a -> f b
fmap is the generalized version of
map that works for Functors. List is one of them. More on Functors in a following chapter.
λ> fmap (+1) [1, 2, 3, 4] [2,3,4,5]
This is how it's defined in
map :: (a -> b) -> [a] -> [b] map _  =  map f (a:as) = f a : map f as
By adding some parens to the type definition we can make it more explicit what map really allows us to do. Basically lifting our function
a -> b to work in lists.
(a -> b) -> ([a] -> [b]) ( a -> b ) ([a] -> [b])
map is not the only function we can use on lists. We can also filter certain values out of a list when they don't fulfill a predicate.
λ> even 10 True λ> even 9 False λ> filter even [1..10] [2,4,6,8,10]
filter is defined.
filter :: (a -> Bool) -> [a] -> [a] filter _  =  filter pred (x:xs) | pred x = x : filter pred xs | otherwise = filter pred xs
Zipping lists together is a means of combining values from multiple lists into a single list.
λ> :t zip zip :: [a] -> [b] -> [(a, b)] λ> zip "abc" "cde" [('a','c'),('b','d'),('c','e')] λ> zip "abc" "cdefghi" [('a','c'),('b','d'),('c','e')] λ> zip "abcdefghi" "jkl" [('a','j'),('b','k'),('c','l')]
zip returns the length of the shortests list.
We can also
λ> :t unzip unzip :: [(a, b)] -> ([a], [b]) λ> unzip [(1,'a'), (2, 'b'), (3, 'c')] ([1,2,3],"abc")
zipWith to combine two lists.
λ> :t zipWith zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] λ> zipWith (+) [1,2,3] [1,2,3] [2,4,6] λ> zipWith (+) [1,2,3] [1,2,3] [2,4,6] λ> zipWith (,) [1,2,3] [1,2,3] [(1,1),(2,2),(3,3)]
With lists we start to see the declarative patterns of functional programming. And how the same functions we can use for plain values can be used for lists as well with higher order functions like
Thanks to Haskell's laziness (nonstrict evaluation) it will only evaluate what it needs and no more.
λ> ls = [1,2,3,4,5,6,7,undefined] λ> filter even ls [2,4,6*** Exception: Prelude.undefined λ> take 2 $ zip "abcdefg" $ map (*2) $ filter even ls [('a',4),('b',8)]
Although it's clear in this example, it has many more implications that I'm yet to understand or even discover and I look forward to learn about that.