**Liste**

Qui il prof Hal (rockz! 💥) dice “to do: put something here” ma poi continua con le liste; probabilmente manca solo un’intro.

**funzioni standard per le liste**

Recall that the definition of the built-in Haskell list datatype is equivalent to:

**data List a = Nil
| Cons a (List a)**

With the exception that ** Nil** is called

**and**

`[]`

**is called**

`Cons x xs`

**. This is simply to make pattern matching easier and code smaller. Let’s investigate how some of the standard list functions may be written. Consider**

`x:xs`

**. A definition is given below:**

`map`

**map _ [] = []
map f (x:xs) = f x : map f xs**

Here, the first line says that when you ** map** across an empty list, no matter what the function is, you get an empty list back. The second line says that when you map across a list with

**as the head and**

`x`

**as the tail, the result is**

`xs`

**applied to**

`f`

**consed onto the result of mapping**

`x`

**on**

`f`

**.**

`xs`

The ** filter** can be defined similarly:

**filter _ [] = []
filter p (x:xs) | p x = x : filter p xs
| otherwise = filter p xs**

How this works should be clear. For an empty list, we return an empty list. For a non empty list, we return the filter of the tail, perhaps with the head on the front, depending on whether it satisfies the predicate ** p** or not.

We can define ** foldr** as:

**foldr _ z [] = z
foldr f z (x:xs) = f x (foldr f z xs)**

Here, the best interpretation is that we are replacing the empty list (** []**) with a particular value and the list constructor (

**) with some function. On the first line, we can see the replacement of**

`:`

**for**

`[]`

**. Using backquotes to make**

`z`

**infix, we can write the second line as:**

`f`

`foldr f z (x:xs) = x `f` (foldr f z xs)`

From this, we can directly see how ** :** is being replaced by

**.**

`f`

Finally, ** foldl**:

**foldl _ z [] = z
foldl f z (x:xs) = foldl f (f z x) xs**

This is slightly more complicated. Remember, ** z** can be thought of as the current state. So if we’re folding across a list which is empty, we simply return the current state. On the other hand, if the list is not empty, it’s of the form

**. In this case, we get a new state by appling**

`x:xs`

**to the current state**

`f`

**and the current list element**

`z`

**and then recursively call**

`x`

**on**

`foldl`

**with this new state.**

`xs`

There is another class of functions: the ** zip** and

**functions, which respectively take multiple lists and make one or take one lists and split them apart. For instance,**

`unzip`

**does the following:**

`zip`

`Prelude> `**zip "hello" [1,2,3,4,5]**
[('h',1),('e',2),('l',3),('l',4),('o',5)]

Basically, it pairs the first elements of both lists and makes that the first element of the new list. It then pairs the second elements of both lists and makes that the second element, etc. What if the lists have unequal length? It simply stops when the shorter one stops. A reasonable definition for ** zip** is:

**zip [] _ = []
zip _ [] = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys**

The ** unzip** function does the opposite. It takes a zipped list and returns the two “original” lists:

`Prelude> `**unzip [('f',1),('o',2),('o',3)]**
("foo",[1,2,3])

There are a whole slew of ** zip** and

**functions, named**

`unzip`

**,**

`zip3`

**,**

`unzip3`

**,**

`zip4`

**and so on; the …3 functions use triples instead of pairs; the …4 functions use 4-tuples, etc.**

`unzip4`

Finally, the function ** take** takes an integer

**and a list and returns the first**

`n`

**elements off the list. Correspondingly,**

`n`

**takes an integer**

`drop`

**and a list and returns the result of throwing away the first**

`n`

**elements off the list. Neither of these functions produces an error; if**

`n`

**is too large, they both will just return shorter lists.**

`n`

**list comprehensions**

There is some syntactic sugar for dealing with lists whose elements are members of the ** Enum** class (see the section on Instances [qui]), such as

**or**

`Int`

**. If we want to create a list of all the elements from 1 to 10, we can simply write:**

`Char`

`Prelude> `**[1..10]**
[1,2,3,4,5,6,7,8,9,10]

We can also introduce an amount to step by:

`Prelude> `**[1,3..10]**
[1,3,5,7,9]
Prelude> **[1,4..10]**
[1,4,7,10]

These expressions are short hand for ** enumFromTo** and

**, respectively. Of course, you don’t need to specify an upper bound. Try the following (but be ready to hit**

`enumFromThenTo`

**to stop the computation!):**

`Control+C`

`Prelude> `**[1..]**
[1,2,3,4,5,6,7,8,9,10,11,12{Interrupted!}

è velocissimissimo, troppo.

Probably yours printed a few thousand more elements than this. As we said before, Haskell is lazy. That means that a list of all numbers from 1 on is perfectly well formed and that’s exactly what this list is. Of course, if you attempt to print the list (which we’re implicitly doing by typing it in the interpreter), it won’t halt. But if we only evaluate an initial segment of this list, we’re fine:

`Prelude> `**take 3 [1..]**
[1,2,3]
Prelude> **take 3 (drop 5 [1..])**
[6,7,8]

This comes in useful if, say, we want to assign an ** ID** to each element in a list. Without laziness we’d have to write something like this:

**assignID :: [a] -> [(a,Int)]
assignID l = zip l [1..length l]**

Which means that the list will be traversed twice. However, because of laziness, we can simply write:

`assignID l = zip l [1..]`

And we’ll get exactly what we want. We can see that this works:

`Prelude> `**assignID l = zip l [1..]**
Prelude> **assignID "hello"**
[('h',1),('e',2),('l',3),('l',4),('o',5)]

Finally, there is some useful syntactic sugar for ** map** and

**, based on standard set-notation in mathematics. In math, we would write something like**

`filter`

to mean the set of all values of ** f** when applied to elements of

**which satisfy**

`s`

**. This is equivalent to the Haskell statement**

`p`

**. However, we can also use more math-like notation and write**

`map f (filter p s)`

**. While in math the ordering of the statements on the side after the pipe is free, it is not so in Haskell. We could not have put**

`[f x | x <- s, p x]`

**before**

`p x`

**otherwise the compiler wouldn’t know yet what**

`x <- s`

**was. We can use this to do simple string processing. Suppose we want to take a string, keep only the uppercase letters and convert those to lowercase. We could do this in either of the following two equivalent ways:**

`x`

`Prelude> `**import Data.Char**
Prelude Data.Char> **map toLower (filter isUpper "Hello World")**
"hw"
Prelude Data.Char> **[toLower x | x <- "Hello World", isUpper x]**
"hw"

These two are equivalent, and, depending on the exact functions you’re using, one might be more readable than the other. There’s more you can do here, though. Suppose you want to create a list of pairs, one for each point between (0,0) and (5,7) below the diagonal. Doing this manually with lists and maps would be cumbersome and possibly difficult to read. It couldn’t be easier than with list comprehensions:

`Prelude> `**[(x,y) | x <- [1..5], y <- [x..7]]**
[(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(2,2),(2,3),(2,4),(2,5),(2,6),
(2,7),(3,3),(3,4),(3,5),(3,6),(3,7),(4,4),(4,5),(4,6),(4,7),(5,5),(5,6),(5,7)]

sì, sono andato a capo.

If you reverse the order of the ** x <-** and

**clauses, the order in which the space is traversed will be reversed (of course, in that case,**

`y <-`

**could no longer depend on**

`y`

**and you would need to make**

`x`

**depend on**

`x`

**but this is trivial).**

`y`

👽