Category Archives: Haskell

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

Haskell – 15 – ricorsione – 1

Continuo da qui, copio qui.

The functions that we considered so far only used a fixed number of elementary operations. Even

distance :: ColourPoint -> ColourPoint -> Float
distance (x1, y1, colour1) (x2, y2, colour2) 
  = sqrt (fromIntegral (dx * dx + dy * dy))
  where
    dx = x2 - x1
    dy = y2 - y1

needs exactly one addition, two subtractions, two multiplications, the invocation of fromIntegral, and one square root — which makes seven operations. If conditional expressions or guards are used, the number of operations may vary, but we can still place an upper limit on the number of operations (independently of the input passed to the function).

However, many problems cannot be solved by functions limited in this way; indeed, some functions —depending on the input— have to perform an arbitrarily large number of operations. In the following, we look at a programming technique known as recursion as the fundamental mechanism to implementing such functions in Haskell.

Ricorsività con numeri
Nota per me: affronta l’argomento dall’inizio dell’inizio ma si sa che sono niubbo 😊

Consider the function natSum, which computes the sum of all natural numbers up to a limit, or the Prelude function product, which computes the product of all of the elements of an integer list:

natSum n ⇒ n + (n-1) + ⋯ + 2 + 1 + 0

product [x1, x2,... , xn] ⇒ x1 * x2 * ... * xn

The above are not actual function definitions, since the notation “…” is not valid Haskell. However, they illustrate the meaning of the two functions in reasonably formal terms. From this specification of the meaning, we see that both functions require n operations to compute their result. Thus, we can make two important observations:

  • The number of operations depends on the input.
  • A certain computation (or more generally, a set of operations) is repeatedly used.

It is this input-dependent repetition that we will implement by recursion

Calcolare n + ... + 2 + 1 + 0
Let us start with the simplest case: recursion over the natural numbers. How can we define the function natSum :: Num a => a -> a, which sums up all natural numbers from zero up to a given number n? It should behave as natSum n = n + ... + 1 + 0 but how can we substitute the ellipsis by working program code?

To get an idea of what we would like to happen, consider the following rules describing the computations to be performed by natSum for input values up to 5:

natSum 0 =                     0
natSum 1 =                 1 + 0
natSum 2 =             2 + 1 + 0
natSum 3 =         3 + 2 + 1 + 0
natSum 4 =     4 + 3 + 2 + 1 + 0
natSum 5 = 5 + 4 + 3 + 2 + 1 + 0

The above are legal Haskell definitions, but obviously, we would need an unbounded number of definitions to define natSum for every possible input. There is, however, an observation that comes to our rescue: each of the above equations contains computations that already appear in the previous equations. For example, for natSum 5, we have to evaluate 0 + 1 + 2 + 3 + 4 + 5, but the subcomputation 0 + 1 + 2 + 3 + 4 already appears in natSum 4. This seems like good news, as it allows us to reuse earlier equations for later ones. In other words, we could redefine natSum 5 as

natSum 5 = 5 + natSum 4

In fact, except for the first equation, we can systematically reuse the immediately preceding equation:

natSum 0 = 0
natSum 1 = 1 + natSum 0
natSum 2 = 2 + natSum 1 
natSum 3 = 3 + natSum 2 
natSum 4 = 4 + natSum 3 
natSum 5 = 5 + natSum 4 
...

Interestingly, all equations —except for the first one— now look exactly the same; they just use different values. This seems like an ideal situation to once more apply the trick that we already used when we introduced function definitions, i.e., we use abstraction to replace concrete values by variables and, in this way, we distill a repeating pattern out of the above equations. The repeating pattern is

natSum n = n + natSum m

where we know that m always equals n - 1. In other words, given the two rules

natSum 0 = 0
natSum n = n + natSum (n - 1)

we seem to have captured the essence of natSum. In natural language, we could describe this essence as follows:

The sum of the natural numbers from 0 to 0 is 0 (first case). The sum of the natural numbers from 0 to n can be obtained by computing the sum of the natural numbers from 0 to n − 1, and then, adding n (second case).

This sounds sensible; indeed, it is sufficient to compute the result of natSum for every case. For example, let us look at the stepwise evaluation of one application of natSum:

natSum 5  ⇒ 5 + natSum (5 - 1)
          ⇒ 5 + natSum 4
          ⇒ 5 + (4 + natSum (4 - 1))
          ⇒ 5 + (4 + natSum 3)
          ⇒ 5 + (4 + (3 + natSum (3 - 1)))
          ⇒ 5 + (4 + (3 + natSum 2))
          ⇒ 5 + (4 + (3 + (2 + natSum (2 - 1))))
          ⇒ 5 + (4 + (3 + (2 + natSum 1)))
          ⇒ 5 + (4 + (3 + (2 + (1 + natSum (1 - 1)))))
          ⇒ 5 + (4 + (3 + (2 + (1 + natSum 0))))
          ⇒ 5 + (4 + (3 + (2 + (1 + 0))))
          ⇒ 15

This obviously works the way we intended it to work. The above definition of natSum is called recursive, because natSum itself is used in the definition of natSum — i.e., a recursive function is a function that makes use of itself in its definition.

