list 在 Haskell 中查找列表中元素的索引？

Finding index of element in a list in Haskell?

提问by Jonno_FTW

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

我在Haskell 中有一个函数，它可以从列表中找到求幂的最大值：

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..])

回答by yairchu

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 Hooglethat can search by Haskell type signatures (as Will suggested):

仅供参考，您还可以询问可以通过 Haskell 类型签名进行搜索的Hoogle（如 Will 建议的那样）：

$ 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]

回答by Will

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.

查找 haskell 函数的一个非常好的工具是Hoogle。允许您按类型签名等进行搜索。

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.

如果您想一次性完成所有操作，我建议使用 Data.List.mapAccumL，将迄今为止找到的最大数字的索引作为累加器传递。

回答by Maxime Henrion

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..]

回答by Daniel Landau

If you are doing numeric calculation in Haskell, you might want to look into libraries that make it easier and more efficient. For example hmatrixhas a method maxIndexfor 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

如果您在 Haskell 中进行数值计算，您可能需要查看使其更容易和更高效的库。例如hmatrix有一个maxIndex高效Vector的方法，其文档在这里：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.

最初提出问题时，方法的确切名称是不同的，但当时图书馆也存在。

回答by Laszlo Treszkai

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

作为一个新手 Haskeller，我会按照以下思路思考：

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 maximumByexists but I suspected something like this, so I could search for it on Hooglebased on the type signature that I would use: it returns an element of type generic type afrom a list of aelements, using a comparison function on two aparameters (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 xjis greater than xi, so this will return the index of the first maximum. If one has a grudge against importing Data.Listand doesn't work with 1000-item-long lists, then foldl1from Prelude will do just fine. The Data.Vectorpackage uses a similar approach, just search for “maxIndex” hereand here.

   • I don't even know the type class Ordfor comparable objects, in which case cmpBySndwould 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

1. Haskell 列表是链表，因此我们需要手动将索引附加到元素：zip [0..] xs。（注意 Haskell 索引从零开始，即列表的头部是x !! 0。）

2. 我想[(0, x!!0), (1, x!!1), ..., (n, x!!n)]根据每个元组的第二个元素找到这个压缩列表的最大值。根据我对 Haskell 的了解，有一些替代方案：

   • 如果我只知道这些函数存在，我就可以像下面的Maxime写的那样写，使用maximumBy (comparing snd)。
   • 我不知道它maximumBy存在，但我怀疑这样的事情，所以我可以根据我将使用的类型签名在Hoogle上搜索它：它使用比较函数a从a元素列表中返回一个泛型类型的元素在两个a参数 ( a -> a -> Ordering) 上 - 总而言之，它要么是[a] -> (a -> a -> Ordering) -> a，要么是参数的一些更合乎逻辑的排列。考虑一下，将列表作为倒数第二个参数更有意义，因为这样可以更好地进行柯里化，正如我们稍后将看到的那样，所以让我们搜索(a -> a -> Ordering) -> [a] -> a.
   • 我一无所知，或者我认为我可以自己写所有内容（或只是想写），所以我可以这样写：

   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'从左侧开始折叠（意味着累加器在折叠函数的左侧），并且累加索引仅在xj大于 时更新xi，因此这将返回第一个最大值的索引。如果有人反对导入Data.List并且不能处理 1000 项长的列表，那么foldl1来自 Prelude 就可以了。该Data.Vector包使用类似的方法，只需在此处和此处搜索“ maxIndex”即可。

   • 我什至不知道Ord可比较对象的类型类，在这种情况下cmpBySnd会变成

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

   在这一点上，人们会错过代数数据类型和高阶函数的好处（如果不知道，这一事实几乎不可能实现），所以 1) 您问得很好！2) 我可以向下一位读者指出像Learn You A Haskell For Great Good或Real World Haskell 之类的资源，或此 SO answer或此 GitHub repo 之类的资源。

3. 我们仍然需要取结果(i, xi)元组的第一个元素，最好使用内置函数fst :: (a, b) -> a，或者使用自制函数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..]