Understanding Haskell recursion in functions

Question

I used several resources for Haskell: learn about Haskell and wikibook. However, I am struggling to find an explanation that helps me understand recursion a bit more. I have attached a sample code from the book Learning You, Haskell, which I partially understand.

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 

I understand all the above code to the last line of 'where maxTail = maximum' xs'. What I don't understand is how the code is evaluated to return the maximum, from just calling the maximum '. Or how he knows that the maximum is the highest element of the list.

Another example:

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

Understand everything until the reverse direction in the tail of the list is reversed. In other words, how does he know that reverse 'means the inverse element of the tails.

I am very grateful for the explanation and apologize if it is simple, I am new to this language.

Answer 1

Going through the lines, in turn, so you hopefully understand this better:

 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 

On line 1: you say you get a list a and return one element of this type. Plus, the items in this list should be consistent, so you can tidy them up.

On line 2: you have an edge where you say that if you get an empty list as input, this empty list cannot have the “highest value”, so you end the function with an error.

On line 3: you have another edge where you say that if you get a list with 1 element, that element should be the highest element, so you return it.

On line 4: you use pattern matching to match the first element ( x ) and the rest of the list ( xs ). Then you check if x is greater than maxTail , where maxTail result of calling the maximum' function with the rest of the xs list.

If this x greater than maxTail , you return x , otherwise maxTail greater than x and you return maxTail .

I think an example with some numbers should also help here:

input:

 [2, 5, 4, 13] 

call:

 maximum' [2, 5, 4, 13] 

What's happening:

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

---

In your second example, this is about the same:

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

On line 1: you say you get list a and return list a.

On line 2: you have an edge where you say that if you get an empty list, the inverted list is also empty.

On line 3: you again use pattern matching to match the first item ( x ) of the list and tail ( xs ).

Now you just use ++ to add two lists together, which is the first element of a list with a reverse tail.

And again, I hope the example is a little clearer:

input:

 [1, 2, 3] 

call:

 reverse' [1, 2, 3] 

What's happening:

 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

Length

 length' [] = 0 

Case 1: The length of the empty list is 0.

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

Case 2: the length of the list with at least one element is 1 greater than the tail length of the list, which we find by repeating case 2, until there are no more elements satisfying case 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' [] = [] 

Case 1: if the list is empty, its reverse is also an empty list.

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

Case 2: if there is at least one element in the list, then we can remove the first element, move it to the end and flip everything else in the same way - by going through the list with register 2 until there are no elements remaining that satisfy 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] 

---

Maximum

 maximum' [x] = x 

Case 1: if the list has only one element, this element is the maximum.

 maximum' (x:xs) 

Case 2: if the list has at least one element, then either ...

  | x > maxTail = x 

... the first of them is larger than all the others, and in this case its maximum; or...

  | otherwise = maxTail 

... it is not, therefore, the maximum is the largest of all the others ...

  where maxTail = maximum' xs 

... which we find by going through the list with register 2 until there is only one element left that satisfies case 1.

Rephrase the maximum' definition to make it easier to show how it replaces:

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

Now:

 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