Хаскель Линейный Поиск (возвращающий индекс) - PullRequest
Новая
       18

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

0 голосов
/ 26 сентября 2018

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

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

Спасибо.

Ответы [ 3 ]

0 голосов
/ 26 сентября 2018

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: поскольку в [0,2,4] не было найдено 3, вы кодируете вызовы 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]

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

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

0 голосов
/ 27 сентября 2018

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

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 LYAH Data.List reddit небезопасная голова от Maybe

0 голосов
/ 26 сентября 2018

Возвращение -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
...