Haskell – 145 – elementi base del linguaggio – 8

Continuo da qui, copio qui.

Ricorsività
In imperative languages like C and Java, the most basic control structure is a loop (like a for loop). However, for loops don’t make much sense in Haskell because they require destructive update (the index variable is constantly being updated). Instead, Haskell uses recursion.

A function is recursive if it calls itself (see the appendix on Recursion [prossimamente] for more). Recursive functions exist also in C and Java but are used less than they are in functional languages. The prototypical recursive function is the factorial function. In an imperative language, you might write this as something like:

int factorial(int n) {
  int fact = 1;
  for (int i=2; i <= n; i++)
    fact = fact * i;
  return fact;
}

While this code fragment will successfully compute factorials for positive integers, it somehow ignores the basic definition of factorial, usually given as:

This definition itself is exactly a recursive definition: namely the value of n! depends on the value of (n-1)!. If you think of ! as a function, then it is calling itself. We can translate this definition almost verbatim into Haskell code:

factorial 1 = 1
factorial n = n * factorial (n-1)

This is likely the simplest recursive function you’ll ever see, but it is correct.

Note: Of course, an imperative recursive version could be written:

int factorial(int n) {
  if (n == 1)
    return 1;
  else
    return n * factorial(n-1);
}

but this is likely to be much slower than the loop version in C.

Recursion can be a difficult thing to master. It is completely analogous to the concept of induction in mathematics (see the chapter Recursion [prossimamente] for a more formal treatment of this). However, usually a problem can be thought of as having one or more base cases and one or more recursive-cases. In the case of factorial, there is one base case (when n=1) and one recursive case (when n>1). For designing your own recusive algorithms, it is often useful to try to differentiate these two cases.

Turning now to the task of exponentiation, suppose that we have two positive integers a and b, and that we want to calculate a^b. This problem has a single base case: namely when b is 1. The recursive case is when b>1. We can write a general form as:

Again, this translates directly into Haskell code:

exponent a 1 = a
exponent a b = a * exponent a (b-1)

Just as we can define recursive functions on integers, so can we define recursive functions on lists. In this case, usually the base case is the empty list [], and the recursive case is a cons list (i.e., a value consed on to another list).

Consider the task of calculating the length of a list. We can again break this down into two cases: either we have an empty list or we have a non-empty list. Clearly the length of an empty list is zero. Furthermore, if we have a cons list, then the length of this list is just the length of its tail plus one. Thus, we can define a length function as:

my_length [] = 0
my_length (x:xs) = 1 + my_length xs

Note: Whenever we provide alternative definitions for standard Haskell functions, we prefix them with my_ so the compiler doesn’t become confused.

Similarly, we can consider the filter function. Again, the base case is the empty list, and the recursive case is a cons list. However, this time, we’re choosing whether to keep an element, depending on whether or not a particular predicate holds. We can define the filter function as:

my_filter p [] = []
my_filter p (x:xs) =
  if p x
    then x : my_filter p xs
    else my_filter p xs

In this code, when presented with an empty list, we simply return an empty list. This is because filter cannot add elements; it can only remove them.

When presented with a list of the form x:xs, we need to decide whether or not to keep the value x. To do this, we use an if statement and the predicate p. If p x is true, then we return a list that begins with x followed by the result of filtering the tail of the list. If p x is false, then we exclude x and return the result of filtering the tail of the list.

We can also define map and both fold functions using explicit recursion. See the exercises for the definition of map and the chapter Language advanced [prossimamente] for the folds.

Esercizi
The fibonacci sequence is defined by:

Write a recursive function fib that takes a positive integer n as a parameter and calculates Fn.

Attenzione 😯: questo è un caso che già una volta mi ha fatto hangare il ‘puter. È un problema di GHCi che non accetta le funzioni su più righe, occorre creare un file e caricarlo.

fib.hs

fib 1 = 1
fib 2 = 2
fib n = fib (n - 2) + fib (n -1)
Prelude> :l fib
[1 of 1] Compiling Main             ( fib.hs, interpreted )
Ok, modules loaded: Main.
*Main> fib 5
8
*Main> fib 10
89

Define a recursive function mult that takes two positive integers a and b and returns a*b, but only uses addition (i.e., no fair just using multiplication). Begin by making a mathematical definition in the style of the previous exercise and the rest of this section.

mult.hs

mult a 1 = a
mult a b = a + mult a (b -1)
Prelude> :l mult
[1 of 1] Compiling Main             ( mult.hs, interpreted )
Ok, modules loaded: Main.
*Main> mult 6 7
42

Define a recursive function my_map that behaves identically to the standard function map.

my_map

doppio x = 2 * x

my_map f [] = []
my_map f (x : xs) = f x : my_map f xs
Prelude> :l my_map
[1 of 1] Compiling Main             ( my_map.hs, interpreted )
Ok, modules loaded: Main.
*Main> my_map doppio [1,2,3,4,5]
[2,4,6,8,10]

👽

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: