понедельник, 15 сентября 2014 г.

Вью-паттерны (view patterns) в haskell на конкретном примере

Как перевести на русский язык view patterns я, честно говоря, не знаю. Образцы с представлением? Образцы с функциональным преобразованием? Чтобы случайно не исказить смысл этих объектов, я буду называть их просто вью-паттернами. Хотя смысл, в общем-то, простой: части общего образца заменяются вызовами функций, которые возвращают объекты произвольного типа — эти объекты представлены в виде образцов, элементы которых, как обычно, связываются с переменными в теле основной функции. Такие функции называются view, а образцы, на которые они указывают (с помощью стрелочки ->) — view patterns. Подробнее о вью-паттернах можно узнать здесь. Вот конкретный пример. Возьмем многострадальный фильтр для pandoc. В нем есть (или уже был, если я решу закоммитить новое решение) участок
substInlineStyle :: Format -> MMap -> Inline -> Inline
substInlineStyle fm m i@(Image ((Style style):alt) (src, title)) =
    substInlineStyle' fm m style (alt, src, title) i
substInlineStyle fm m i@(Link ((Style style):alt) (src, title)) =
    substInlineStyle' fm m style (alt, src, title) i
substInlineStyle _ _ i = i

substInlineStyle' :: Format -> MMap -> String -> ObjParams -> Inline -> Inline
substInlineStyle' (Format fm) m style params i
    | Just (MetaMap mm) <- M.lookup style m
    , Just (MetaBlocks [Para ((RawInline f s):r)]) <- M.lookup fm mm =
        let subst (Style "ALT") = RawInline f "$ALT$"
            subst i = i
        in RawInline f $ substParams fm params $
                                s ++ stringify' fm (map subst r)
    | otherwise = i
Что мне здесь не нравится? Первый и второй клозы функции substInlineStyle отличаются только именем конструктора в образце (Image и Link), больше эти имена нигде не фигурируют. Оба конструктора имеют одинаковые аргументы [Inline] Target (так они определены в pandoc). Так почему бы не избавиться от этих конструкторов таким образом, чтобы объединить первый и второй клозы substInlineStyle в одну функцию? Однако, плейсхолдеры конструкторов в образцах в haskell не используются, охранные выражения с образцами (см. предыдущую статью) здесь тоже бесполезны (они всё так же не смогут убрать имена конструкторов или заменить их плейсхолдерами). А чем здесь могут помочь вью-паттерны? Ну, они могут заменить тип Inline с его конструкторами Image и Link на какой-нибудь новый тип, например, кортеж из двух аргументов этих конструкторов, обернутый в Maybe!
substInlineStyle :: Format -> MMap -> Inline -> Inline
substInlineStyle (Format fm) m
                 i@(getInlineParams -> Just (((Style style):alt), (src, title)))
    | Just (MetaMap mm) <- M.lookup style m
    , Just (MetaBlocks [Para ((RawInline f s):r)]) <- M.lookup fm mm =
        let params = (alt, src, title)
            subst (Style "ALT") = RawInline f "$ALT$"
            subst i = i
        in RawInline f $ substParams fm params $
                                s ++ stringify' fm (map subst r)
    | otherwise = i
substInlineStyle _ _ i = i

getInlineParams :: Inline -> Maybe ([Inline], Target)
getInlineParams (Image alt target) = Just (alt, target)
getInlineParams (Link alt target) = Just (alt, target)
getInlineParams _ = Nothing
Еще один вариант — искать стиль сразу в getInlineParams и возвращать из нее кортеж из трех элементов — стиля, списка alt и элемента target.
substInlineStyle :: Format -> MMap -> Inline -> Inline
substInlineStyle (Format fm) m
                 i@(getInlineParams -> Just (Style style, alt, (src, title)))
    | Just (MetaMap mm) <- M.lookup style m
    , Just (MetaBlocks [Para ((RawInline f s):r)]) <- M.lookup fm mm =
        let params = (alt, src, title)
            subst (Style "ALT") = RawInline f "$ALT$"
            subst i = i
        in RawInline f $ substParams fm params $
                                s ++ stringify' fm (map subst r)
    | otherwise = i
