Find max element and index of a list in Haskell

Question

I'm taking my first steps into the wonderful world of Haskell. As an exercise, I would like to implement a method which finds the maximum element of a list and its index. Let's call this function "maxi". Calling maxi on a list should return the following result:

ghci> maxi [1, 3, 4, 1, 2, 3]
(4, 2)

4 is the largest int in this list, and it is located at index 2.

I have attempted to implement this function as follows:

maxim :: (Ord a) => [a] -> (a, Int)
maxim l = 
  let pmaxim :: (Ord a) => [a] -> Int -> (a, Int) -- Internal function to do the work
      pmaxim [] _  = error "Empty list"           -- List is empty, error
      pmaxim [x] xi = (x, xi)                     -- List has one item, return it and the index
      pmaxim (x:xs) xi                            -- More than one item, break list apart
        | x > t     = (x, xi)                     -- If current item is bigger, return it and its index
        | otherwise = (t, ti)                     -- If list tail has a bigger item, return that
        where (t, ti) = pmaxim xs (ti + 1)        -- Get max of tail of the list
  in pmaxim l 0                                   -- Call internal function with start index

When I call this, I get something really weird: ghci seems to hang after returning the max element's value.

ghci> maxi [1, 3, 4, 1, 2, 3]
(4,

I will venture a guess that this has something to do with Haskell's lazy evaluation nature, but I'm finding it difficult to figure out what is actually going on here, and how to fix it. I would also be really grateful for any tips anyone might have about how to debug in Haskell. Is there an easy way to print out values during execution without effecting behavior?

I just wanted to point out that I am aware that there are several better ways to get this behavior using built-in Haskell functions. I am implementing this from scratch to try and learn Haskell.

Thank you

Answer 1

It's because of a slight bug in your code. You have:

where (t, ti) = pmaxim xs (ti + 1)

... but it should actually be:

where (t, ti) = pmaxim xs (xi + 1)

This fixes your code, which now produces the correct solution:

>>> maxim [1, 2, 3, 2, 1]
(3, 2)

Your code hanged because your computation for ti results in an endless loop since you accidentally defined it in terms of itself. Note that ghc is a sufficiently smart compiler and figures out that t does not depend on the value of ti, which is why your version could still successfully compute the maximum value even if it cannot compute the index.

The standard way to debug pure computations is the Debug.Trace module.

As a side note, there is a much simpler solution:

import Data.List
import Data.Ord

maxi xs = maximumBy (comparing fst) (zip xs [0..])

Edit: Oops, I didn't see that you were deliberately implementing it from scratch, but I'll still leave that there.