Recursive function definitions have at least two cases: the base case and the recursive case (or stepping case). The base case specifies what to do in the simplest form of input (where the function stops calling itself), whereas the stepping case includes the recursive use of the function by itself:

natSum :: Num a => a -> a
natSum 0  = 0                    -- base case
natSum n  = n + natSum (n - 1)   -- recursive/stepping case

Later, we will encounter recursive functions with more than one base case and/or more than one recursive case — but there will always be at least one of each kind.

An alternative way of writing the recursive definition of natSum would be

natSum :: Num a => a -> a
natSum n = if n == 0 
              then 0 
              else n + natSum (n - 1)

It contains only one equation and makes the case distinction explicit through a conditional.

A question that might come up during the definition of natSum is, what happens if we call this function with an argument that causes the recursive case to move away from, rather than towards the base case. For example, what does natSum (-1) result in? As the recursive case is applicable, the argument will be reduced to -2, -3, and so on, which means that we enter an infinite computation. In other words, natSum is not defined for arguments smaller than 0.

This is another instance of the concept of partial functions, which we discussed here. However, here the problem is not simply a lack of an undefined input pattern, but that the function fails to terminate for some of the input values admitted by its type signature. To replace non-termination by a proper runtime error, we can use the previously discussed error function:

natSum :: (Num a, Ord a) => a -> a
natSum 0             = 0
natSum n | n > 0     = n + natSum (n - 1) 
         | otherwise = error "natSum: Input value too small!"

Volendo di là c’è il video.

🤢

Haskell – 14 – elementi fondamentali – 8

Continuo da qui, copio qui, scrollare fino a “Exercises”.

Resta da fare un ultimo esercizio, ne approfitto per qualche considerazione personale.

5. Implement division on Int, divide :: Int -> Int -> Int using the list functions described in this section. Hint: first, write a function that returns all the multiples of a given number up to a specific limit.

divide 5 10 ⇒ 2
divide 5 8 ⇒ 1
divide 3 10 ⇒ 3

Non sono ancora abituato a Haskell, ho iniziato trascurando il suggerimento, così:

Prelude> 10 / 3
3.3333333333333335
Prelude> round 10 / 3

:2:1: error:
    • Ambiguous type variable ‘a0’ arising from a use of ‘print’
      prevents the constraint ‘(Show a0)’ from being solved.
      Probable fix: use a type annotation to specify what ‘a0’ should be.
      These potential instances exist:
        instance Show Ordering -- Defined in ‘GHC.Show’
        instance Show Integer -- Defined in ‘GHC.Show’
        instance Show a => Show (Maybe a) -- Defined in ‘GHC.Show’
        ...plus 22 others
        ...plus 12 instances involving out-of-scope types
        (use -fprint-potential-instances to see them all)
    • In a stmt of an interactive GHCi command: print it
Prelude> round (10 / 3)
3

OK, le parentesi. Provo a mettere tutto nel file

dr.hs

dr :: Int -> Int -> Int

dr x y = round (x / y)
Prelude> :l dr
[1 of 1] Compiling Main             ( dr.hs, interpreted )

dr.hs:3:10: error:
    • No instance for (RealFrac Int) arising from a use of ‘round’
    • In the expression: round (x / y)
      In an equation for ‘dr’: dr x y = round (x / y)
  |
3 | dr x y = round (x / y)
  |          ^^^^^^^^^^^^^

dr.hs:3:17: error:
    • No instance for (Fractional Int) arising from a use of ‘/’
    • In the first argument of ‘round’, namely ‘(x / y)’
      In the expression: round (x / y)
      In an equation for ‘dr’: dr x y = round (x / y)
  |
3 | dr x y = round (x / y)
  |                 ^^^^^
Failed, 0 modules loaded.

No, ovvio che / non da Int, provo a eliminare la signature

drn.hs

dr x y = round (x / y)
Prelude> :l drn
[1 of 1] Compiling Main             ( drn.hs, interpreted )
Ok, 1 module loaded.
*Main> dr 10 3
3

OK, anche se non è quello richiesto e poi capita questo

*Main> dr 8 3
3

Si potrebbe cambiare round con floor e i conti tornerebbero. Anche se non è solo per Int.

Insomma, anche se spero ci sia un metodo più semplice do retta ai prof, ecco –dopo diversi tentativi, l’ho detto che sono niubbo:

Prelude> [3, 6..10]
[3,6,9]
Prelude> x=3
Prelude> y = 10
Prelude> [x, (2*x)..y]
[3,6,9]
Prelude> length [x, (2*x)..y]
3

Posso quindi costruire lo script

div.hs

divide :: Int -> Int -> Int

divide x y = length [x, (2*x)..y]
*Main> :l div
[1 of 1] Compiling Main             ( div.hs, interpreted )
Ok, 1 module loaded.
*Main> divide 5 10
2
*Main> divide 5 8
1
*Main> divide 3 10
3

😁 Fatto! era semplice, semplicissimissimo, bastava seguire quanto detto a lezione (cioè nei posts precedenti). Solo che –tentativo di giustificazione qui– da solo è più difficile, rischi di innamorarti acriticamente delle tue idee. E poi sono condizionato da altri linguaggi. Ma poi mi passa … probabilmente … forse 😊

🤢

Haskell – 13 – elementi fondamentali – 7

Continuo da qui, copio qui, scrollare fino a “Exercises”.