substInlineStyle _ _ i = i

getInlineParams :: Inline -> Maybe (Inline, [Inline], Target)
getInlineParams (Image (style@(Style _):alt) target) = Just (style, alt, target)
getInlineParams (Link (style@(Style _):alt) target) = Just (style, alt, target)
getInlineParams _ = Nothing
Вот и всё! Нам удалось выбросить имена Image и Link из substInlineStyle и благодаря этому объединить два ее клоза в один. Правда, пришлось добавить новую вью-функцию getInlineParams, но в любом случае возможности и семантика нового решения стали намного богаче. Во-первых, вью-функцию можно спрятать в библиотеку (или же, в общем случае, эта функция может быть предоставлена библиотекой, либо являться стандартной), во-вторых, вью-функция может производить важные семантические изменения данных, а не просто выдергивать данные из конструкторов, как в нашем случае. Вот просто потрясающий пример, иллюстрирующий второе утверждение (найден здесь):
endpoints (sort -> begin : (reverse -> end : _)) = Just (begin, end)
endpoints _ = Nothing
Эта штука находит минимальный и максимальный элементы в произвольном списке, предварительно сортируя этот список прямо в образце! А представьте что будет, если это скрестить с синонимами образцов!
pattern Sort begin end <- (sort -> begin : (reverse -> end : _))

endpoints (Sort begin end) = Just (begin, end)
endpoints _ = Nothing

min (Sort begin _) = Just begin
min _ = Nothing

