CODEWITHSUNDEEP
listhaskellindexing
Jonno_FTW
Jonno_FTW

Reputation: 8809

Finding index of element in a list in Haskell?

I have a function in Haskell which finds the maximum value of an exponentiation from a list:

prob99 = maximum $ map (\xs -> (head xs)^(head (tail xs))) numbers

What I need to find is the location of this maximum value in the resultant list. How would I go about this?

Edit: I found a solution that goes like this:

n = [[519432,525806],[632382,518061]....
prob99b [a,b] = b* (log a)
answer = snd $ maximum (zip  (map prob99b n) [1..])

Upvotes: 37

Views: 68875

Answers (5)

yairchu
yairchu

Reputation: 24754

How to find the index of the maximum element? How about trying all indexes and checking whether they are the maximum?

ghci> let maxIndex xs = head $ filter ((== maximum xs) . (xs !!)) [0..]

But this sounds like something for which a function already exists. My code will be more readable, maintainable, and probably even more efficient, if I used the existing function.

FYI, you can also ask Hoogle that can search by Haskell type signatures (as Will suggested):

$ hoogle "Ord a => [a] -> Int" | head

<Nothing relevant>

$ # hmm, so no function to give me the index of maximum outright,
$ # but how about finding a specific element, and I give it the maximum?
$ hoogle "a -> [a] -> Int" | head
Data.List elemIndex :: Eq a => a -> [a] -> Maybe Int
Data.List elemIndices :: Eq a => a -> [a] -> [Int]

Upvotes: 41

Laszlo Treszkai
Laszlo Treszkai

Reputation: 400

As a novice Haskeller that I am, I would think along these lines:

  1. Haskell lists are linked lists, so we need to manually attach the indices to the elements: zip [0..] xs. (Note that Haskell indexing starts from zero, i.e. the head of a list is x !! 0.)

  2. I want to find the maximum of this zipped list [(0, x!!0), (1, x!!1), ..., (n, x!!n)] according to the second element of each tuple. There are a few alternatives, based on how well I know Haskell:

    • I could write this as Maxime wrote below, using maximumBy (comparing snd), if I only knew that these functions exist.
    • I didn't know that maximumBy exists but I suspected something like this, so I could search for it on Hoogle based on the type signature that I would use: it returns an element of type generic type a from a list of a elements, using a comparison function on two a parameters (a -> a -> Ordering) – altogether it would be either [a] -> (a -> a -> Ordering) -> a, or some more logical permutation of the arguments. Thinking of it, putting the list as the penultimate argument makes more sense, because then it allows for better currying as we'll see in a moment, so let's search for (a -> a -> Ordering) -> [a] -> a.
    • I'm clueless or I think I can write everything myself (or just want to), so I can write this as:

    import Data.List (foldl1')

maxBySnd :: Ord a => [(Int, a)] -> (Int, a)
maxBySnd = foldl1 cmpBySnd
  where
    cmpBySnd (i, xi) (j, xj) = case xi `compare` xj of
                                 LT -> (j, xj)
                                 _  -> (i, xi)

    foldl1' starts folding from the left (meaning the accumulator is on the left in the folding function), and the accumulated index is updated only if xj is greater than xi, so this will return the index of the first maximum. If one has a grudge against importing Data.List and doesn't work with 1000-item-long lists, then foldl1 from Prelude will do just fine. The Data.Vector package uses a similar approach, just search for “maxIndex” here and here.

    • I don't even know the type class Ord for comparable objects, in which case cmpBySnd would become

        cmpBySnd (i, xi) (j, xj) = if xi < xj then j else i

    At this point one would be missing out on the benefits of algebraic data types and higher-order functions (which fact is almost impossible to realize if one doesn't know), so 1) it's good that you're asking! 2) may I point the next reader to a resource like Learn You A Haskell For Great Good, or Real World Haskell, or this SO answer, or this GitHub repo.

  3. We still need to take the first element of the resulting (i, xi) tuple, preferably with the built-in function fst :: (a, b) -> a, or with the home-made function first (a,b) = a

The end result is the following:

import Data.List (maximumBy)
import Data.Ord (comparing)

maxIndex :: Ord a => [a] -> Int
maxIndex = fst . maximumBy (comparing snd) . zip [0..]
-- or
-- maxIndex = fst . maxBySnd . zip [0..]

Upvotes: 3

Daniel Landau
Daniel Landau

Reputation: 2314

If you are doing numeric calculation in Haskell, you might want to look into libraries that make it easier and more efficient. For example hmatrix has a method maxIndex for efficient Vectors, the documentation of which is here: https://hackage.haskell.org/package/hmatrix-0.17.0.1/docs/Numeric-LinearAlgebra-Data.html#g:14

> maxIndex $ vector [1, 3, 2]
1

The exact names of the methods were different when the question was originally asked but the library was around then too.

Upvotes: 1

Maxime Henrion
Maxime Henrion

Reputation: 146

This probably doesn't deserve to be in an answer of his own, but I can't comment yet. Anyway, here is how I would have written this:

import Data.List
import Data.Ord

maxIndex ::  Ord a => [a] -> Int
maxIndex = fst . maximumBy (comparing snd) . zip [0..]

Upvotes: 11

Will
Will

Reputation: 1631

import Data.List
elemIndex 'b' "abc" === Just 1

A really good tool for finding haskell functions is Hoogle. Allows you to search by type signature among other things.

If you wanted to do everything in one pass I'd recommend Data.List.mapAccumL, passing the index of the largest number found so far along as the accumulator.

Upvotes: 36

Related Questions