Почему недопустимые ошибки в списке Haskell вызывают ошибку при совпадении с совпадением шаблона?

Я пытаюсь понять, как интерпретации списка Haskell работают "под капотом" в отношении соответствия шаблонов. Следующий вывод ghci иллюстрирует мою точку зрения:

Prelude> let myList = [Just 1, Just 2, Nothing, Just 3]
Prelude> let xs = [x | Just x <- myList]
Prelude> xs
[1,2,3]
Prelude>

Как вы можете видеть, он может пропустить "Nothing" и выбрать только "Just". Я понимаю, что Список - это монада, определяемая как (источник из Real World Haskell, глава 14):

instance Monad [] where
    return x = [x]
    xs >>= f = concat (map f xs)
    xs >> f = concat (map (\_ -> f) xs)
    fail _ = []

Таким образом, понимание списка в основном создает одноэлементный список для каждого элемента, выбранного в понимании списка, и объединяет их. Если совпадение шаблона не выполняется на некотором шаге, вместо этого используется результат функции "fail". Другими словами, шаблон "Just x" не совпадает, поэтому [] используется в качестве заполнителя, пока не будет вызвано "concat". Это объясняет, почему "Nothing" кажется пропущенным.

То, что я не понимаю, как Хаскелл знает, чтобы вызвать функцию "fail"? Это "магия компилятора" или функциональность, которую вы можете написать в Haskell? Можно ли написать следующую функцию "select", чтобы работать так же, как понимание списка?

select :: (a -> b) -> [a] -> [b]
select (Just x -> x) myList       -- how to prevent the lambda from raising an error?
[1,2,3]

Ответы

Ответ 1

В то время как реализация Haskell может не делать это прямо так, как это внутренне, полезно подумать об этом следующим образом:)

[x | Just x <- myList]

... становится:

do
    Just x <- myList
    return x

... который есть:

myList >>= \(Just x) -> return x

Что касается вашего вопроса:

Я не понимаю, как Haskell знает, как вызвать функцию "fail"?

В do-notation, если сбой привязки шаблона (т.е. Just x), вызывается метод fail. В приведенном выше примере это выглядит примерно так:

myList >>= \temp -> case temp of
    (Just x) -> return x
    _        -> fail "..."

Итак, каждый раз, когда у вас есть соответствие шаблонов в монадическом контексте, который может завершиться неудачно, Haskell вставляет вызов fail. Попробуйте с помощью IO:

main = do
    (1,x) <- return (0,2)
    print x -- x would be 2, but the pattern match fails

Ответ 2

Правило для обесцвечивания понимания списка требует выражения формы [ e | p <- l ] (где e - выражение, p шаблон и l выражение списка) ведут себя как

let ok p = [e]
    ok _ = []
in concatMap ok l

Предыдущие версии Haskell содержали monad assrehensions, которые были удалены с языка, потому что их было трудно читать и избыточно с помощью do - нотации. (Смысл списков тоже избыточный, но их не так сложно прочитать.) Я думаю, что desugaring [ e | p <- l ] как монада (или, точнее, как монада с нулем) даст что-то вроде

let ok p = return e
    ok _ = mzero
in l >>= ok

где mzero - из класса MonadPlus. Это очень близко к

do { p <- l; return e }

который desugars для

let ok p = return e
    ok _ = fail "..."
in l >>= ok

Когда мы берем Monad List, имеем

return e = [e]
mzero = fail _ = []
(>>=) = flip concatMap

I.e., 3 подхода (понимание списков, понимание монады, выражения do) эквивалентны для списков.

Ответ 3

Я не думаю, что синтаксис понимания списка имеет много общего с тем фактом, что List ([]) или Maybe, если на то пошло, является экземпляром класса типа Monad.

Пояснения к спискам - это действительно магия компилятора или синтаксический сахар, но это возможно, потому что компилятор знает структуру типа данных [].

Вот то, что компилируется в список: (Ну, я думаю, я фактически не проверял его против GHC)

xs = let f = \xs -> case xs of
                      Just x -> [x]
                      _      -> []
     in concatMap f myList

Как вы можете видеть, компилятор не должен вызывать функцию fail, он может просто вставить пустой список, потому что он знает, что такое список.

Интересно, что тот факт, что синтаксис синтаксиса "пропускает" шаблоны соответствует неудачам, используется в некоторых библиотеках для выполнения общего программирования. См. Пример в Uniplate library.

Изменить: О, и чтобы ответить на ваш вопрос, вы не можете вызвать свою функцию select с помощью лямбда, которую вы ей дали. Он действительно завершится неудачей при сбое совпадения шаблонов, если вы вызываете его с помощью значения Nothing.

Вы можете передать ему функцию f из приведенного выше кода, но <<26 > будет иметь тип:

select :: (a -> [b]) -> [a] -> [b]

что отлично, вы можете использовать функцию concatMap внутри: -)

Кроме того, этот новый select теперь имеет тип монадического оператора привязки для списков (с перевернутыми аргументами):

(>>=) :: [a] -> (a -> [b]) -> [b]
xs >>= f = concatMap f xs -- 'or as you said: concat (map f xs)