3. Define a function isLower :: Char -> Bool which returns True if a given character is a lower case letter. You can use the fact that characters are ordered, and for all lower case letters ch we have ′a′ ≤ ch and ch ≤ ′z′. Alternatively, you can use the fact that ['a'..'z'] evaluates to a list containing all lower case letters.

isl-1.hs

isLower :: Char -> Bool

isLower x = 'a' <= x && x <= 'z'
Prelude> :l isl-1
[1 of 1] Compiling Main             ( isl-1.hs, interpreted )
Ok, 1 module loaded.
*Main> isLower 'j'
True
*Main> isLower 'a'
True
*Main> isLower 'z'
True
*Main> isLower '0'
False
*Main> isLower 'T'
False

Io la modificherei in questo modo (sapete, vengo da lontano (Fortran)😊)

isl-2.hs

isLower :: Char -> Bool

isLower x = x >= 'a' && x <= 'z'
*Main> :l isl-2
[1 of 1] Compiling Main             ( isl-2.hs, interpreted )
Ok, 1 module loaded.
*Main> isLower 'j'
True
*Main> isLower 'T'
False
*Main> isLower '.'
False
*Main> isLower '~'
False

Ma ancora più sexy questa versione

isl-3.hs

isLower :: Char -> Bool

isLower x = elem x ['a'..'z']
*Main> :l isl-3
[1 of 1] Compiling Main             ( isl-3.hs, interpreted )
Ok, 1 module loaded.
*Main> isLower 'l'
True
*Main> isLower 'U'
False

4. Write a function mangle :: String -> String which removes the first letter of a word and attaches it at the end. If the string is empty, mangle should simply return an empty string:

mangle "Hello" ⇒ "elloH"
mangle "I" ⇒ "I"
mangle "" ⇒  ""

Non ci sto riuscendo. Uh! capito 😁, dopo diversi tentativi (che non racconto, già dimenticati)

mgl.hs

mangle :: String -> String

mangle x = if (length x <= 1) then x else tail x ++ [head x]
*Main> :l mgl
[1 of 1] Compiling Main             ( mgl.hs, interpreted )
Ok, 1 module loaded.
*Main> mangle "Hello"
"elloH"
*Main> mangle "I"
"I"
*Main> mangle ""
""

Personalmente preferisco scriverlo con le  guardie  guards:

mgl-g

mangle :: String -> String

mangle x | (length x <= 1) = x 
         | otherwise = tail x ++ [head x]

Resta da fare il 5. Prossimamente, forse 😊

🤢

Haskell – 12 – elementi fondamentali – 6

Continuo da qui, copio qui, scrollare fino a “Exercises”.

Esercizi
1. Write a function sort2 :: Ord a => a -> a -> (a, a) which accepts two Int values as arguments and returns them as a sorted pair, so that sort2 5 3 is equal to (3,5). How can you define the function using a conditional, how can you do it using guards?

es1-1.hs

sort2 :: Ord a => a -> a -> (a, a)
sort2 x y = if x >= y then (y, x) else (x, y)
Prelude> :l es1-1
[1 of 1] Compiling Main             ( es1-1.hs, interpreted )
Ok, 1 module loaded.
*Main> sort2 5 3
(3,5)
*Main> sort2 1 8
(1,8)

es1-2.hs

sort2 :: Ord a => a -> a -> (a, a)
sort2 x y | x >= y = (y, x) 
          | x < y  = (x, y)
*Main> :l es1-2
[1 of 1] Compiling Main             ( es1-2.hs, interpreted )
Ok, 1 module loaded.
*Main> sort2 5 3
(3,5)
*Main> sort2 1 8
(1,8)

2. Consider a function

almostEqual :: Eq a => (a, a) -> (a, a) -> Bool

which compares the values of two pairs. It returns True if both pairs contain the same values, regardless of the order. For example, almostEqual (3,4) (4,3) is True, but almostEqual (3,4) (3,5) is False. Which of the following definitions return the correct value? Which of the definitions would you consider good style? Why?

(The operator (&&) is logical ”and”, the operator (||) is logical ’or’, and (==) tests if two values are equal. The first two are of type Bool -> Bool -> Bool; the third is of type Eq a => a -> a -> Bool.)

almostEqual (x1, y1) (x2, y2)
  | (x1 == x2) && (y1 == y2) = True
  | (x1 == y2) && (y1 == x2) = True
  | otherwise                = False

almostEqual (x1, y1) (x2, y2)
  | (x1 == x2) = (y1 == y2) 
  | (x1 == y2) = (y1 == x2) 
  | otherwise  = False

almostEqual pair1 pair2 
  = (pair1 == pair2) || (swap pair1 == pair2)
  where 
    swap (x,y) = (y,x)

almostEqual pair1 pair2 
  = (pair1 == pair2) || (swap pair1 == swap pair2)
  where 
    swap (x,y) = (y,x)

almostEqual (x1, y1) (x2, y2) 
  = if (x1 == x2) 
      then
        if (y1 == y2) 
          then True
          else False
      else 
        if (x1 == y2) 
          then 
            if (x2 == y1)
              then True
              else False
          else False

La prima versione (es2-a.hs) è OK

es2-a.hs

almostEqual :: Eq a => (a, a) -> (a, a) -> Bool

