Получить индекс следующего наименьшего элемента в списке в Haskell

Question

Я новичок в Хаскеле.Я очень хорошо разбираюсь в императивных языках, но не в функционале.Хаскель мой первый как функциональный язык.

Я пытаюсь выяснить, как получить индекс наименьшего элемента в списке, где минимальный элемент определен мной.

Позвольте мне объяснить на примерах.

Например:

Сигнатура функции minList :: x -> [x]

let x = 2
let list = [2,3,5,4,6,5,2,1,7,9,2] 

minList x list --output 1 <- is index

Это должно вернуть1. Поскольку at at list [1] равен 3. Он возвращает 1, потому что 3 является наименьшим элементом после x (= 2).

let x = 1
let list = [3,5,4,6,5,2,1,7,9,2] 
minList x list -- output 9 <- is index

Он должен возвращать 9, поскольку в списке [9] 2 и2 - самый маленький элемент после 1. x = 1, который я определил.

То, что я пробовал до сих пор.

minListIndex :: (Ord a, Num  a) => a -> [a] -> a
minListIndex x [] = 0
minListIndex x (y:ys) 
            | x > y =  length ys
            | otherwise = m
            where m = minListIndex x ys

Когда я загружаю файл, я получаю эту ошибку

• Couldn't match expected type ‘a’ with actual type ‘Int’
      ‘a’ is a rigid type variable bound by
        the type signature for:
          minListIndex :: forall a. (Ord a, Num a) => a -> [a] -> a
        at myFile.hs:36:17
    • In the expression: 1 + length ys
      In an equation for ‘minListIndex’:
          minListIndex x (y : ys)
            | x > y = 1 + length ys
            | otherwise = 1 + m
            where
                m = minListIndex x ys
    • Relevant bindings include
        m :: a (bound at myFile.hs:41:19)
        ys :: [a] (bound at myFile.hs:38:19)
        y :: a (bound at myFile.hs:38:17)
        x :: a (bound at myFile.hs:38:14)
        minListIndex :: a -> [a] -> a (bound at myFile.hs:37:1)

Когда я изменяю функцию следующим образом

minListIndex :: (Ord a, Num  a) => a -> [a] -> a
minListIndex x [] = 0
minListIndex x (y:ys) 
            | x > y =  2 -- <- modified...
            | otherwise = 3 -- <- modifiedd
            where m = minListIndex x ys

Я снова загружаю файл, затем он компилируется и запускается, но ofc вывод не нужен.

Что такоепроблема с

| x > y =  length ys
| otherwise = m

?

Короче говоря: в основном, я хочу найти индекс наименьшего элемента, но выше, чем x, который я определил в сигнатуре параметра / функции.

Заранее спасибо за помощь!

Answer 1

Мне не понятно, что именно вы хотите.Основываясь на примерах, я предполагаю, что это: найти индекс наименьшего элемента выше x, который появляется после x .В этом случае это решение просто Prelude.Нет импорта

minList :: Ord a => a -> [a] -> Int
minList x l = snd . minimum . filter (\a -> x < fst a) . dropWhile (\a -> x /= fst a) $ zip l [0..]

Логика такова:

• создать список пар, [(elem, index)], используя zip l [0..]
• отбрасывать элементы, пока не найдете входx с использованием dropWhile (\a -> x /= fst a)
• отбрасывает элементы, меньшие x, с использованием filter (\a -> x < fst a)
• находит минимум полученного списка.Кортежи упорядочены с использованием лексикографического порядка, так что это соответствует вашей проблеме
• взять индекс с помощью snd

Answer 2

