Поиск индекса элемента в списке в Haskell?

Ответ 1

Как найти индекс максимального элемента? Как насчет того, чтобы попробовать все индексы и проверить, являются ли они максимальными?

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

Но это звучит как нечто, для которого функция уже существует. Мой код будет более читабельным, поддерживаемым и, возможно, даже более эффективным, если я воспользуюсь существующей функцией.

К вашему сведению, вы также можете спросить Hoogle, который может искать по сигнатурам типа Haskell (как будет предложено):

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

Ответ 2

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

Действительно хороший инструмент для поиска функций haskell - Hoogle. Позволяет выполнять поиск по типу подписи между прочим.

Если вы хотите сделать все за один проход, я бы рекомендовал Data.List.mapAccumL, передав индекс наибольшего числа, найденного до сих пор, как накопитель.

Ответ 3

Это, вероятно, не заслуживает того, чтобы быть в его собственном ответе, но я не могу комментировать. Во всяком случае, вот как я написал бы это:

import Data.List
import Data.Ord

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

Ответ 4

Если вы делаете числовые вычисления в Haskell, вам может понадобиться изучить библиотеки, которые упрощают и повышают эффективность. Например hmatrix имеет метод maxIndex для эффективного Vector s, документация которого находится здесь: https://hackage.haskell.org/package/hmatrix-0.17.0.1/docs/Numeric-LinearAlgebra-Data.html#g:14

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

Точные названия методов были разными, когда вопрос был первоначально задан, но библиотека тоже была тогда.

Ответ 5

Как я начинающий Хаскеллер, я подумаю так:

1. Списки Haskell являются связанными списками, поэтому нам нужно вручную прикрепить индексы к элементам: zip [0..] xs. (Обратите внимание, что индексирование на Haskell начинается с нуля, т.е. Заголовок списка равен x !! 0)

2. Я хочу найти максимум этого сжатого списка [(0, x!!0), (1, x!!1),..., (n, x!!n)] соответствии со вторым элементом каждого кортежа, Есть несколько альтернатив, основанных на том, насколько хорошо я знаю Haskell:

   • Я мог бы написать это, как написал Максим, ниже, используя 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-ответ, или это GitHub-репо.

3. Нам все еще нужно взять первый элемент результирующего кортежа (i, xi), предпочтительно со встроенной функцией fst :: (a, b) → a или first (a,b) = a с домашней функцией first (a,b) = a

Конечный результат следующий:

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