almostEqual (x1, y1) (x2, y2)
  | (x1 == x2) && (y1 == y2) = True
  | (x1 == y2) && (y1 == x2) = True
  | otherwise                = False
*Main> :l es2-a
[1 of 1] Compiling Main             ( es2-a.hs, interpreted )
Ok, 1 module loaded.
*Main> almostEqual (3,4) (4,3)
True
*Main> almostEqual (3,4) (3,5)
False

La seconda (es2-b.hs) anche.

es2-b.hs

almostEqual :: Eq a => (a, a) -> (a, a) -> Bool

almostEqual (x1, y1) (x2, y2)
  | (x1 == x2) = (y1 == y2)
  | (x1 == y2) = (y1 == x2)
  | otherwise  = False
Prelude> :l es2-b
[1 of 1] Compiling Main             ( es2-b.hs, interpreted )
Ok, 1 module loaded.
*Main> almostEqual (3,4) (4,3)
True
*Main> almostEqual (3,4) (3,5)
False

perché ritorna il valore dato dall’operatore = se questo è True; se False ritorna la guard finale (otherwise). La prima è (forse) più chiara, la seconda (credo) più haskelliana. Anzi, ripensandoci la seconda è molto più bella.

La terza (es2-c.hs) è ancora più haskelliana, deriva dalla seconda:

es2-c.hs

almostEqual :: Eq a => (a, a) -> (a, a) -> Bool

almostEqual pair1 pair2
  = (pair1 == pair2) || (swap pair1 == pair2)
  where 
    swap (x,y) = (y,x)
*Main> :l es2-c
[1 of 1] Compiling Main             ( es2-c.hs, interpreted )
Ok, 1 module loaded.
*Main> almostEqual (3,4) (4,3)
True
*Main> almostEqual (3,4) (3,5)
False

la quarta (es2-d.hs) non è corretta per lo swap di entrambe le pair in quanto devo verificare se una è il rovescio dell’altra.

es2-d.hs

almostEqual :: Eq a => (a, a) -> (a, a) -> Bool

almostEqual pair1 pair2
  = (pair1 == pair2) || (swap pair1 == swap pair2)
  where 
    swap (x,y) = (y,x)

risultati non corretti

*Main> :l es2-d
[1 of 1] Compiling Main             ( es2-d.hs, interpreted )
Ok, 1 module loaded.
*Main> almostEqual (3,4) (4,3)
False
-- risultato NON corretto!!!
*Main> almostEqual (3,4) (3,5)
False
*Main> almostEqual (3,4) (3,4)
True

la quinta (es2-e.hs) è OK ma primitiva, sembra Python (o peggio)

es2-e.hs

almostEqual :: Eq a => (a, a) -> (a, a) -> Bool

almostEqual (x1, y1) (x2, y2) 
  = if (x1 == x2) 
      then
        if (y1 == y2) 
          then True
          else False
      else 
        if (x1 == y2) 
          then 
            if (x2 == y1)
              then True
              else False
          else False
*Main> :l es2-e
[1 of 1] Compiling Main             ( es2-e.hs, interpreted )
Ok, 1 module loaded.
*Main> almostEqual (3,4) (4,3)
True
*Main> almostEqual (3,4) (3,5)
False

Ci sono ancora 3 esercizi, per il prossimo post 😊

🤢

Haskell – 11 – elementi fondamentali – 5

Continuo da qui, copio qui, scrollare fino a “Lists versus tuples”.

Confronto liste – tuples
As lists and tuples are often confused, let us summarise the differences between them. Tuples have the following properties:

  • Fixed size, i.e., fixed number of components: the pair (1, 2) :: (Int, Int) and the triple (1, 2, 3) :: (Int, Int, Int) have different types.
  • Components may be of different type: (5, Hello) makes perfect sense.

In contrast, the following are the properties of lists:

  • Variable size, i.e., number of components may vary: [1, 2] :: [Int] and [1, 2, 3] :: [Int] have the same types.
  • Components must be of the same type: [5, Hello] is incorrect.

Stringhe come liste
Strings are in fact a particular form of lists in Haskell, which are defined as follows in the Prelude:

type String = [Char]

Hence, list operations work on strings. "Hello" !! 1   ⇒   'e' In fact, in Haskell, "Hello" is exactly the same as ['H', 'e', 'l', 'l', 'o']. This is very convenient, as we will see that there are many powerful list processing operations and these are directly available for string manipulation.

Hence, if we ask the Haskell system for the type of an expression that produces a list, it may report the type as either String or as [Char]. As these two types have been deemed equal by the above type definition, they may be used interchangeably

Funzioni parziali
Some list functions, such as length, may be applied to any list and always produce a meaningful result. In contrast, some other functions, such as head and tail, fail for some lists. For example, if we apply head to an empty list, we get a runtime error or runtime exception.

Prelude> head []
*** Exception: Prelude.head: empty list

The function head is defined by pattern matching using the same symmetry between list construction and list pattern matching as we discussed previously for tuples — i.e., it matches on the cons-operator (:):

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

When head gets applied to the empty list, there is simply no function equation that matches this case. We call such functions partial functions. Their definition ignores —or is invalid for— some of the input values admitted by the function’s type signature. We discussed that types represent sets of related values; hence, partial functions are functions that are only defined for a subset of the values included in their argument types. The opposite are total functions. Total functions, such as length, are defined for all values included in the sets represented by their argument types.

