Хаскелл Линейный Поиск (возвращающий индекс)

Question

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

linsearch _ [] = -1
linsearch y (x:xs) = head [i | let j = length xs, i <- [0..j-1], y == x]

Спасибо.

Answer 1

Возврате -1 представлять неудачный поиск - это то, что вы делаете на языке с плохой системой типов. Кроме того, нет причин искать все элементы, если вы заботитесь только о первом. В дальнейшем, head потерпит неудачу, если результирующий список будет пустым.

linsearch :: Eq a => a -> [a] -> Maybe Int
linsearch _ [] = Nothing
linsearch y (x:xs) | y == x = Just 0
                   | otherwise = fmap (+ 1) (linsearch y xs)

Пустой список явно терпит неудачу: return Nothing, С непустым списком проверьте, является ли первый элемент тем, который вы ищете; если так, вернись Just 0, Иначе, y может или не может быть в xs; рекурсивно выяснить. Вы добавите 1 к этому результату для учета xs будучи "сдвинутой" версией исходного списка. Вам нужно использовать fmap потому что вы не будете добавлять 1 к некоторому целому числу y; вы будете добавлять его к "завернутому" значению, как Just yили, возможно, Nothing если y действительно нет в списке. Заметка

fmap (+1) Nothing == Nothing
fmap (+1) (Just 3) == Just 4

Answer 2

TL;DR: решение находится в конце поста.

Вам не нужен шаблон декомпозиции списка в вашем определении, просто разберитесь со списком в целом через понимание списка:

linsearch :: Eq a => a -> [a] -> Int
linsearch _ [] = -1
linsearch y xs = head [i | let j = length xs, i <- [0..j-1],
                           -- y == x  -- x? what is that?
                           y == (xs!!i)]

Сейчас linsearch 3 [0..9] возвращается 3, как это должно. Но linsearch 3 [0..] не возвращается вообще - он теряется при попытке вычислить длину списка, которая на самом деле здесь вообще не нужна! Более того, отказ от вычисления длины заставляет нас перестроить алгоритм из его текущей квадратичной формы в гораздо лучшую линейную форму:

linsearch :: Eq a => a -> [a] -> Int
linsearch _ [] = -1
linsearch y xs = head [i | (x,i) <- zip xs [0..], y == x]

linsearch 3 [0..] теперь успешно возвращается 3, как и должно быть.

linsearch 3 [0,2..] хотя все еще расходится (то есть никогда не возвращается), потому что Haskell не знает - и не хочет этого - что нет смысла искать в упорядоченном увеличивающемся списке, пока не проходит самый первый элемент, который больше, чем тот, который мы ищем за. Это так, потому что [a] тип списков, а не упорядоченных списков.

Мы могли бы также определить такой вариант, например,

linsearchOrdered :: Ord a => a -> [a] -> Int
linsearchOrdered y xs = linsearch y $ takeUntil (> y) xs

takeUntil :: (a -> Bool) -> [a] -> [a]
takeUntil p xs = foldr (\x r -> if not (p x) then x:r else [x]) [] xs

И, конечно же, он работает сейчас:

> linsearchOrdered 3 [0,2..]
*** Exception: Prelude.head: empty list

> takeUntil (> 3) [0,2..]
[0,2,4]
it :: (Ord a, Num a, Enum a) => [a]    

> linsearch 3 [0,2,4]
*** Exception: Prelude.head: empty list

чего ждать? Откуда исходит ошибка? Это происходит от вашего использования head: так как не было 3 нашел в [0,2,4]Код звонка head [] что является ошибкой

Вместо этого мы можем использовать take 1и преобразовать его результат в Maybe a со стандартным использованием listToMaybe:

import Data.Maybe

linsearch :: (Eq a) => a -> [a] -> Maybe Int
linsearch y xs = listToMaybe $ take 1 [i | (x,i) <- zip xs [0..], y == x]

Хорошо, теперь это работает:

> linsearchOrdered 3 [0,2..]
Nothing    

> linsearchOrdered 4 [0,2..]
Just 2

Обратите внимание, что тип возвращаемого значения теперь другой. Вместо использования специального значения мы используем тип обтекания, чтобы указать на успех (с Just) или неудача (с Nothing):

data Maybe a = Nothing | Just a

Если вы действительно хотите свой оригинальный дизайн, мы можем закодировать его как

linsearch y xs = head $ [i | (x,i) <- zip xs [0..], y == x] ++ [-1]

Хаскель так ленив head будет (безопасно, сейчас, с ++ [-1]) остановиться на первом соответствующем элементе (если это вообще возможно). Там почти нет дублирующих усилий, которые будут потрачены впустую, как с использованием head а также takeUntil,

Оба складки, хотя. zip может быть закодирован как сгиб, так что linsearch складка тоже. И композицию сгибов можно объединить в один сгиб, объединив функции редуктора, превратив все это в явно однопроходный алгоритм, если это необходимо.

Answer 3

Есть функция elemIndex в Data.List который делает именно то, что вы хотите. Ваша функция может быть написана следующим образом:

import Data.List
linsearch y xs = elemIndex y xs

elemIndex возвращает Maybe Int, Так зовет linsearch 5 [] доходность Nothing в то время как linsearch 5 [3,4,5] доходность Just 2, Примечание, приведенная выше реализация позволяет отбросить xs: linsearch y = elemIndex y является действительным. Теперь, если вы хотите вернуть только Int мы можем "извлечь" значение из Maybe используя case выражение:

linsearch y xs = caseExtract $ elemIndex y xs
  where
    caseExtract m = case m of
                      Just a  -> a
                      Nothing -> -1

Если вы хотите по-настоящему модно, вы можете пойти "без очков", бросив xs и используя композицию(.) с fromMaybe от Data.Maybe:

import Data.List
import Data.Maybe
linsearch y = fromMaybe (-1) . elemIndex y

Преимущество использования библиотечных функций, таких как elemIndex в том, что они безопасны, в отличие от head который будет бум, если пропущен пустой список. Ссылка: Haskell Report LYAH Data.List reddit небезопасная голова от Maybe