Почему понимание списка Хаскелла не приводит к ошибке при сбое сопоставления с образцом? - PullRequest
Новая
       33

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

20 голосов
/ 16 марта 2009

Я пытаюсь понять, как понимание списка Хаскелла работает "под капотом" в отношении сопоставления с образцом. Следующий вывод 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». Другими словами, шаблон «Just x» не совпадает, поэтому [] используется в качестве заполнителя, пока не будет вызван «concat». Это объясняет, почему «Ничто» кажется пропущенным.

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

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

Ответы [ 3 ]

31 голосов
/ 17 марта 2009

Хотя реализации 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
10 голосов
/ 16 марта 2009

Правило для отладки понимания списка требует выражения вида [ 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 выражения) эквивалентны для списков.

6 голосов
/ 16 марта 2009

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

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

Вот для чего составлено понимание списка: (Ну, я думаю, я на самом деле не проверял его по 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)
...