Understanding Recursion in Haskell

Question

I find it very difficult to understand how to think about problems recursively and solve them with Haskell. I spent hours reading, trying to wrap my head around recursion. The explanation that I most often get from people who understand it is never clear and something like "you pass the function, the name of the function as an argument, then the function executes, solving a small part of the problem and calling again and again while you don't press the base case. "

Can someone please be kind and lead me through the thought process of these three simple recursive functions? Not so much functionality as how the code ends execution and problem solving, recursively.

Thank you very much in advance!

Function 1

maximum' [] = error "maximum of empty list" maximum' [x] = x maximum' (x:rest) = max x(maximum' rest) 

Function 2

 take' n _ | n <= 0 = [] take' _ [] = [] take' n (x:xs) = x : take' (n-1) xs 

Function 3

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

Answer 1

Recommendations

When trying to understand recursion, it will be easier for you to think about how the algorithm works for a given input. It's easy to hang up on what the execution path looks like, so instead ask yourself questions such as:

• What happens if I go through an empty list?
• What happens if I pass a list with one item?
• What happens if I pass a list with many items?

Or, for recursion by numbers:

• What happens if I pass a negative number?
• What happens if I pass 0?
• What happens if I pass a number greater than 0?

The structure of a recursive algorithm is often just a matter of covering the above cases. So let's see how your algorithms behave to understand this approach:

maximum

 maximum [] = error maximum [1] = 1 maximum [1, 2] = 2 

As you can see, the only interesting behavior is # 3. The rest just guarantee that the algorithm completes. Considering the definition,

 maximum' (x:rest) = max x (maximum' rest) 