Partial functions are a common source of programming mistakes. Hence, good style dictates that the documentation of a partial function (e.g., as a comment preceding the function definition) includes a statement specifying the range of admissible input values (and specifies what happens if the function is incorrectly called with an argument that is outside of this range).

The Haskell Prelude includes the function

error :: String -> a

that always results in a runtime error using its argument as the error message — that is, we have

Prelude> error "encountered a fatal error"
*** Exception: encountered a fatal error

We can use error to customise the error message of a partial function. For example, the complete definition of head in the Haskell Prelude reads as follows:

head :: [a] -> a
head (x:_) = x
head []    = error "Prelude.head: empty list"

This is better than the default error message generated by the Haskell compiler, which includes the location of the failing function definition, but doesn’t specify the argument value that led to the failure.

Note the use of the underscore _ as the second argument of the cons-operator in the first equation. It represents a pattern matching position whose value is not used in the body of the function definition. It is better style than using a regular variable name, such as xs, as it immediately signals that the corresponding value goes unused. Instead of a plain underscore, we can also use variable names starting with an underscore character (here, for example _xs) to indicate that the value is not used.

Layout
Unlike in many other programming languages, formatting matters in Haskell. In other words, the correct use of indentation and newlines is crucial to avoid errors. This allows the language to do away with some of the noise that is introduced by some other languages to disambiguate the input — in particular, Haskell programs don’t need curly braces or semicolon to delimit blocks and statements.

Compare

foo x 
  = a + b
  where
    a = 1 + x
    b = 2

to

foo x 
  = a + b
  where
    a = 1 + x
b = 2

Both are legal programs. However, in the first one, the definition of b is part of the where binding and therefore local to foo whereas in the second program, the use of b is not restricted to foo.

An example of proper layout is the function distance that we discussed earlier:

distance :: ColourPoint -> ColourPoint -> Float
distance (x1, y1, colour1) (x2, y2, colour2) 
  = sqrt (fromIntegral (dx * dx + dy * dy))
  where
    dx = x2 - x1
    dy = y2 - y1

There are three layout rules that we have to follow to get syntactically correct programs:

  • All program code that belongs to a function definition has to be further to the right than the first character of that definition (i.e., the first character of the function name). In the case of distance, all code has to be further to the right than the column in which the character d of the function name distance is located.
  • Similarly, all code of a local definition in a where clause must be further to the right than the first character of the name of the variable defined by the binding.
  • All definitions within a where clause must be aligned — e.g., above the definitions of dx and dy start in the same column.

Alternatively, we can explicitly group the bindings of a where clause using curly braces, and separate the individual bindings by semicolons:

distance (x1, y1, colour1) (x2, y2, colour2) 
  = sqrt (fromIntegral (dx * dx + dy * dy))  
  where {dx = x2 - x1; dy = y2 - y1}

Inside the curly braces, we can format the code anyway we like, because the compiler can still figure out what belongs where. Nevertheless, while the following program is legal

distance (x1, y1, colour1) (x2, y2, colour2) 
  = sqrt (fromIntegral (dx * dx + dy * dy)) where {dx 
= x2 - 
x1; dy = y2 - y1}

it is hard to read and clearly pretty bad style. Seasoned Haskell programmers who prefer explicit bracketing align the braces and the semicolons at the beginning of each line (which looks rather strange to, say, a C-programmer, who is used to having semicolons at the end of the line):

distance (x1, y1, colour1) (x2, y2, colour2) 
  = sqrt (fromIntegral (dx * dx + dy * dy))  
  where 
    { dx = x2 - x1
    ; dy = y2 - y1
    }

Qui (di là) volendo c’è il video riassuntivo.

🤢

Haskell – 10 – elementi fondamentali – 4

Continuo da qui, copio qui, scrollare fino a “Lists: Many Values of a Single Type”.

Liste: più valori dello stesso tipo
Tuples provide the ability to bring together a fixed number of values of varying type. However, many applications, in addition, require the ability to manipulate compound types that may contain a varying number of elements of a single type. This is what lists are for.

We can create lists in a manner similar to pairs, by listing all components, separated by comma. The only difference is that we enclose these values in square brackets:

firstTenPrimes :: [Int]
firstTenPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Lists are a central data structure in Haskell, and the language offers a lot of convenient shortcuts. We don’t need to explicitly write every single element if our list elements are just a sequence of consecutive numbers — or in fact, any type whose values can be enumerated:

oneToTwenty :: [Int]
oneToTwenty = [1..20]

If the elements follow a simple pattern of the form [n, n + k, n + 2*k, n + 3*k ....,m] we simply write the first two numbers and the last one, and the compiler will figure out what the elements are:

-- return all positive odd numbers up to maxNumber
oddNumbers :: Int -> [Int]
oddNumbers maxNumber = [1, 3..maxNumber]

The length of the list returned by this function depends on the argument, unlike with the earlier addMul, where only the value, but not the number of values, depended on the input. For example, we have

Prelude> oddNumbers 10
[1,3,5,7,9]
Prelude> oddNumbers 15
[1,3,5,7,9,11,13,15]

The difference between tuples and lists can be seen by comparing their types, as in

