Haskell – 171 – Sintassi avanzata – 8

Continuo da qui, copio qui.

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 Cons x xs is called 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 map. A definition is given below:

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 x as the head and xs as the tail, the result is f applied to x consed onto the result of mapping f on 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 z. Using backquotes to make f infix, we can write the second line as:

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 x:xs. In this case, we get a new state by appling f to the current state z and the current list element x and then recursively call foldl on xs with this new state.

There is another class of functions: the zip and unzip functions, which respectively take multiple lists and make one or take one lists and split them apart. For instance, zip does the following:

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 unzip functions, named zip3, unzip3, zip4, unzip4 and so on; the …3 functions use triples instead of pairs; the …4 functions use 4-tuples, etc.

Finally, the function take takes an integer n and a list and returns the first n elements off the list. Correspondingly, drop takes an integer n 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.

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 Int or Char. If we want to create a list of all the elements from 1 to 10, we can simply write:

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 enumFromThenTo, respectively. Of course, you don’t need to specify an upper bound. Try the following (but be ready to hit Control+C to stop the computation!):

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 filter, based on standard set-notation in mathematics. In math, we would write something like

to mean the set of all values of f when applied to elements of s which satisfy p. This is equivalent to the Haskell statement map f (filter p s). However, we can also use more math-like notation and write [f x | x <- s, p x]. 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 p x before x <- s otherwise the compiler wouldn’t know yet what x 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:

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 y <- clauses, the order in which the space is traversed will be reversed (of course, in that case, y could no longer depend on x and you would need to make x depend on y but this is trivial).

👽

Posta un commento o usa questo indirizzo per il trackback.

Trackback

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: