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

Question

Я пытаюсь понять, как понимание списков 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>

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

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

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

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

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

Answer 1

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

[x | Just x <- myList]

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

do
    Just x <- myList
    return x

...который является:

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

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

Чего я не понимаю, так это откуда Хаскелл знает, что нужно вызывать функцию "fail"?

В do-нотации, если происходит сбой привязки шаблона (т.е.в 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

Answer 2

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

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

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

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

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

do { p <- l; return e }

который десугары Для

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

Когда мы берем монаду списка, мы имеем

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

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

Answer 3

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

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

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

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

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

---

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

---

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

Вы могли бы передать это в f функция из приведенного выше кода, но чем select имел бы такой тип:

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

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

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

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