(1, 2, "green") :: (Int, Int, String)

and

[1, 2, 3, 4] :: [Int]

The number of components is explicit in the type of a tuple, but not in the type of a list. As a consequence, the elements of tuples may be heterogeneous, whereas those of lists must be homogeneous.

Funzioni utili per le liste
Adding elements to the front of a list. The right-associative operator (:) adds another element to the front of an existing list:

(:) :: a -> [a] -> [a]

For example, we have

Prelude> "blue" : []
["blue"]
Prelude> "yellow" : ["red", "green", "blue"]
["yellow","red","green","blue"]
Prelude> "yellow" : "red" : "green" :"blue" : []
["yellow","red","green","blue"]

The operator : (pronounced cons) can only add elements at the front. So,

Prelude> ["red", "green", "blue"] : "yellow"

:11:28: error:
    • Couldn't match type ‘Char’ with ‘[[Char]]’
      Expected type: [[[Char]]]
        Actual type: [Char]
    • In the second argument of ‘(:)’, namely ‘"yellow"’
      In the expression: ["red", "green", "blue"] : "yellow"
      In an equation for ‘it’: it = ["red", "green", "blue"] : "yellow"

The cons-operator is another example of a polymorphic function, as it works on lists of any type. The only restriction is that the element we are adding is of the same type as the elements of the list we pass as the second argument:

(:) :: a -> [a] -> [a]

Joining two lists. We can join two lists together using the operator ++

(++) :: [a] -> [a] -> [a]

Just as the cons operator, it works on lists of any type, as long as the two lists have the same type of elements:

Prelude> [4, 2, 3] ++ [3, 1, 2, 7]
[4,2,3,3,1,2,7]
Prelude> [True] ++ [False, True]
[True,False,True]

You may remember this operator from the previous chapter, where we used it to join two strings to define

exclaim :: String -> String
exclaim sentence = sentence ++ "!"

This works, because strings are simply lists of characters in Haskell.

Extract the element at a specific index position out of a list. We can index into a list and extract an element using

(!!) :: [a] -> Int -> a

On lists of ints

Prelude> [0, 1, 2, 3] !! 2
2

or strings (lists of characters)

Prelude> "Hello" !! 4
'o'

As you can see, the index count starts at 0. If we apply the index operation to an index which is out of range for the given list, evaluation will raise an exception and we get an error message.

Split a list into its first element and the rest.
head :: [a] -> a
tail :: [a] -> [a]

Both functions require the input list to be non-empty, and if they are applied to an empty list, we get a runtime error.

Prelude> head [0, 1, 2, 3]
0
Prelude> tail [0, 1, 2, 3]
[1,2,3]
Prelude> head "mouse"
'm'
Prelude> tail "mouse"
"ouse"
Prelude> head ["mouse", "cat", "dog"]
"mouse"
Prelude> tail ["mouse", "cat", "dog"]
["cat","dog"]

Length of a list.
length :: [a] -> Int

For example, we have

Prelude> length [0, 1, 2, 3]
4
Prelude> length "mouse"
5
Prelude> length ["mouse", "cat", "dog"]
3

Check if an item is contained in a list. We can check if an item is element of a given list if its type is in the class Eq. This restriction is necessary because the implementation of this function needs to compare the items for equality.

elem :: Eq a => a -> [a] -> Bool

For example, we have

Prelude> elem 2 [0, 1, 2, 3]
True
Prelude> elem 5 [1, 2, 3, 4]
False
Prelude> elem 'o' "Hello"
True

Add up or multiply the elements of a list. We can calculate the maximum, minumum, sum, or the product of all the elements of a list with these functions.

maximum :: Ord a => [a] -> a
minimum :: Ord a => [a] -> a
sum     :: Num a => [a] -> a
product :: Num a => [a] -> a

For example, we get

Prelude> sum [0, 1, 2, 3]
6
Prelude> product [1, 2, 3, 4]
24

Given these functions, how can we add "yellow" at the end of ["red", "green", "blue"]? We can’t use : (cons), since it can only add elements at the start of a list. We need to use ++ as follows:

Prelude> ["red", "green", "blue"] ++ ["yellow"]
["red","green","blue","yellow"]

Note the list constructing brackets around "yellow". In effect, we wrap "yellow" into a singleton list, which we then append to the list ["red", "green", "blue"].

A questo punto di là c’è il solito video riassuntivo. Per chi vuole; io preferisco il testo scritto 😊

🤢

Haskell – 9 – elementi fondamentali – 3

Continuo da qui, copio qui, scrollare fino a “Tuples: Combining Different Data Items”.

Tuples: combinare elementi di dati diversi
So far, we have seen how to pass multiple values to a function, but not how a function can return more than one result value. We can achieve this by using tuples:

addMul :: Num a => a -> a -> (a, a)
addMul x y = (x + y, x * y)

A tuple combines multiple components (two integer values, in the above example) into one compound value. The compound value can be manipulated as a single entity and, in particular, be returned as a value from a function.

However, the construction of a compound value is only half of the story. We also need a method for decomposing such values. We achieve this by using a notation dual to that of tuple construction:

fst (x, y) = x
snd (x, y) = y

Note: Both fst and snd are already defined in the Prelude.

