Informazioni sulla ricorsione Haskell nelle funzioni

Question

Ho usato poche risorse per Haskell: Imparate un Haskell e il wikibook. Tuttavia, sto faticando a trovare una spiegazione che mi aiuti a capire la ricorsione un po 'di più. Ho allegato un esempio di codice del libro "Learn you a Haskell" che in parte comprendo.

maximum' :: (Ord a) => [a] -> a 
maximum' [] = error "maximum of empty list" 
maximum' [x] = x 
maximum' (x:xs) 
    | x > maxTail = x 
    | otherwise = maxTail 
    where maxTail = maximum' xs 

Capisco tutto il codice di cui sopra fino a quando l'ultima riga 'dove maxTail = massimi' xs'. Quello che non capisco è come viene valutato il codice per restituire il massimo, dal solo richiamo del massimo '. O come sa che il massimo 'è l'elemento più alto della lista.

Un altro esempio:

reverse' :: [a] -> [a] 
reverse' [] = [] 
reverse' (x:xs) = reverse' xs ++ [x] 

capire tutto fino inverso' viene chiamata sulla coda della lista. In altre parole, come fa a sapere che il contrario "significa invertire gli elementi delle code.

Apprezzerei molto una spiegazione e mi scuso se è semplice, sono nuovo in questa lingua.

Answer 1

Passando attraverso le linee, riga per riga, in modo da poter meglio capire meglio:

1| maximum' :: (Ord a) => [a] -> a 
2| maximum' [] = error "maximum of empty list" 
3| maximum' [x] = x 
4| maximum' (x:xs) 
    | x > maxTail = x 
    | otherwise = maxTail 
    where maxTail = maximum' xs 

In linea 1: si dice che si ottiene un elenco di di e restituire un elemento di quel tipo. Inoltre, gli elementi di quella lista devono essere ordinati, quindi puoi metterli in un ordine.

Nella riga 2: si ha un caso limite, dove si dice che se si ottiene una lista vuota come input, non ci può essere un "valore più alto" in quella lista vuota, quindi si termina la funzione con un errore .

Nella riga 3: si ha un altro caso limite, in cui si dice che se si ottiene un elenco con 1 elemento, quell'elemento deve essere l'elemento più alto, quindi lo si restituisce.

Nella riga 4: si utilizza la corrispondenza del modello per abbinare il primo elemento (x) e il resto dell'elenco (xs). Quindi si controlla se maxTail è più grande di maxTail, dove è il risultato della chiamata di funzione maximum' con il resto dell'elenco xs.

Se questo x è più grande maxTail poi ritorni x ed altrimenti maxTail è più grande di x e ritorni maxTail.

penso che un esempio con alcuni numeri dovrebbe anche aiutare qui:

ingresso:

[2, 5, 4, 13] 

chiamata:

maximum' [2, 5, 4, 13] 

Cosa succede:

maximum' (x : xs) 
      ↓  ↓ 
maximum' (2:[5, 4, 13]) 
      │ 
      ↓        result 13 
    x > maxTail = x       ↑ 
    2 > maximum' [5, 4, 13] = x //2 > 13 = 13 ← ────┐ 
     │           │ 
     └ maximum' (x : xs)      │ 
         ↓ ↓       │ 
      maximum' (5:[4, 13])      │ 
         │        │ 
         ↓        ↑ 
       x > maxTail = x      │ 
       5 > maximum' [4, 13] = x //5 > 13 = 13 ← ─────┐ 
        │           │ 
        └ maximum' (x: xs)      │ 
            ↓ ↓       │ 
         maximum' (4:[13])      │ 
            │       │ 
            ↓       ↑ 
           x > maxTail = x     │ 
           4 > maximum' [13] = x //4 > 13 = 13 ┐ 
            │         │ 
            └ maximum' [x] = x    ↑ 
            maximum' [13] = 13 → ───────────┘ 

---

Nel suo secondo esempio è più o meno lo stesso:

1| reverse' :: [a] -> [a] 
2| reverse' [] = [] 
3| reverse' (x:xs) = reverse' xs ++ [x] 

In linea 1: si dice che si ottiene un elenco di di e restituire un elenco di di.

Nella riga 2: si ha un caso limite, dove si dice se si ottiene una lista vuota, l'elenco invertito è anche solo vuoto.

Nella riga 3: si utilizza nuovamente la corrispondenza del modello per abbinare il primo elemento (x) dell'elenco e la coda (xs) di esso.

Ora basta usare ++ per aggiungere due elenchi, che è il primo elemento della lista con la coda invertita.

