CODEWITHSUNDEEP
haskellrecursionfunctional-programmingtail-recursion
Pierre P.
Pierre P.

Reputation: 1061

Update a function to include tail recursion

I have the following function that determines the maximum element of a given list. 

maxList :: Ord a => [a] -> a
maxList l =
    let iMaxList :: Ord a => [a] -> a
        iMaxList [] = error( "Empty list" )
        iMaxList [x] = x
        iMaxList ( x:xs )
            | x > t = x
            | otherwise = t
            where t = iMaxList xs
    in iMaxList l

Yet, it doesn't use tail recursion and I'd like it to do so. I tried to use an accumulator to comply with the tail recursion principle in Haskell. 

maxList :: Ord a => [a] -> a
maxList ( x:xs ) = loop( xs, x )
                  where loop( x:xs, m )
                            | ( null xs ) = m
                            | ( x >= m ) = loop( xs, x )
                            | otherwise = loop( xs, m )

Yet, it logically fails because of this guard (null xs) = m. Indeed, if we take the list [1,2,3,4], 4will never be evaluated.

How can I fix that?

Upvotes: 1

Views: 419

Answers (3)

Davislor
Davislor

Reputation: 15154

listMax :: Ord a => [a] -> a
listMax [] = error "Tried to find maximum of an empty list."
listMax (x:xs) = listMax' xs x where
  listMax' :: Ord a => [a] -> a -> a
  listMax' [] y = y
  listMax' (x:xs) y | x > y     = listMax' xs x
                    | otherwise = listMax' xs y

In this case, y is the accumulating parameter that holds the maximum value found so far. Brief proof of correctness: the algorithm terminates because each tail-recursive call removes one element from the input list until it is empty. The final value of y it returns is the maximum because, for every other element x in the input, either y > x or y > z > x for some z after x and before y. (This assumes that > is transitive.)

You could also write the helper function this way:

listMax' :: Ord a => [a] -> a -> a
listMax' [] y = y
listMax' (x:xs) y = listMax' xs (max x y)

And this implementation does the same thing:

listMax2 :: Ord a => [a] -> a
listMax2 [] = error "Tried to find maximum of an empty list."
listMax2 list = foldl1 max list

The foldl1 function is a tail-recursive lazy evaluation from front to back, but the strict foldl1' version or foldr1 might be more efficient in this case. The first version is closer to strict evaluation than lazy.

Upvotes: 1

Benjamin Hodgson
Benjamin Hodgson

Reputation: 44654

Don't worry about it.

I wrote the following in a file:

module MaxList (maxList) where

import Data.List

maxList :: Ord a => [a] -> a
maxList = foldl1' max

Then I compiled it with -O2 -ddump-simpl, to have a look at the optimised Core. After a bit of cleaning up - GHC generates a lot of variables with names that are difficult to read - the generated code looks like this:

maxList [] = error "empty list"
maxList (x:xs) = go xs x
    where go ys y =
              case ys of
                   [] -> y;
                   (z:zs) -> case y of  -- force y to WHNF before continuing
                                  _ -> go zs (max y z)

go is tail recursive. In fact it's the same as the code in @Davislor's answer! I used foldl1' - a high-level control structure - and GHC generated exactly the code that you would've written by hand if you wanted to write a tail recursive loop.

Haskell's philosophy is that you should use high-level tools like folds, unfolds, monads, classes, etc, and rely on the compiler to generate good code. There certainly is an art to writing code which GHC will do a good job of optimising - you don't always get it for free - but you usually shouldn't need to unroll high-level structures into low-level loops because GHC is good at that.

Upvotes: 0

Román García
Román García

Reputation: 423

I guess this is what your are searching for:

maxList' :: Ord a => [a] -> a
maxList'     []   = error "Empty List"
maxList'    [x]   = x
maxList' (x:y:xs) = maxList' (max x y:xs)

The function uses the same list that is processing to store the biggest number found so far. It seems to comply with the tail recursion definition, ie: the recursive call is the very last thing in the computation of the function.

Upvotes: 1

Related Questions