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 )
Ok, 1 module loaded.
*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 )
Ok, 1 module loaded.
*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 )
Ok, 1 module loaded.
*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 )
Ok, 1 module loaded.
*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
Post a comment or leave a trackback: Trackback URL.

Trackbacks

Rispondi

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

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. 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 )

Google+ photo

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

Connessione a %s...

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