Zrozumienie rekursji Haskella w funkcjach

Question

Używam kilku zasobów dla Haskella: poznaj Haskella i wikibook. Jednak staram się znaleźć wyjaśnienie, które pomoże mi lepiej zrozumieć rekursję. Dołączyłem przykładowy fragment kodu z książki "Uczę się Haskella", którą częściowo rozumiem.

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 

Rozumiem cały powyższy kod do ostatniej linii "gdzie maxTail = maximum" xs ". To, czego nie rozumiem, to sposób, w jaki kod jest oceniany, aby zwrócić maksimum, od samego wywołania maksymalnego ". Albo jak wie, że maksimum "jest najwyższym elementem listy.

Inny przykład:

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

zrozumieć wszystko aż odwrocie”nazywa na ogonie listy. Innymi słowy, skąd wiadomo, że odwrócenie "oznacza odwrócenie elementów ogona.

Naprawdę doceniam wyjaśnienie i przepraszam, jeśli to proste, jestem nowy w tym języku.

Answer 1

Idąc za pośrednictwem linii, linia po linii, więc mam nadzieję, że rozumieją to lepiej:

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 

W wierszu 1: mówisz, że masz listę A i zwraca jeden element tego typu. Dodatkowo elementy na tej liście muszą być uporządkowane, abyś mógł je umieścić w zamówieniu.

W linii 2: masz przypadek skrajny, gdzie mówisz, że jeśli otrzymasz pustą listę jako dane wejściowe, nie może być "najwyższej wartości" na tej pustej liście, więc kończysz funkcję z błędem .

W linii 3: masz inny przypadek na krawędzi, gdzie mówisz, że jeśli otrzymasz listę z jednym elementem, element ten musi być najwyższym elementem, więc go zwrócisz.

W wierszu 4: dopasowujesz wzorce do pierwszego elementu (x), a resztę listy (xs). Następnie sprawdź, czy x jest większy niż maxTail, gdzie maxTail wynik wywołania funkcji maximum' z resztą listy xs.

Jeśli x jest większy niż maxTail potem wrócisz x i inaczej maxTail jest większy niż x i wrócisz maxTail.

myślę przykład z niektórymi numerami powinny również pomóc tutaj:

wejściowe:

[2, 5, 4, 13] 

wezwanie:

maximum' [2, 5, 4, 13] 

Co się dzieje:

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 → ───────────┘ 

---

W drugim przykładzie jest to niemal tak samo:

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

W wierszu 1: mówisz, że masz listę A i zwróci listę ciągu roku.

W linii 2: masz przypadek skrajny, gdzie mówisz, że jeśli otrzymasz pustą listę, odwrócona lista jest również pusta.

W linii 3: ponownie użyjesz dopasowywania wzorów, aby dopasować pierwszy element (x) listy i ogon() z tej listy.

Teraz wystarczy użyć ++, aby dołączyć dwie listy razem, co jest pierwszym elementem listy z odwróconym ogonem.

I znowu mam nadzieję, że na przykładzie będzie to nieco wyraźniej:

wejściowe:

[1, 2, 3] 

wezwanie:

reverse' [1, 2, 3] 

Co się dzieje:

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

Długość

length' [] = 0 

Przypadek 1: długość pustej listy wynosi 0.

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

Przypadek 2: długość listy z co najmniej jednego elementu jest więcej niż 1 długość ogona listy, którą odnajdujemy, powtarzając przypadek 2, dopóki nie pozostaną żadne elementy, spełniając przypadek 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 

---

Odwrócona

reverse' [] = [] 

Przypadek 1: Jeżeli lista jest pusta, jej odwrotna jest również pusta lista.

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

Przypadek 2: jeśli lista zawiera co najmniej jeden element, to możemy zdjąć pierwszy element, przenieść go do końca i odwrócić resztę w ten sam sposób, postępując w dół listy z przypadku 2 aż żadne elementy pozostają spełniających case 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] 

---

Maksymalne

maximum' [x] = x 

Przypadek 1: jeżeli lista ma onl y jeden element, ten element jest maksymalny.

maximum' (x:xs) 

Przypadek 2: jeśli lista zawiera co najmniej jeden element, to albo ...

| x > maxTail = x 

... pierwsza jest większa niż wszystkich innych, w tym przypadku jest to maksymalna; lub ...

| otherwise = maxTail 

... to nie jest, więc maksymalna to największy ze wszystkich innych ...

where maxTail = maximum' xs 

... co możemy znaleźć postępując w dół listy z przypadku 2 aż jeden tylko element pozostaje spełniających przypadek 1.

będę przeformułować definicję maximum' aby łatwiej pokazać, jak to podstawia:

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

Teraz:

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