## Haskell – 16 – ricorsione – 2

Continuo da qui, copio qui, scrollare fino a “Recursion and Lists”.

Ricorsione e liste
We can not only use recursion to calculate numbers, but also to build lists: A simple example of such a recursive function is `repeatN`, which produces a list that contains a given item `n` times; i.e., has type

`repeatN :: Int -> a -> [a]`

To find a suitable definition for the function, we first consider what an appropriate base case might look like. Let us assume that we want the function to work for zero repetitions. Then, the expression `repeatN 0 x` would have to return an empty list, which fully specifies the base case.

repN.hs

``````repeatN :: Int -> a -> [a]

repeatN 0 x  = []
repeatN n x  = x : repeatN (n - 1) x``````
``````Prelude> :l repN
[1 of 1] Compiling Main             ( repN.hs, interpreted )
*Main> repeatN 0 "j"
[]
*Main> repeatN 8 "j"
["j","j","j","j","j","j","j","j"]``````

Given the material that we covered so far, it should be relatively straightforward to write a function that, when given a string, produces a list containing all of the possible suffixes of that string. For example, we would have

`suffixes "Hello" ⇒ ["Hello", "ello", "llo", "lo", "o"]`

The base case is when we have an empty string; then, we have no suffix, so we return the empty list:

`suffixes "" = []`

On the other hand, given

`suffixes "ello" ⇒ ["ello", "llo", "lo", "o"]`

we only need to add the string `Hello` at the front of the result to get the value of `suffixes Hello`. Moreover, as

`tail Hello ⇒ ello`

we arrive at the following definition:

suff.hs

``````suffixes :: String -> [String]

suffixes ""  = []
suffixes str = str : suffixes (tail str)``````
``````*Main> :l suff
[1 of 1] Compiling Main             ( suff.hs, interpreted )
*Main> suffixes "Hello"
["Hello","ello","llo","lo","o"]``````

In other words, after adding the current string `str`, we only need the suffixes of tail `str`.

Note that we can build lists recursively using only the empty list `[]` and the list forming operator (`:`). As these two suffice to build any list, they are regarded as the basic list forming constructors. In fact, they are usually called nil and cons, respectively. (The word “nil” actually stands for “Not In List” and “cons” is an abbreviation for “(list) constructor”. Già sentite, chissà da dove vengono? uh! Lisp 😁)

Liste come strutture ricorsive
All lists are constructed from nil and cons, where the following equality illustrates the correspondence between the square bracket and the nil/cons notation:

`[x1, x2,... , xn] = (x1 : (x2 : ...: (xn : [])...)`

Due to the repeated occurrence of cons, the right hand side exposes the recursive structure of lists. For each element xi in a list, we have one cons operator including this element into the list. Finally, each list is terminated by nil. This representation not only makes the recursive nature of lists explicit, but it is, in fact, the original representation of lists. The closed `[x1, x2,... , xn]` notation is only a convenient shorthand.

Qui davvero devo richiamare l’attenzione sul mio logo

Pattern matching in liste
The nil and cons operators are so elementary that we not only use them to construct lists, but also to decompose them; much as we did with pattern matching to decompose tuples in this definition of `fst`:

`fst :: (a, b) -> a`
`fst (x, y) = x`

In a similar manner, we use pattern matching to decompose lists into their first element and the rest of the list; i.e., into the two components joined together by cons. In fact, this is exactly what the two functions `head` and `tail` do to extract the first element and the remaining elements from a list:

`head :: [a] -> a`
`head (x:xs) = x`

`tail :: [a] -> [a]`
`tail (x:xs) = xs`

In other words, they yield the two values that are used to compose a list using the cons operator. Thus, for every non-empty list `xs`, we have the equality:

`xs = head xs : tail xs`

Therefore, the first component passed to cons is often called the head of the new list and the second component the tail.

In Fundamentals, we discussed that `head` and `tail` are partial functions as they lack a pattern matching the empty list. If we want to define a total function over lists with pattern matching, we have to specify at least two cases, one for the case where the input is an empty list and a second for the case where it is not empty; i.e., can be regarded as being constructed by a cons operator. The following function (also included in the `Prelude`), which checks whether a given list is empty, covers both cases:

`null :: [a] -> Bool`
`null [] = True`
`null (x:xs) = False`

``````*Main> null ""
True
*Main> null "Juhan"
False``````

Mappare: applicare un’operazione a ogni elemento di una lista
Combining pattern matching with recursion, we can traverse a list from beginning to end. Let’s say we have a list of numerals and want to compute the square of each element and return the resulting squared numbers as a new list:

`allSquares [x1, x2,... , xn] = [x1 * x1, x2 * x2, ... , xn * xn]`

For the base case, that is, empty list, we just return the empty list. If the list consists of a `head x` and a `tail xs` (pronounced: xes, as in boxes), we build a new list, with `x * x` as `head`, and the result of the recursive call `allSquares xs` as `tail`:

allSq.hs

``````allSquares :: Num a => [a] -> [a]

allSquares []       = []
allSquares (x : xs) = x * x : allSquares xs``````
``````*Main> :l allSq
[1 of 1] Compiling Main             ( allSq.hs, interpreted )
*Main> allSquares [1, 2, 3, 4, 5]
[1,4,9,16,25]``````

With the same list traversal pattern, we can define a function `allToUpper` which converts a string to upper case.

`allToUpper "can you hear me now? ⇒ "CAN YOU HEAR ME NOW?"`

To do so, we use a function defined in the standard module `Data.Char` called `toUpper :: Char -> Char`, which converts a lower case letter to an uppercase letter and leaves all other characters as they are:

allUp.hs

``````import Data.Char

allToUpper :: String -> String

allToUpper []                 = []
allToUpper (chr : restString) = toUpper chr : allToUpper restString``````
``````*Main> :l allUp
[1 of 1] Compiling Main             ( allUp.hs, interpreted )
*Main> allToUpper "Juhan was here"
"JUHAN WAS HERE"``````

Per chi vuole di là c’è il video.

Apart from the names of the functions and variables, and that we have to `import` the module `Data.Char`, the functions `allSquares` and `allToUpper` are almost identical — both follow the pattern

`recursiveFunction [] = []`
`recursiveFunction (x : xs) = doSomethingWith x : recursiveFunction xs`

Such functions can get additional arguments than the list as parameter. For example, re-using the definition `ColourPoint` from Fundamentals, we might define function that, given a `point :: ColourPoint` together with a list of points `points :: [ColourPoint]`, calculates the distance of each point in `points` to `point`:

``````distancesFromPoint :: ColourPoint -> [ColourPoint] -> [Float]

distancesFromPoint point [] = []
distancesFromPoint point (p : ps) = distance point p : distancesFromPoint point ps``````

This function still follows the same pattern of recursive list traversal as do `allSquares` and `allToUpper`.

🤢

Annunci
Posta un commento o usa questo indirizzo per il trackback.