Фильтр HaskellM с фильтромM (\ x → [True, False]) [1, 2, 3]

Я просто не могу понять волшебство, которое Haskell делает с этим вариантом использования filterM. Исходный код для этой функции приведен ниже:

filterM          :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
filterM _ []     =  return []
filterM p (x:xs) =  do
    flg <- p x
    ys  <- filterM p xs
    return (if flg then x:ys else ys)

В этом случае p должна быть лямбда-функцией (\x -> [True, False]), а первая x должна быть 1. Итак, что возвращает flg <- p x? Что такое значение flg для каждой рекурсии?

Ответы

Ответ 1

Список monad [] моделирует недетерминизм: список значений [a] представляет собой ряд различных возможностей для значения a.

Когда вы увидите инструкцию типа flg <- p x в монаде списка, flg будет принимать каждое значение p x по очереди, т.е. True, а затем False в этом случае. Остальная часть тела filterM выполняется дважды, один раз для каждого значения flg.

Чтобы узнать, как это происходит более подробно, вам нужно понять десурацию нотации do и реализацию оператора (>>=) для монады списка.

Обозначение

do выводится поочередно по вызовам оператора (>>=). Например, тело непустого случая filterM превращается в

p x >>= \flg -> (filterM p xs >>= \ys -> return (if flg then x:ys else ys))

Это полностью механически, поскольку он по сути просто заменяет flg <- перед выражением >>= \flg -> после выражения. На самом деле соответствие шаблонов делает это немного сложнее, но не так много.

Далее приведена фактическая реализация (>>=), которая является членом класса типа Monad и имеет различную реализацию для каждого экземпляра. Для [], тип:

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

и реализация - это что-то вроде

[] >>= f = []
(x:xs) >>= f = f x ++ (xs >>= f)

Итак, цикл происходит в теле (>>=). Это все в библиотеке, без магии компилятора за десурагированием нотации do.

Эквивалентное определение для (>>=) есть

 xs >>= f = concat (map f xs)

который также может помочь вам понять, что происходит.

То же самое происходит для рекурсивного вызова filterM: для каждого значения flg выполняется рекурсивный вызов и создается список результатов, а заключительный оператор return выполняется для каждого элемента ys в этом списке результатов.

Этот "разветвление" для каждого рекурсивного вызова приводит к 2^3 = 8 элементам в конечном результате filterM (\x -> [True, False]) [1, 2, 3].