Жизнь на свободе Голосов: 1 Адрес блога: http://sovety.blogspot.com/ Добавлен: 2008-02-19 12:40:29 блограйдером Lurk

Как аппликативные функторы с if-ами боролись

2010-10-01 16:26:00 (читать в оригинале)



На днях заметил, как полезны могут быть аппликативные функторы для избавления от леса вложенных условных конструкций (if-ов и case-ов). А именно, как удобно, что тип Maybe можно использовать как аппликативный функтор.

О функторах, пирогах и яблоках

Речь пойдёт о языке Хаскель, но постараюсь рассказать так, чтобы пользователям других языков было тоже понятно. Кто Хаскель знает, этот раздел может пропустить и сразу перейти к следующему.

Итак, для представления такого результата, которого может и не быть, в Хаскеле используется тип Maybe a, где a — любой тип. У Maybe a бывают значения двух видов: Just a («просто а», если значение есть) и Nothing («ничего», если значения нет). Maybe является функтором, то есть из любой функции из a в b (тип :: a -> b) можно сделать функцию из Maybe a в Maybe b (тип :: Maybe a -> Maybe b). В общем, функтором является любой тип f, для которого определена^*:

fmap :: (a -> b) -> (f a -> f b)

^* определение fmap должно удовлетворять при этом двум условиям: 1) fmap id = id, где id — функция, возвращаюая свой аргумент, 2) fmap должна быть дистрибутивна слева относительно композиции функций... [ссылка]

Например, пусть у нас есть типы Яблоко и Пирог и функция испечь :: Яблоко -> Пирог, превращающая одно в другое. Тогда мы легко можем взять яблоко, которого может и не быть, и испечь из него пирог, , которого может и не быть. То есть если будет просто яблоко, то выйдет просто пирог, а если ничего не было, то ничего и не выйдет. Делается это проще простого: fmap испечь.

data Яблоко = Яблоко deriving Show
data Пирог = Пирог deriving Show

испечь :: Яблоко -> Пирог
испечь Яблоко = Пирог

испечьЕслиЕсть :: (Maybe Яблоко) -> (Maybe Пирог)
испечьЕслиЕсть = fmap испечь

После этого мы можем печь пироги, которых может и не быть:

ghci> испечьЕслиЕсть (Just Яблоко)
Just Пирог
ghci> испечьЕслиЕсть Nothing
Nothing

А что делать, если самой функции из a в b может и не быть? Как применить Maybe (a -> b) к Maybe a? Такая операция определена для аппликативных функторов, Maybe — один из них. В Хаскеле для этого подключают модуль Control.Applicative, саму же операцию последовательного применения называют звучным словом (<*>).

Поясняю на яблоках. Что делать случае на входе у нас Maybe (Яблоко -> Пирог) — рецепт, которого может и не оказаться? Естественно, что пирог у нас получится тогда и только тогда, когда есть и яблоко, и сам рецепт. Если хоть что-то отсутствует, то и пирога не будет, будет Nothing. Итак, дано:

безРецепта = Nothing
сРецептом = Just испечь

Проверяем, как работает с такими «рецептами» аппликативный функтор Maybe:

ghci> :m + Control.Applicative
ghci> сРецептом <*> Just Яблоко
Just Пирог
ghci> сРецептом <*> Nothing
Nothing
ghci> безРецепта <*> Just Яблоко
Nothing
ghci> безРецепта <*> Nothing
Nothing

Это всё, что нам сейчас потребуется из «теории». И ещё пара замечаний: 1) с аппликативными функторами часто применяется ещё операция (<$>), которая является для них синонимом fmap и в инфиксной записи выглядит короче; 2) любая монада является также аппликативным функтором (обратное неверное), и для неё ap и (<*>) совпадают (об этом полезно знать, хотя нам сейчас и не потребуется).

Избавление от условных конструкций

Перехожу к практическим вопросам. На днях писал небольшой парсер для файлов формата Matrix Market. Это несложный формат, состоящий из заголовка в котором указывается, как хранится структура матрицы (покоординатно или сплошным массивом) и тип значений её элементов (целые, действительные или комплексные). Возможны разные комбинации.

Логику разбора такого формата на императивном псевдокоде можно описать так:

if (структура == координатная) {
    if (тип == целые) {
        читатьЦелыеПоКоординатам;
    } else if (тип == действительные) {
        читатьДействительныеПоКоординатам;
    } else if (тип == комплексные) {
        читатьКомплексныеПоКоординатам;
    } else {
        ошибка;
    }
} else if (структура == массив) {
    if (тип == целые) {
        читатьМассивЦелых;
    } else if (тип == действительные) {
        читатьМассивДействительных;
    } else if (тип == комплексные) {
        читатьМассивКомплексных;
    } else {
        ошибка;
    }
} else {
    ошибка;
}