max (Sort _ end) = Just end
max _ = Nothing
Сплошное очарование. Обратите внимание: несмотря на то, что функции endpoints, min и max ожидают на входе список, переменные их образцов связаны с конкретными элементами списка — концами begin и end. Осталось сказать, что поскольку вью-паттерны являются нестандартным расширением, то для их использования в начало программы следует добавить прагму
{-# LANGUAGE ViewPatterns #-}
, либо при компиляции указать опцию -XViewPatterns.

пятница, 12 сентября 2014 г.

Охранные выражения с образцом (pattern guards) в haskell на конкретном примере

Я опять переписал фильтр для pandoc, о котором рассказывал здесь и здесь. Давайте посмотрим на оригинальное определение первого клоза функции substStyle.
substStyle (Format fm) m b@(Para [Image ((Style style):alt) (src, title)]) =
    case M.lookup style m of
        Nothing -> b
        Just (MetaMap mm) ->
            let params = (alt, src, title)
            in case M.lookup fm mm of
                   Nothing -> b
                   Just (MetaBlocks [RawBlock f s]) ->
                       RawBlock f $ substParams fm params s
                   Just (MetaBlocks [mb]) ->
                       walk substParams' mb
                       where substParams' (RawInline f s) =
                                   RawInline f $ substParams fm params s
                             substParams' i = i
                   Just _ -> b
        Just _ -> b
Смысл этой функции простой: вернуть новое форматирование в случае, если имя style было найдено в списке объектов метаданных документа (результат Just (MetaMap mm) в первом выражении case) и представление найденного объекта метаданных соответствует MetaBlocks [RawBlock f s] (для встроенного кода latex) или просто MetaBlocks [mb] (для встроенного кода html) как результат проверки второго case. Несмотря на то, что нас фактически интересуют только эти два условия (в остальных случаях мы просто вернем исходный блок b), использование вложенных case привело к формированию неоправданно разросшегося куста с шестью ветвями, четыре из которых в общем-то ничего полезного не делают (просто возвращают b). Как бы нам подрезать ненужные ветви? Оказывается, в haskell есть механизм, который позволит решить эту задачу. Это охранные выражения с образцом (я попытался перевести pattern guards без искажения семантики этих объектов). Документация доступна здесь. Несмотря на то, что охранные выражения с образцом являются синтаксическим расширением, никакие дополнительные флаги компиляции для их использования не требуются, поскольку они были включены в стандарт Haskell 2010. В упомянутой выше документации приводится пример с двумя последовательными поисками в отображении: как раз то, что нам нужно. Вот результат трансляции кейсов из substStyle в охранные выражения.
substStyle (Format fm) m b@(Para [Image ((Style style):alt) (src, title)])
    | Just (MetaMap mm) <- M.lookup style m
    , Just (MetaBlocks [mb]) <- M.lookup fm mm =
        let params = (alt, src, title)
            substStyle' mb
                | RawBlock f s <- mb =
                    RawBlock f $ substParams fm params s
                | otherwise =
                    let substParams' (RawInline f s) =
                                RawInline f $ substParams fm params s
                        substParams' i = i
                    in walk substParams' mb
        in substStyle' mb
    | otherwise = b
Итак, новая функция substStyle реализована с помощью охранных выражений с образцом, в которых последовательно ищутся значение style в метаданных документа и (на основе уже найденного объекта-стиля mm!) представление стиля в метаданных. Если представление стиля соответствует MetaBlocks [mb], то, с помощью функции substStyle’, которая тоже реализована с помощью охранных выражений с образцом, выполняется подстановка шаблона стиля в документ. Хочу также отметить, что в данном случае let-выражения нельзя заменить словом where, поскольку последнее может быть использовано только после перечисления всех охранных выражений функции, таким образом замена внешнего let на where приведет просто к ошибке компиляции, ну а в случае с внутренним let его замена на where слегка изменит семантику: программа в общем-то скомпилируется, поскольку where будет стоять после всех охранных выражений, однако все объявления внутри него (то есть функция substParams’) будут видны во всех ветвях охранных выражений — а зачем нам это надо? Оставшиеся трансляции case в pattern guards. Из
substStyle (Format fm) m b@(Para cnt) =
    let walk' = walk $ substInlineStyle (Format fm) m
    in case M.lookup "para_style" m of
           Nothing -> walk' b
           Just (MetaMap mm) ->
               case M.lookup fm mm of
                   Nothing -> walk' b
                   Just (MetaBlocks [Para [Span attr _]]) ->
                       walk' $ Plain [Span attr cnt]
                   Just _ -> walk' b
           Just _ -> walk' b
в
substStyle (Format fm) m b@(Para cnt)
    | Just (MetaMap mm) <- M.lookup "para_style" m
    , Just (MetaBlocks [Para [Span attr _]]) <- M.lookup fm mm =
        walk' $ Plain [Span attr cnt]
    | otherwise = walk' b
    where walk' = walk $ substInlineStyle (Format fm) m
(здесь мы использовали where, поскольку объявленная в нем функция walk’ должна быть доступна во всех ветвях охранных выражений). Из
substInlineStyle' (Format fm) m style params i =
    case M.lookup style m of
        Nothing -> i
        Just (MetaMap mm) ->
            case M.lookup fm mm of
                Nothing -> i
                Just (MetaBlocks [Para ((RawInline f s):r)]) ->
                    RawInline f $ substParams fm params $
                                    s ++ stringify' fm (map subst r)
                    where subst (Style "ALT") = RawInline f "$ALT$"
                          subst i = i
                Just _ -> i
        Just _ -> i
в
substInlineStyle' (Format fm) m style params i
    | Just (MetaMap mm) <- M.lookup style m
    , Just (MetaBlocks [Para ((RawInline f s):r)]) <- M.lookup fm mm =
        let subst (Style "ALT") = RawInline f "$ALT$"
            subst i = i
        in RawInline f $ substParams fm params $
                                s ++ stringify' fm (map subst r)
    | otherwise = i
Итак, мы заменили все case на охранные выражения, сократили код на 12 строк и сделали его более понятным. По-моему, это вин! Update. Реализовав локальную функцию substStyle’ в первом клозе substStyle с помощью охранных выражений, я, честно говоря, перестарался. В самом деле, какой смысл вытаскивать образец из связанной переменной, если эту переменную можно изначально представить в виде декомпозиции с интересующим нас конструктором? Использование охранных выражений с образцом в этом случае — это просто ненатуральный аналог сопоставления с образцом. Таким образом, первый клоз substStyle следует переписать так:
substStyle (Format fm) m b@(Para [Image ((Style style):alt) (src, title)])
    | Just (MetaMap mm) <- M.lookup style m
    , Just (MetaBlocks [mb]) <- M.lookup fm mm =
        let params = (alt, src, title)
            substStyle' (RawBlock f s) = RawBlock f $ substParams fm params s
            substStyle' b = walk substParams' b
                where substParams' (RawInline f s) =
                            RawInline f $ substParams fm params s
                      substParams' i = i
        in substStyle' mb
    | otherwise = b
И substParams’ теперь можно определить внутри блока where, поскольку два определения substStyle’ стали лексически независимы, в отличие от случая с охранными выражениями.

среда, 10 сентября 2014 г.

Ограничение мономорфным типом (monomorphism restriction) в haskell на конкретном примере

Дело было вечером, делать было нечего… Загрузил я ghci, чтобы немного развлечься.
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> let f = map (3*)
Prelude> :t f
f :: [Integer] -> [Integer]
Что за фигня, подумал я. Функция f не полиморфна! Но ведь это значит, что я не смогу ее применить, например, к списку вещественных чисел!
Prelude> let a = f [1.2, 3.4]

<interactive>:4:12:
    No instance for (Fractional Integer) arising from the literal `1.2'
    Possible fix: add an instance declaration for (Fractional Integer)
    In the expression: 1.2
    In the first argument of `f', namely `[1.2, 3.4]'
    In the expression: f [1.2, 3.4]
Так и есть. Попробуем с оригинальной полиморфной функцией map.
Prelude> :t map (3*)
map (3*) :: Num b => [b] -> [b]
Prelude> let b = map (3*) [1.2, 3.4]
Prelude> b
[3.5999999999999996,10.2]
Все работает, никаких неожиданностей. Неожиданностью остается обращение компилятора с функцией f. Давайте объявим аналогичную функцию f’ с явным указанием ожидаемого для нее полиморфного типа.
Prelude> :{
Prelude| let f' :: Num a => [a] -> [a]
Prelude|     f' = map (3*)
Prelude| :}
Prelude> let c = f' [1.2, 3.4]
Prelude> c
[3.5999999999999996,10.2]
Ух, сработало! Не все так плохо. Но почему же компилятор по умолчанию сужает исходный полиморфный тип функции map (3*) до конкретного [Integer] -> [Integer] в функции f? Как выяснило следствие, данный эффект обусловлен правилом ограничения мономорфным типом (monomorphism restriction), включенном в ghc по умолчанию. Главный довод для включения этого правила — обеспечение однократного вычисления значений внутри let и where, как этого обычно ожидает пользователь. Например, len в
f xs = (len, len)
       where len = genericLength xs
может быть вычислена более одного раза без включения ограничения мономорфным типом. Я взял данный пример из этой статьи — в ней объясняется почему такое может произойти. В Haskell Report проливается свет на условия применения ограничения мономорфным типом. В частности, Rule 1.(a) утверждает, что если мы свяжем все переменные в определении функции, то ее тип должен остаться полиморфным. Проверяем.
Prelude> let g x = map (3*) x
Prelude> :t g
g :: Num b => [b] -> [b]
Работает! А теперь удостоверимся, что исходное определение функции f при выключенном ограничении мономорфным типом станет полиморфным.
Prelude> :set -XNoMonomorphismRestriction 
Prelude> let f'' = map (3*)
Prelude> :t f''
f'' :: Num b => [b] -> [b]
Prelude> let d = f'' [1.2, 3.4]
Prelude> d
[3.5999999999999996,10.2]

суббота, 6 сентября 2014 г.

Синонимы образцов (pattern synonyms) в ghc-7.8 на конкретном примере

В предыдущей статье был представлен фильтр для pandoc, который позволяет настраивать стили изображений. В дальнейшем возможности фильтра были расширены и новая версия размещена на github. Основное нововведение — это возможность ссылаться на определение стиля, объявленного в метаданных документа, прямо из ссылки на изображение в исходном документе. Например, ссылка
![$img_style$ *Пример изображения*](../images/gnome-terminal-italic.png)
без использования фильтра styleFromMeta будет оформлена с альтернативным текстом img_style Пример изображения, причем запись img_style будет рассматриваться как встроенная математическая запись (inline math), поскольку она окружена символами доллара. Фильтр styleFromMeta проверяет, не начинается ли содержимое внутри квадратных скобок в определениях ссылок (и не только на изображения) со встроенной математической записи, и если это так, то пытается найти объект с именем этой записи в метаданных документа. В случае удачного поиска найденный объект подставляется в выходной документ с возможной заменой плейсхолдеров $ALT$, $SRC$ и $TITLE$ на значения из определения ссылки. Вместо $ALT$ подставляется остаток содержимого внутри квадратных скобок определения ссылки без начальных пробелов. В нашем примере значению $ALT$ будет соответствовать строка Пример изображения. Алгоритм поиска ссылок с возможным указанием на требуемый стиль реализуется с помощью сопоставления с образцом (pattern matching). Например, так.
substStyle :: Format -> MMap -> Block -> Block
substStyle (Format fm) m
           b@(Para [Image ((Math InlineMath style):alt) (src, title)]) =
Я не привел тело функции, поскольку к обсуждаемой проблеме оно не имеет отношения. Тип MMap объявлен как
type MMap = M.Map String MetaValue
, он соответствует способу хранения метаданных документа в pandoc. Главная проблема определения substStyle состоит в необходимости записывать образец для поиска стиля как Math InlineMath style. Но ведь это же просто деталь реализации! Просто так совпало, что мы выбрали обрамление долларами для отметки ссылок на стиль, и ссылки эти не имеют никакого отношения к встроенным математическим записям. Иными словами, использование оригинальных имен конструкторов в данном случае искажает семантику образца и не отражает наше намерение использовать его для извлечения ссылок на стиль. Определение
substStyle (Format fm) m b@(Para [Image ((Style style):alt) (src, title)]) =
выглядело бы гораздо лучше. Провернуть такой трюк позволит новое синтаксическое расширение Синонимы образцов (pattern synonyms), появившееся в ghc-7.8. Выражение Style в новом определении substStyle можно объявить как синоним образца.
pattern Style x <- Math InlineMath x
В данном случае мы объявили односторонний (unidirectional) синоним образца: для определения таких синонимов используется символ <-. Двухсторонние (bidirectional) синонимы объявляются с помощью символа =. Разница между двумя типами синонимов образцов простая: односторонние синонимы можно использовать только для сопоставления с образцом, в то время как двухсторонние — как обычные выражения. Подробнее о синонимах образцов можно узнать здесь. Все это хорошо, но что делать, если у нас в наличии старый компилятор ghc? Он не поймет, что это за объявление pattern Style x и что за Style объявлен в определении функции styleFromMeta. В нашем случае проблема легко решается введением условной компиляции и применением макросов cpp. В самом начале программы добавим объявления
{-# LANGUAGE CPP #-}
#if __GLASGOW_HASKELL__ >= 708
{-# LANGUAGE PatternSynonyms #-}
#endif
В первой строке заявлено, что мы хотим использовать препроцессор cpp. Далее, если версия ghc не древнее 7.8, мы включаем расширение PatternSynonyms. После объявлений импортов модулей вставляем строки
#if __GLASGOW_HASKELL__ >= 708
pattern Style x <- Math InlineMath x
#else
#define Style Math InlineMath
#endif
Если компилятор ghc древнее версии 7.8, то препроцессор cpp заменит слово Style на два слова Math InlineMath во всем исходном коде программы непосредственно перед ее компиляцией.