0

Given an Array, I need to compute the index of the maximum element (which is assumed to be unique).

My current attempt is:


maxIndex' :: (Ix i, Ord a) => Array i a -> [i] -> i -> a -> i -> a -> i
maxIndex' arr ids index element maxIndex maxElement
  | length ids == 1 && element > maxElement = index
  | length ids == 1 && element <= maxElement = maxIndex
  | element > maxElement = maxIndex' arr (tail ids) (head ids) (arr ! head ids) index element
  | otherwise = maxIndex' arr (tail ids) (head ids) (arr ! head ids) maxIndex maxElement

maxIndex :: (Ix i, Ord a) => Array i a -> i
maxIndex arr = maxIndex' arr (tail (indices arr)) firstIndex firstMaximum firstIndex firstMaximum
  where
    firstIndex = head (indices arr)
    firstMaximum = arr ! firstIndex

The current implementation, however, is incorrect:

print (maxIndex (array (False,True) [(False,54),(True,104)])) -- Prints False.
print (maxIndex (array (False,True) [(True,104),(False,54)])) -- Prints False.

So, what am I missing?

0

2 Answers 2

1

Your maxIndex function is very complicated, and honestly I don't understand what you are doing. In general, If you are doing a lot of head, tail and explicit recursion something has gone already wrong. The easiest approach is to transform the array in a linked list of pairs (index, element), compare them by the second element of the pair, and get the first one (the index)

import Data.Array
import Data.Function (on)
import Data.List (maximumBy)

-- Notice maximumBy is partial
maxIndex = fst . maximumBy (compare `on` snd) . assocs 
--         |     |                              |- the list of (index, array_element)
--         |     |- maximum using a custom comparision function. In this case, compare on second element in the tuple
--         |- get the first element of the tuple
main = do  
  let arr = array (False,True) [(False,54),(True,104)]
  print $ maxIndex arr 
1
0

Found that meets my experience level:

maxIndex :: (Ix i, Ord a) => Array i a -> i
maxIndex arr = fst (sortBy (\(_,a) (_,b) -> compare b a) (assocs arr) !! 0)
3
  • Nice you found a different solution. Notice (\(_,a) (_,b) -> compare b a) is the same as compare `on` snd. The on combinator is a little it weird, but In general functions ending in By (like sortBy, maximumBy, etc...) interact very well with it. Now, my approach was to use maximumBy instead of sorting and then take the first, which is slower I think. But, yes this solution and mine are very similar indeed
    – lsmor
    May 24 at 6:58
  • 1
    @lsmor I think it's actually flip (compare `on` snd)! May 24 at 15:00
  • @DanielWagner Indeed!!
    – lsmor
    May 24 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.