E di nuovo mi auguro con un esempio che sarà un po 'più chiaro:

ingresso:

[1, 2, 3] 

chiamata:

reverse' [1, 2, 3] 

Cosa succede:

reverse' (x : xs) 
      ↓ ↓ 
reverse' (1:[2, 3]) 
      │        result [3, 2, 1] 
      ↓          ↑ 
    (reverse' [2, 3]) ++ [1] //[3, 2] ++ [1] = [3, 2, 1] ← ────┐ 
    │               │ 
    └ reverse' (x: xs)           │ 
       ↓ ↓           │ 
     reverse' (2:[3])           │ 
       │            ↑ 
       ↓            │ 
     (reverse' [3]) ++ [2] //[3] ++ [2] = [3, 2] ← ───┐ → ┘ 
      │            │ 
      └ reverse' (x:xs)        │ 
         ↓ ↓         │ 
      reverse' (3:[])        │ 
         │         ↑ 
         ↓         │ 
       (reverse' []) ++ [3] //[] ++ [3] = [3] ┐ → ┘ 
       │          ↑   
       └ reverse' [] = [] → ──────────────────┘ 

Answer 2

intera

length' [] = 0 

Caso 1: la lunghezza di un elenco vuoto è 0.

length' (x:xs) = 1 + length' xs 

Caso 2: la lunghezza di una lista con almeno un elemento è 1 superiore al lunghezza della coda della lista, che troviamo ripetendo caso 2 fino a non più restano elementi, soddisfacendo caso 1.

length' [1, 2, 3] 
= 
length' (1 : (2 : (3 : []))) 
= 
1 + length' (2 : (3 : [])) 
= 
1 + (1 + length' (3 : [])) 
= 
1 + (1 + (1 + length' [])) 
= 
1 + (1 + (1 + 0)) 
= 
1 + (1 + 1) 
= 
1 + 2 
= 
3 

---

Reverse

reverse' [] = [] 

Caso 1: se una lista è vuota, il suo contrario è anche una lista vuota.

reverse' (x:xs) = reverse' xs ++ [x] 

Caso 2: se un elenco contiene almeno un elemento, allora possiamo tirare fuori il primo elemento, spostarlo alla fine, e invertire il resto nello stesso modo, procedendo lungo la lista con il caso 2 fino a quando non rimangono elementi, soddisfacendo caso 1.

reverse' [1, 2, 3] 
= 
reverse' (1 : (2 : (3 : []))) 
= 
reverse' (2 : (3 : [])) ++ [1] 
= 
reverse' (3 : []) ++ [2] ++ [1] 
= 
reverse' [] ++ [3] ++ [2] ++ [1] 
= 
[] ++ [3] ++ [2] ++ [1] 
= 
[3, 2, 1] 

---

massima

maximum' [x] = x 

caso 1: se un elenco ha onl y un elemento, quell'elemento è il massimo.

maximum' (x:xs) 

Caso 2: Se un elenco ha almeno un elemento, allora o ...

| x > maxTail = x 

... il primo è più grande di tutti gli altri, in questo caso è il massimo; o ...

| otherwise = maxTail 

... non è, in modo che il massimo è il più grande di tutti gli altri ...

where maxTail = maximum' xs 

... che troviamo procedendo verso il basso la lista con il caso di 2 fino a quando un solo elemento rimane, soddisfacendo caso 1.

sarò riformulare la definizione di maximum' per rendere più facile per mostrare come esso sostituisce:

maximum' (x:xs) = let maxTail = maximum' xs in 
    if x > maxTail then x else maxTail 

Ora:

maximum' [1, 3, 2] 
= 
maximum' (1 : (3 : (2 : []))) 
= 
let maxTail1 = maximum' (3 : (2 : [])) in 
    if 1 > maxTail1 then 1 else maxTail1 
= 
let maxTail1 = 
    (let maxTail2 = maximum' (2 : []) in 
     if 3 > maxTail2 then 3 else maxTail2) in 
    if 1 > maxTail1 then 1 else maxTail1 
= 
let maxTail1 = 
    (let maxTail2 = 2 in 
     if 3 > maxTail2 then 3 else maxTail2) in 
    if 1 > maxTail1 then 1 else maxTail1 
= 
let maxTail1 = (if 3 > 2 then 3 else 2) in 
    if 1 > maxTail1 then 1 else maxTail1 
= 
let maxTail1 = 3 in 
    if 1 > maxTail1 then 1 else maxTail1 
= 
if 1 > 3 then 1 else 3 
= 
3