Естественно, что такого развесистого дерева выбора можно избежать, потому что выбор типа элементов и выбор структуры матрицы независимы друг от друга. В функциональном стиле можно просто составить «словарь» поддерживаемых функций для разбора структуры и отдельный «словарь» функций для чтения значений разных типов, выбирать подходящие, и потом передавать вторые в качестве параметра первым. Так я и сделал.

Опять псевдокод для пояснения этой идеи:

let читатьСтруктуру = lookup структура словарьФункцийРазбора
    читатьЧисло = lookup тип словарьФункцийРазбораЧисла
in  читатьСтруктуру читатьЧисло исходныеДанные

На практике дело обстоит немного сложнее. Операция поиска в словаре может ничего не найти. Как легко догадаться, lookup в Хаскеле возвращает Maybe a. Итак, у нас есть Maybe функция, Maybe аргумент, а мы хотим получить Maybe результат. Ничего не напоминает? Да-да, тут самое время применить (<*>).

Однако представим на минуту, как эта задача решается без операции последовательного применения Maybe a. И для функции, и для её аргумента нужно проверять являются ли они чем-то (Just a) или ничем (Nothing), и в результате получается тот же лес проверок, что и в императивном псевдокоде, только в этот раз с проверкой на результат поиска. Можно, правда, все проверки объединить в одной единственной условной конструкции на каждое применение функции, но все проверки надо всё равно записывать явно. То есть без (<*>) получается что-то такое:

let читатьСтруктуру = lookup структура словарьФункцийРазбора
    читатьЧисло = lookup тип словарьФункцийРазбораЧисла
in  case (читатьСтруктуру, читатьЧисло) of
      (Just f, Just g) -> Just (f g исходныеДанные)
      _                -> Nothing

Код склонен паталогически ветвиться, если таких Maybe-аргументов у функции больше одного, или если полученный Maybe-результат нужно использовать в качестве аргумента ещё одной функции (тут не обойтись без вложенных проверок).

К счастью, все эти проверки тривиальны, и код можно записать гораздо короче:

let читатьСтруктуру = lookup структура словарьФункцийРазбора 
    читатьЧисло = lookup тип словарьФункцийРазбораЧисла 
in  читатьСтруктуру <*> читатьЧисло <*> (Just исходныеДанные)

Здесь нет ни одной явной условной конструкции, но код, тем не менее, делает все необходимые проверки, и вернёт Just результат только если нашлись обе функции.

У меня получилось немного длиннее, но суть та же:

let p = lookup fmt parsers        :: Maybe FormatReader
    nr = lookup fieldq readers    :: Maybe (Int, ValueReader)
    sy = lookup symq symmetries   :: Maybe Symmetry
    p' = uncurry <$> p <*> nr     :: Maybe ([String] -> Maybe MatrixData)
    d = join $ p' <*> (Just toks) :: Maybe MatrixData
    m = MM <$> d <*> sy           :: Maybe Matrix
in ...

Что тут можно заметить. Во-первых, (<$>) практически так же часто используется, как и (<*>). Эта операция позволяет применять обычные функции к Maybe-значениям. Вместо (<$>) можно поднимать значения в функтор с помощью pure (для любых аппликативных функторов) или Just (конкретно для Maybe) и использовать только (<*>).

Во-вторых, если у нас кругом функции, возвращающие Maybe, и они сами оказываются внутри Maybe (см. p' в моём примере), то рано или поздно появляются «вложенные» значения типа Maybe (Maybe a). Тут помогает монадный join, превращающий их в просто Maybe a. join определён в Control.Monad. И кстати, это тоже помогает избавиться от вложенных тривиальных проверок (join (Just Nothing) даёт Nothing).

В-третьих, при таком подходе мы, естественно, теряем информацию о том, какое именно вычисление не дало результата (дало Nothing). Для передачи «исключения» по цепочке можно использовать другие типы, например Either e, определив для них Applicative.

Заключение

Мне такой способ комбинировать вычисления очень понравился. По-моему, случай, когда все условные проверки сводятся к «если в порядке, то считать дальше, а если нет, то прервать» — довольно распространённый. Тип Maybe с операцией последовательного применения (<*>) позволяет такие проверки, любой степени вложенности, не писать вообще.