A list is a data structure used to store multiple homogeneous values.
Lists are also used as an infinite series of values, usually generated by a function, which allows them to act as a stream datatype.
The list datatype is defined as:
data [] a = [] | a : [a]
-- [1] [2][3] [4] [5] [6]
[][][a]The [] data constructor is a nullary constructor because it takes no arguments.
The second data constructor, has arguments. (:) is an infix operator usually called 'cons' which is short for constructs. Here, cons takes a value of type a and a list of type [a] and evaluates to [a].
The list datatype is a sum type because it is either an empty list or a single value with more list.
We can pattern match on data constructors for lists just like we do with data constructors.
We can match on the first argument to the infix (:) constructor:
Prelude> let myHead (x : _) = x -- returns first argument given
Prelude> :t myHead
myHead :: [t] -> t
Prelude> myHead [1, 2, 3]
1
We could rewrite this using Maybe which I will discuss more in future articles:
safeHead :: [a] -> Maybe [a]
safeHead [] = Nothing
safeHead ([]:x) = Nothing
safeHead (xs:_) = Just xs
Prelude> [1, 2, 3] ++ [4] -- write this
[1, 2, 3, 4]
Prelude> (1 : 2 : 3 : []) ++ 4 : [] -- not this
[1,2,3,4]
One of the most simple ways to construct lists is with ranges.
Prelude> [1..10]
[1,2,3,4,5,6,7,8,9,10]
Prelude> enumFromTo 1 10
[1,2,3,4,5,6,7,8,9,10]
Prelude> [1,2..10]
[1,2,3,4,5,6,7,8,9,10]
Prelude> enumFromThenTo 1 2 10
[1,2,3,4,5,6,7,8,9,10]
Prelude> [2,4..10]
[2,4,6,8,10]
Prelude> enumFromThenTo 2 4 10
[2,4,6,8,10]
Prelude> ['a'..'c']
"abc"
There are some useful functions for extracting portions of lists:
take :: Int -> [a] -> [a] -- takes the specified number of elements out of a list and returns a list
drop :: Int -> [a] -> [a] -- drops the specified number of elements off the beginning of the list
splitAt :: Int -> [a] -> ([a], [a]) -- cuts a list into two parts at the element specified byt the Int and makes a tuple
Prelude> take 3 [1..10]
[1,2,3]
Prelude> drop 5 [1..10]
[6,7,8,9,10]
Prelude> splitAt 5 [1..10]
([1,2,3,4,5],[6,7,8,9,10])
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.
Let's look at an example:
[ x^2 | x <- 1..10]
-- [1] [2] [ 3 ]
Output:
Prelude> [x^2 | x <- [1..10]]
[1,4,9,16,25,36,49,64,81,100]
Adding Predicates
List comprehensions can optionally take predicates that limit the elements drawn from the generator list.
Predicates must evaluate to Bool values.
Let's say we wanted the same output as the other function but with only the squares of odd numbers:
Prelude> [x^2 | x <- [1..10], odd x]
Lists are a recursive series of cons cells a : [a] terminated by the empty list [].
The spine of a data structure is the structure that ties the collection of values together.
In the case of a list, the spine is represented by the recursive cons (:) operators.
When a list in constructed, it starts from the bottom of the list up the spine, putting the first element in the empty list and so on.
A list isn't constructed until it is consumed.
Spines are Evaluated Independently of Values
Values in Haskell get reduced to weak head normal form by default.
Normal form means that the expression is fully evaluated.
Weak head normal form means that the expression is only evaluated as far as is necessary to reach a data constructor.
Example of both WHNF (weak head normal form) and NF (normal form):
(5, 7)
This example is in NF and is fully evaluated.
Anything that is in NF is also in WHNF because weak head is an expression which is evaluated up to at least the first data constructor.
NF exceeds that precedent by requiring that all subexpressions by fully evaluated.
(1, 2 + 5)
This example is in WHNF but not in NF.
This is because it is not fully evaluated.
One common thing that you may want to do is return a list with a function applied uniformly to all values within the list.
We can either use the map or fmap functions for this purpose.
map can only be used with [] whereas fmap is defined in a typeclass called Functor and can be applied to data other than lists.
Prelude> map (+2) [1, 2, 3]
[3,4,5]
Prelude> fmap (+1) [1,2,10]
[2,3,11]
Prelude> map fst [(1, 1), (2, 2), (3, 3)]
[1,2,3]
The filter function takes a function that returns a Bool value, maps that function over a list, and return a new list of all the values that met the condition.
Filtering builds a new list including values that meet the condition and excluding that ones that do not. It does not mutate the existing list.
Prelude> multiplesOf3Filter xs = filter $ \x -> x `mod` 3 == 0
Prelude> multiplesOf3Filter [1..30]
[3,6,9,12,15,18,21,24,27,30]
Prelude> removeArticlesFromSentence = filter (\x -> x `notElem` ["a", "the", "an"]) . words
Zipping lists together is a means of combining values from multiple lists into a single list.
zip, unzip, and zipWith are the important functions to know with zipping.
Prelude> zip [2, 3, 4] [1, 2, 3]
[(2, 1), (3, 2), (4, 3)]
Prelude> zip [2, 2] [1] -- the zip stops when one of the lists runs out of values
[(2, 1)]
Prelude> unzip [(2, 1)]
([2],[1])
Prelude> zipWith (*) [1, 2, 3] [10, 11, 12]
[10,22,36]
Data.List Documentation - http://hackage.haskell.org/package/base/docs/Data-List.html
Haskell Book - https://haskellbook.com/