CODEWITHSUNDEEP
haskell
AnchovyLegend
AnchovyLegend

Reputation: 12538

Finding the max of a list using tail recursion

I am trying to understand how to write functions using tail recursion in Haskell. In my example below, the function takes in a list and outputs the maximum value in the list. My intention is to use the c variable to store the current max. I was wondering if someone can explain how using tail recursion would work for this instance?

    myMax [] c = error "max of empty list"
    myMax [x] c = x
    myMax (x:xs) c = 
                if x > myMax xs then c = x
                else myMax xs c

--currently getting a parse error

Upvotes: 1

Views: 4338

Answers (2)

fp_mora
fp_mora

Reputation: 714

There is a problem with the normal tail recursive versions of minimum or maximum, that is, the accumulator as parameter. More specifically, the accumulator parameter's initial value must be supplied from the list, the first item of the list, that is the second parameter of the the function and in which you what to find the minimum or maximum. Restated, a min or max tail recursive function must normally take two parameters. The first parameter is the accumulator, the second is the list to analyze. The problem is the initial value of the first parameter. It cannot be supplied except from the list to be analyzed. Next the basis of a tail recursive function is the accumulator. The accumulator is where the last min or max value is stored and passed to the the function to compare to the next value of the list. A basic function could be

fix (\f v (x:xs) -> if xs == [] then v else if x < v then f x xs else f v xs) 9999999 [6,5,4,3,2,1,10,7,8]

The first parameter is a guess at a value higher than any in the list and is destined to fail and cannot be automated. The first parameter should come from the list, perhaps the first item. The first parameter in the preceeding function is 'v'. It carries the last min or max value. It is easy to use another call to the preceding function.

t= \(y:ys) -> (fix (\f v (x:xs) -> if xs == [] then v else if x < v then f x xs else f v xs) y ys)

The first part uses pattern matching (y:ys) to split the supplied list into head and tail. The head becomes the initial v parameter in the called function. The tail becomes the second. This seems convoluted and complicated to me. The accumulator initial value is the problem. It must be calculated. How can this be done? By eliminating the first parameter. Get rid of it. But we must still retain an accumulator value to pass to compare to the next value of the list. Where can we keep it? The only place possible, in the list itself.

minf :: (Num b, Ord b) => [b] -> b
minf [x]      = x
minf (x:xs) = if x > head xs then minf $ x : tail xs else minf xs

minf takes one parameter, the list to analyze for min or max. Just change the comparison sign to '<' or '>' for min or max. Also, I use this version.

min = fix (\f (x:xs) -> if xs == [] then x else if x < head xs then f $ x : tail xs else f xs)

I am only getting my feet wet in Haskell but my expectations for it are extremely high. It is the best language, ever. It is a version of the above and takes one parameter only.

Upvotes: 0

asm
asm

Reputation: 8898

There are a couple things to think about here. First You don't want the user to have to enter some beginning value, so we want a function that takes only a list as its parameter. Since you want a tail recursive implementation we do need a function that takes a second parameter though, so we'll create an inner function named go which takes the current max and the remaining list.

myMax [] = error "Empty List"
myMax (x:xs) = go x xs  -- Initialize current max to head of list.
  where
    -- go takes the current max as the first argument and the remaining list
    -- as the second.
    -- m is the current max, if there are no more elements it is the max.
    go m [] = m 
    -- Otherwise we compare m to the current head.
    -- If the head (y) is greater than m it becomes the current max.
    go m (y:ys) = if m > y then go m ys else go y ys

Note that we never changed the value of any variable here. We update the current max value by passing it as a parameter to the next step in the function. This is critical to understand in Haskell because mutating variables is not allowed.

Upvotes: 6

Related Questions