Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Categories:

Монадическое и другие обобщения fmap

Пишу я, значит, прототип оптимизатора для HN+1 (HN+1 = HN0 + инлайнер и инстанциатор)

HN0 не то чтобы готов к эксплуатации, но мне внезапно стало скучно и захотелось чего-нибудь эдакого. Эдаким оказалась бета-библиотека для написания оптимизаторов basic blocks под названием HOOPL, релиз которой даже намереваются присобачить к следующей версии GHC. 

Ну, я решил выпендриться и использовать её для оптимизации аппликативного кода HN0 вместо императивных basic blocks, для которых она была разработана (внутри  GHC её прототип оптимизировал ассемблерную лапшу С--).

Так вот, HOOPL оптимизирует граф control flow (на самом деле произвольный граф, но есть поддержка для узлов с одним входящим и/или одним выходящим ребром, специфичная для графов из  ассемблерных инструкций). А у меня никакого графа control flow нет - только AST.
 
Решил я переделать AST в граф - а для этого нужно заменить в нем неуникальные строковые идентификаторы на уникальные метки особого типа Label, определенного внутри Hoopl, а уникальность обеспечить посредством монады UniqueMonad с методом freshUnique, определенной опять же внутри HOOPL.

Упрощая для целей данного поста, получаем такой AST:

data Expression a = Atom a | Application (Expression a) (Expresion a) | Constant Int

Мне нужно реализовать функцию

withUniqueLabels :: MyMonadTransformer m => Expression String -> m (Expression Label)

Я её реализовал, но возник резонный вопрос: есть ли обобщенная её версия в стандартной библиотеке?

Понятно, что Expression - это функтор (в смысле Data.Functor). Можно реализовать операцию fmap, применяющую функцию-аргумент к каждому "атому" внутри и конструирующую новое дерево идентичное по форме и веткам Constant.

Но также можно реализовать "zip", cклеивающую два дерева, отличающиеся лишь атомами, и "mapAccum", выполняющую параллельный fmap и склеивание элементов в некий результат (в моем случае в новое состояние генератора уникальных меток).

Хочу я withUniqueLabels реализовать так:

withUniqueLabels a = mapAccum f a where
    f :: MyMonadTransformer m => Atom String -> m () -> m Label
    f = ...

Мои вопросы господину Олл:

1) есть ли обобщенная функция, аналогичная mapAccum из примера, в стандартной библиотеке Хаскела?
2) является ли () в сингатуре функции f признаком того, что мне нужна не монада, а что-то "менее могущественное"?
Tags: fp, programming
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 11 comments