The challenge of this using [1, 2] extends to:

 maximum [1, 2] ~ max 1 (maximum' [2]) ~ max 1 2 

maximum' works by returning a number that in this case knows how to process recursively using max . Consider another case:

 maximum [0, 1, 2] ~ max 0 (maximum' [1, 2]) ~ max 0 (max 1 2) ~ max 0 2 

You can see how the maximum' recursive call on the first line is exactly the same as in the previous example.

reverse '

 reverse [] = [] reverse [1] = [1] reverse [1, 2] = [2, 1] 

Reverse works by taking the head of a given list and inserting it at the end. For an empty list, this does not require any work, so the basic case. Therefore, given the definition:

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

We will make some replacement. Given that [x] equivalent to x:[] , you can see that there are actually two values:

 reverse' [1] ~ reverse' [] ++ 1 ~ [] ++ 1 ~ [1] 

Simple enough. And for a two-element list:

 reverse' [0, 1] ~ reverse' [1] ++ 0 ~ [] ++ [1] ++ 0 ~ [1, 0] 

take '

This function introduces recursion on an integer argument, as well as on lists, so there are two basic cases.

• What happens if we take 0 or less items? We do not need to take any items, so just return an empty list.

   take' n _ | n <= 0 = [] take' -1 [1] = [] take' 0 [1] = [] 

• What happens if we go through an empty list? There are no more items, so stop the recursion.

   take' _ [] = [] take' 1 [] = [] take -1 [] = [] 

The softness of the algorithm really is to go down the list, pull out the input list and reduce the number of elements that need to be executed until none of the above basic cases stops the process.

 take' n (x:xs) = x : take' (n-1) xs 

So, in the case when the numerical base case is executed first, we stop before we reach the end of the list.

 take' 1 [9, 8] ~ 9 : take (1-1) [8] ~ 9 : take 0 [8] ~ 9 : [] ~ [9] 

In the case when the first case of the list is satisfied, we finished the elements before the counter reaches 0, and simply return what we can.

 take' 3 [9, 8] ~ 9 : take (3-1) [8] ~ 9 : take 2 [8] ~ 9 : 8 : take 1 [] ~ 9 : 8 : [] ~ [9, 8] 

Answer 2

Recursion is a strategy for applying this function to a given set. You apply the function to the first element of the set, than you will repeat the process for the remaining elements of the set.

Let's take an example, you want to double the whole integer inside the list. First you think what function I want to apply? Answer → 2* , now you have to apply this function recursively. Lets call it apply_rec , so you have:

 apply_rec (x:xs) = (2*x) 

But this will only change the first element, you want to change all the elements on the set. Therefore, you should apply apply_rec to the rest of the elements. Thus:

 apply_rec (x:xs) = (2*x) : (apply_rec xs) 

But now you have a problem. When does apply_rec end? Ends when you reach the end of the list. In other words [] , so you need to define this new premise.

 apply_rec [] = [] apply_rec (x:xs) = (2*x) : (apply_rec xs) 

When you reach the goal, you do not want to use any function, so you defined this behavior. Thus, when the end is reached, the apply_rec function should "return" [] .

Let's look at the behavior of this function in the set = [1,2,3] .

• apply_rec [1,2,3] = (2 * 1) : (apply_rec [2,3])
• apply_rec [2,3] = 2 : ((2 * 2) : (apply_rec [3]))
• apply_rec [3] = 2 : (4 : ((2 * 3) : (apply_rec []))
• apply_rec [] = 2 : (4 : (6 : [])))

which leads to [2,4,6] .

Probably, since you do not know recursion very well, it is best to start when you have presented simpler examples. And study it yourself, even if it takes several hours.

Look to learn recursion on this Haskell Tutorial 3 - recursion .

Answer 3

You ask about the “thought process,” presumably the programmer, not the computer, right? So here are my two cents:

How to think about writing some function g with recursion, imagine that you already wrote this function . It's all.

This means that you can use it whenever you need it, and it will "do" everything that it should do. So just write what it is - formulate the laws that he must abide by , write down everything you know about it. Say something about it.

Now, just saying gx = gx says nothing. Of course, this is true, but it is a meaningless tautology. If we say gx = g (x+2) , this is no longer a tautology, but still meaningless. We need to say something more reasonable. For example,

 g :: Integer -> Bool gx | x<=0 = False g 1 = True g 2 = True 

here we said something. Besides,

 gx = x == y+z where y = head [y | y<-[x-1,x-2..], gy] -- biggest y<x that gy z = head [z | z<-[y-1,y-2..], gz] -- biggest z<y that gz 

Did we say all we could say about x ? Whether we will do it or not, we talked about this x . And this concludes our recursive definition - as soon as all the possibilities are exhausted, we are done .

But what about completion ? We want to get some kind of result from our function, we want it to complete its work. This means that when we use it to compute x , we need to make sure that we use it recursively with some y , which defined "before x , " closer to one of the simplest specific cases we have .

And so, we did it. Now we can marvel at our work,

 filter g [0..] 

The last thing to understand the definition, do not try to repeat the steps. Just read the equations themselves. If we were presented with the above definition for g , we would read it simply like this: g is a Boolean function of a number that is True for 1 and 2, and for any x > 2 that is the sum of its two previous g numbers.

Answer 4

Looking at feature 3:

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

Say you called reverse '[1,2,3], then ...

 1. reverse' [1,2,3] = reverse' [2,3] ++ [1] reverse' [2,3] = reverse' [3] ++ [2] ... so replacing in equation 1, we get: 2. reverse' [1,2,3] = reverse' [3] ++ [2] ++ [1] reverse' [3] = [3] and there is no xs ... ** UPDATE ** There *is* an xs! The xs of [3] is [], the empty list. We can confirm that in GHCi like this: Prelude> let (x:xs) = [3] Prelude> xs [] So, actually, reverse' [3] = reverse' [] ++ [3] Replacing in equation 2, we get: 3. reverse' [1,2,3] = reverse' [] ++ [3] ++ [2] ++ [1] Which brings us to the base case: reverse' [] = [] Replacing in equation 3, we get: 4. reverse' [1,2,3] = [] ++ [3] ++ [2] ++ [1], which collapses to: 5. reverse' [1,2,3] = [3,2,1], which, hopefully, is what you intended! 

Perhaps you can try to do something similar with the other two. Select small options.
Good luck

Answer 5

Perhaps the way you present your problem is not very good, I mean, this is not related to the implementation of an existing recursive function, and you will understand how it can be replicated. I prefer to provide you with an alternative way, it can be considered as a methodological process that will help you write a standard skeleton of a recursive call, and then facilitate the discussion about them.

Your whole example is about a list, then the first material when you work with a list should be exhaustive, I mean use pattern matching.

 rec_fun [] = -- something here, surely the base case rec_fun (x:xs) = -- another thing here, surely the general case 

Now the base case cannot contain a recursive one, otherwise you will end an infinite loop, then the base case should return a value, and the best way to understand this value is to look at the annotation of the type of your function,

For example:

 reverse :: [a] -> [a] 

May suggest you consider the base case as a value of type [a], as [] for the opposite

 maximum :: [a] -> a 

Perhaps you should consider the base case as a value of type a for maximum

Now for the recursive part, as said, the function must include calling itself.

 rec_fun (x:xs) = fun x rec_fun xs 

happy to indicate the use of another function that is responsible for implementing the chain of the recursive call. To help your intuition, we can imagine it as an operator.

 rec_fun (x:xs) = x `fun` rec_fun xs 

Now, considering (again) the annotation of the type of your function (or, more briefly, the base case), you should be able to determine the nature of this operator. For the opposite, since it should return a list, the operator is certainly concatenation (++) and so on.

If you put it all together, it should not be so difficult to achieve the desired implementation.

Of course, as with any other algorithm, you always need to think a little, and there is no magic recipe you should think about. For example, when you know the maximum tail of a list, what is the maximum list?