Во-первых, я бы полностью отделил тип индекса от типа элемента списка.Там нет очевидной причины для них быть одинаковыми.Я буду использовать расширение BangPatterns, чтобы избежать утечки пространства без слишком большого количества обозначений;включите это, добавив {-# language BangPatterns #-} в самый верх файла.Я также импортирую Data.Word, чтобы получить доступ к типу Word64.

Есть два этапа: сначала найти индекс данного элемента (если он есть), а остальную часть списка -точка.Затем найдите индекс минимума хвоста.

-- Find the 0-based index of the first occurrence
-- of the given element in the list, and
-- the rest of the list after that element.
findGiven :: Eq a => a -> [a] -> Maybe (Word64, [a])
findGiven given = go 0 where
  go !_k [] = Nothing --not found
  go !k (x:xs)
    | given == xs = Just (k, xs)
    | otherwise = go (k+1) xs

-- Find the minimum (and its index) of the elements of the
-- list greater than the given one.
findMinWithIndexOver :: Ord a => a -> [a] -> Maybe (Word64, a)
findMinWithIndexOver given = go 0 Nothing where
  go !_k acc [] = acc
  go !k acc (x : xs)
    | x <= given = go (k + 1) acc xs
    | otherwise
    = case acc of
        Nothing -> go (k + 1) (Just (k, x)) xs
        Just (ix_min, curr_min)
          | x < ix_min = go (k + 1) (Just (k, x)) xs
          | otherwise = go (k + 1) acc xs

Теперь вы можете соединить эти функции, чтобы создать ту, которую вы ищете.Если вам нужен общий Num результат, а не Word64, вы можете использовать fromIntegral в самом конце.Зачем использовать Word64?В отличие от Int или Word, он (практически) гарантированно не будет переполнен в любое разумное время.Вероятно, это значительно быстрее, чем использование чего-то вроде Integer или Natural напрямую.

Answer 3

Ваша функция может быть построена из готовых деталей следующим образом:

import Data.Maybe (listToMaybe)
import Data.List  (sortBy)
import Data.Ord   (comparing)

foo :: (Ord a, Enum b) => a -> [a] -> Maybe b
foo x = fmap fst . listToMaybe . take 1 
                 . dropWhile ((<= x) . snd) 
                 . sortBy (comparing snd) 
                 . dropWhile ((/= x) . snd)
                 . zip [toEnum 0..] 

Это Maybe находит индекс следующего наименьшего элемента всписок над данным элементом, расположенный после данного элемента, во входном списке.Как вы и просили.

Вы можете использовать любой тип Enum по вашему выбору в качестве индекса.

Теперь вы можете реализовать эти высокоуровневые исполняемые спецификации как прямую рекурсию, используя эффективнуюMap структура данных для хранения ваших отсортированных элементов выше x видимых до сих пор для поиска следующего наименьшего и т. Д.

Сначала корректность, эффективность позже!

---

Обновление эффективности: отбрасывание после сортировка отбрасывает их сортировка , так что усилия потрачены впустую;на самом деле его следует заменить фильтрацией (как видно из ответа на Luis Morillo ) перед сортировкой.И если наш тип элемента находится в Integral (то есть это правильно дискретный тип, в отличие от Enum, благодаря @ dfeuer для , указывающим это!), Естьеще одна возможность для оппортунистической оптимизации: если мы попадаем на succ минимальный элемент по чистой случайности , дальнейших улучшений больше нет, и мы должны выручить в этот момент прямо здесь:

bar :: (Integral a, Enum b) => a -> [a] -> Maybe b
bar x = fmap fst . either Just (listToMaybe . take 1 
                                . sortBy (comparing snd))
                 . findOrFilter ((== succ x).snd) ((> x).snd)
                 . dropWhile ((/= x) . snd)
                 . zip [toEnum 0..] 

findOrFilter :: (a -> Bool) -> (a -> Bool) -> [a] -> Either a [a]
findOrFilter t p = go 
   where  go []                 = Right []
          go (x:xs) | t x       = Left   x
                    | otherwise = fmap ([x | p x] ++) $ go xs

Тестирование:

> foo 5 [2,3,5,4,6,5,2,1,7,9,2] :: Maybe Int
Just 4
> foo 2 [2,3,5,4,6,5,2,1,7,9,2] :: Maybe Int
Just 1
> foo 1 [3,5,4,6,5,2,1,7,9,2] :: Maybe Int
Just 9

Answer 4

minListIndex :: (Ord a, Num  a) => a -> [a] -> a

Проблема в том, что вы пытаетесь вернуть результат универсального типа a, но на самом деле это индекс в списке.

Предположим, вы пытаетесь оценить свою функцию для списка двойников,В этом случае компилятор должен создать экземпляр типа функции в Double -> [Double] -> Double, что является ерундой.

На самом деле компилятор замечает, что вы возвращаете что-то, полученное из длины списка, и предупреждает вас, что невозможно сопоставить универсальный тип a с бетоном Int.

length ys возвращает Int, так что вы можете попробовать это вместо этого:

minListIndex :: Ord a => a -> [a] -> Int

---

Что касается вашей первоначальной проблемы, кажется, что вы можете 'Т решить это с простой рекурсией.Рассмотрим определение вспомогательной рекурсивной функции с помощью аккумулятора .В вашем случае это может быть пара (min_value_so_far, its_index).