In the argument of fst, we do not use a variable to refer to the compound argument as a whole. Instead, we decompose the pair into its components x and y — this is also called decomposition by pattern matching.

Prelude> :l addMul
[1 of 1] Compiling Main             ( addMul.hs, interpreted )
Ok, 1 module loaded.
*Main> addMul 5 6
(11,30)
*Main> fst (addMul 5 6)
11
*Main> snd (addMul 5 6)
30

The combined use of addMul and fst behaves as follows:

fst (addMul 5 6) ⇒  fst (5 + 6,  5 * 6)
                 ⇒  fst (11,  30)
                 ⇒  11

The types of fst and snd. So far, we omitted the type annotations from the definitions of fst and snd. Generally, the Haskell system will automatically infer the types of definitions that lack a signature — however, it is good style to explicitly provide signatures. In all our previous definitions, the type was determined by the operations we applied to the arguments. For example max was restricted to work on types which are members of the type class Ord, since we needed the operator >=, which can only compare certain types of values. The functions fst and snd are different, though. We don’t actually apply any function or operation to x or y, so they could be values of any type. In fact, x and y don’t even have to have the same type. Hence, we can just use type variables to represent the types of x and y without having to add any type class restrictions:

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

snd :: (a, b) -> b
snd (x, y)  = y

Functions like fst and snd, which can handle arguments of any type are called (parametric) polymorphic functions.

Example: points. Tuples are not just useful to return multiple results, but also for the representation of data items that cannot be modeled by one primitive value alone. A useful example is given by the points in a 2-dimensional Cartesian coordinate system: they can be represented by a pair of integer values. To avoid having to write the less informative (Int, Int) whenever we denote the type of a point, we can introduce a new type name — similar to the introduction of names for repeatedly used values, which we discussed earlier

type Point = (Int, Int)

With this definition, we define some simple operations on points:

-- origin of the coordinate system
--
origin :: Point
origin  = (0, 0)

-- move a given point to the right
--
moveRight :: Point -> Int -> Point
moveRight (x, y) distance  = (x + distance, y)

-- move a given point to upwards
--
moveUp :: Point -> Int -> Point
moveUp (x, y) distance  = (x, y + distance)

Example: colour points. When we extend points to include a colour, another important property of tuples becomes obvious: tuple components may be of different types. Hence, if we denote colour values with a textual (string) representation, we have

-- we represent colours by strings
--
type Colour = String

-- new name for the type of colour points
--
type ColourPoint = (Int, Int, Colour)

which enables the following operations on colour points:

-- origin of the coordinate system in a given colour
--
origin :: Colour -> ColourPoint
origin colour  = (0, 0, colour)

-- move a colour point vertically and horizontally
--
move :: ColourPoint -> Int -> Int -> ColourPoint
move (x, y, colour) xDistance yDistance  
  = (x + xDistance, y + yDistance, colour)

-- compute the distance between two colour points
--
distance :: ColourPoint -> ColourPoint -> Float
distance (x1, y1, colour1) (x2, y2, colour2) 
  = sqrt (fromIntegral (dx * dx + dy * dy))
  where
    dx = x2 - x1
    dy = y2 - y1

Note how we use a where clause in the last definition to avoid repeating the expressions x2 - x1 and y2 - y1. The standard function fromIntegral converts any integral type to any other numeric type. Its signature is

fromIntegral :: (Integral a, Num b) => a -> b

Important symmetries in Haskell. If we compare the syntax of values and types of tuples, we see that they correspond. For example, consider

(10, 15, "green") :: (Int, Int, String)

If we replace the values 10, 15, and "green" with their respective types Int, Int, and String, we obtain the type of the tuple. Moreover, we have a correspondence between term construction and term decomposition (also called pattern matching). Consider,

startPoint = (0, 0, "black")
colourOfPoint (x, y, colour) = colour

If we replace the components in the tuple construction (0, 0, and "black") by variable names (in this case x, y, colour), we arrive at the pattern that can be used to decompose the corresponding tuple.

Nomi speciali per alcune tuples
The following table lists a number of tuple types and their names:

# Expression          	    Name
0 () 	                    Unit
1 n/a 	                    n/a
2 (x_1, x_2) 	            Pair
3 (x_1, x_2, x_3)           Triple
4 (x_1, x_2, x_3, x_4) 	    Quadruple
5 (x_1, x_2, x_3, x_4, x_5) Quintuple
     ⋮ 		
n (x_1,..., x_n)            n-tuple

🤢

Haskell – 8 – elementi fondamentali – 2

Continuo da qui, copio qui, scrollare fino a “Binders — Associating Names with Values or Functions”.

Binders – associare nomi con valori o funzioni
A binder binds a value to a name. The value can subsequently be referred to by that name. For example, the Prelude definition

pi :: Floating a => a
pi = 3.141592653589793

allows us to just write pi instead of spelling out 3.141592653589793. The type class Floating contains the types Float and Double (i.e., single and double precision floating point numbers).

We may use a previously introduced name in another function definition:

circleArea :: Floating a => a -> a
circleArea radius = pi * radius * radius

Sometimes, we need to introduce a new name, which will only be used within a function. In that case, we should use a local binding. For example,

circleArea' :: Floating a => a -> a
circleArea' diameter = pi * radius * radius
  where
    radius = diameter / 2.0       -- local binding

