Understanding Haskell recursion in functions

Question

I've been using a few resources for Haskell: Learn you a Haskell and the wikibook. However, I'm struggling to find an explanation that helps me understand recursion a bit more. I've attached a sample piece of code from the 'Learn you a Haskell' book 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 of the above code until the last line 'where maxTail = maximum' xs'. What I don't understand is how the code is evaluated to return the maximum, from just calling maximum'. Or how it 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 up until reverse' is called on the tail of the list. In other words, how does it know that reverse' means reverse the tails elements.

I would really appreciate an explanation, and apologies if it's simple, I'm new to this language.

Answer 1

Going through the lines, line by line, so you hopefully understand it 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

In line 1: you say that you get a list of a's and return one element of that type. Plus the elements in that list have to be ordable, so you can put them into a order.

In line 2: you have an edge case, where you say that if you get an empty list as input, there can't be a "highest value" in that empty list, so you end the function with an error.

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

In 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 bigger than the maxTail, where maxTail the result of the function call maximum' with the rest of the list xs.

If that x is bigger than maxTail then you return x and otherwise maxTail is bigger 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 happens:

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 it's pretty much the same:

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

In line 1: you say that you get a list of a's and return a list of a's.

In line 2: you have an edge case, where you say if you get an empty list, the reversed list is also just empty.

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

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

And again I hope with an example it will be a bit clearer:

input:

[1, 2, 3]

call:

reverse' [1, 2, 3]

What happens:

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' [] = [] → ──────────────────┘