Find the maximum item and list index in Haskell

Question

I am taking my first steps in the wonderful world of Haskell. As an exercise, I would like to implement a method that finds the maximum list item and its index. Let me call this function "maxi". A call to maxi in the list should return the following result:

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

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

I tried 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 strange: ghci seems to hang after returning the value of the maximum element.

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

I would venture to suggest that this is due to the lazy nature of the Haskell assessment, but it’s hard for me to understand what is really going on here and how to fix it. I would also be very grateful for any advice that you might have about how to debug in Haskell. Is there an easy way to print values ​​at runtime without affecting behavior?

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

thanks

Answer 1

This is due to a small error in your code. You have:

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

... but actually it should be:

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

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

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

Your code hanged because your calculation for ti leads to an infinite loop, because you accidentally defined it in terms of yourself. Note that ghc is a fairly intelligent compiler and calculates that t is independent of the value of ti , so your version can still successfully calculate the maximum value, even if it cannot calculate the index.

The standard way to debug clean calculations is with 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: Unfortunately, I have not seen you consciously implementing it from scratch, but I will still stay there.

Answer 2

I see you have already received the answer to your question. I managed to do this without recursion using lambda functions.

 maxim xs = foldr (\ (x,y) acc -> if (x == maximum xs) then (x,y) else acc) (0,head xs) (zip xs [0..])