cioè calcola l’area dato il diametro 😊

The evaluation of this function proceeds as follows:

circleArea' 6.0 ⇒   pi * radius * radius where radius = 6.0 / 2.0

                ⇒   pi * radius * radius where radius = 3.0

                ⇒   pi * 3.0 * 3.0

                ⇒   pi * 9.0

                ⇒   3.141592653589793 * 9.0

                ⇒   28.2743

Pausa perché l’argomento successivo è lungo 😊

🤢

Haskell – 7 – elementi fondamentali – 1

Continuo da qui, copio qui.

The functions we defined so far were restricted to elementary operations, such as incrementing a number. In this chapter, we will discuss some slightly more advanced functions and survey elementary operations on lists.

I programmi sono composti da moduli
Usually, a program consists of a large number of function and type definitions. Obviously, putting them all into one single file is a bad idea. Modern programming languages therefore provide some means to structure the program by allowing to group related definitions into logical units which are stored in separate files. In Haskell, these units are called modules.

Let us have a look at the definition of a Haskell module, called Simple:

-- Example module
-- Gabriele Keller, August 2015
--
-- This is a simple example of a module definition

module Simple
where

-- calculates the arithmetic mean of two numbers
--
arithmetic_mean :: Fractional a => a -> a -> a
arithmetic_mean x y  = (x + y)  / 2

-- calculates the harmonic mean of two numbers
--
harmonic_mean :: Fractional a => a -> a -> a
harmonic_mean x y  = 2 * x * y / (x + y)

The module begins with a header: a comment containing a one line description of the module, the author and date of creation, and briefly describes the purpose of the module. (Note: The header is optional in that the compiler will not raise an error if it is missing.)

The first line of code starts with the keyword module, followed by the name of the module, the keyword where, and the definitions that belong to the module. Note that a module name, in contrast to function or variable names must start with an uppercase letter.

In Haskell, there is a special module called Prelude whose contents is always available. The module Prelude contains all the functions that are pre-defined in Haskell, such as +, length, and so on.

For now, as we are starting with simple, short programs, we will add all function definitions of a program to a single module. Later we will learn how we can structure more complex programs using multiple modules. In fact, this is a central topic in software development, and modules play an essential role in structuring large software systems.

Indirizzarsi nel flusso di controllo
ho difficoltà a tradurre “branching” 😊

So far, each of our functions has unconditionally performed one specific computation. In general, this is too limiting; so, next, we will look at the role of conditionals in Haskell programs.

choice by way of conditionals
How can we implement a function max which returns the greater of its two arguments? That is, the expressions max 5 2 and max 2 5 both evaluate to 5, max 1 7 to 7, and so on. For two arbitrary numbers x and y, we want max x y to return x if x >= y; otherwise, it should return y. (Note: The function max, as well as signum discussed later, are already defined in the Prelude; so, if we want to define these functions ourselves, we need to add the line import Prelude hiding (max, signum) right after the module header to hide the standard definitions.)

We can generally compare values with types that belong to the type class Ord, which we discussed in previusly; hence, the type of max is

max :: Ord a => a -> a -> a

This can be expressed in Haskell by a so-called conditional or if-then-else expression of the form

if ⟨condition⟩ then ⟨value if true⟩ else ⟨value if false⟩

Now, we can implement max:

max :: Ord a => a -> a -> a
max x y = if x >= y then x else y

Let’s look at the evaluation of max 5 2:

max 5 2 ⇒ if 5 >= 2 then 5 else 2  ⇒ if True then 5 else 2 ⇒ 5

Conditionals are an essential component of programming, because they allow us to dynamically choose between different computations depending on the values of the inputs. Here is another example:

signum :: (Ord a, Num a) => a -> Int
signum x = if x < 0 then -1 else if x == 0 then 0 else 1

A note about the type of signum: the type of the argument x has to be both in Ord, as we use the function < and ==, but also in Num, otherwise we would not be able to compare it to 0, which is in type class Num. We will cover type classes in more depth in a later chapter.

guards
Cascading conditional expressions —as in the previous definition of signum— are difficult to read; therefore, some programming languages, including Haskell, provide an alternative syntax:

signum :: (Ord a, Num a) => a -> Int
signum x | x < 0 = -1 
         | x == 0 = 0 
         | x >  0  = 1

The guards are checked in the order they are listed. For example, if we apply signum to the number 7, then the system first checks if the argument is less than zero. As this is not the case, it checks whether it is equal to zero, before finally the last guard succeeds:

Prelude> signum 7
1

on the basis of the following three side computations evaluating the guards

Prelude> 7 < 0 
False 
Prelude> 7 == 0
False
Prelude> 7 > 0
True

Usually, the last guard should catch all the cases not covered before. For this purpose, we can use the special guard otherwise, which always evaluates to True:

signum :: (Ord a, Num a) => a -> Int
signum x | x <  0     = -1
         | x == 0     = 0
         | otherwise  = 1

Finally, we can rephrase the definition of max using guards:

max :: Ord a => a -> a -> a
max x y | x >= y     = x 
        | otherwise  = y

Which to choose is often a matter of personal style; however, idiomatic Haskell tends to favour code using guards.

A questo punto, per chi vuole, c’è il ripasso in video, nella pagina da cui copio.

🤢