Можно ли сделать свободную монаду в Клоджуре?

Есть некоторые выдающиеся работы с монадами в Clojure от Конрада Хинсена, Джим Дьюи и Леонардо Борхес.

Мой вопрос - Можно ли сделать свободную монаду в Clojure?

Это пример в Haskell из статьи о Scala: 

data Free f r = Free (f (Free f r)) | Pure r

Это соответствующий пример Scala 

sealed abstract class Free[S[+_], +A](implicit S: Functor[S]) {
  final def map[B](f: A => B): Free[S, B] =
    flatMap(a => Return(f(a)))

  final def flatMap[B](f: A => Free[S, B]): Free[S, B] = this match {
    case Gosub(a, g) => Gosub(a, (x: Any) => Gosub(g(x), f))
    case a           => Gosub(a, f)
  }
  ...
}
3 7
monads clojure free-monad

3 ответа:

Да, следующие Луис Касильяс ответ, Вот это реализация в Clojure из Free монады в Clojure.

    (use 'clojure.algo.monads)

    ;; data Free f r = Free (f (Free f r)) | Pure r
    (defn pure [v] {:t :pure :v v})
    (defn impure [v] {:t :impure :v v })

    (defn free-monad
    [fmap]
    (letfn [
            (fm-result [v] (pure v))         
            (fm-bind [mv mf]                 
                (if (= :pure (:t mv))
                    (mf (:v mv))             ;; Pure a >>= f = f a
                    (impure                  ;; Free fa >>= f = Free (fmap (>>=f) fa) 
                     ((fmap (fn [lmv] (fm-bind lmv mf))) (:v mv)))))          
            ]
        {
        :m-result fm-result
        :m-bind fm-bind
        :m-zero ::undefined 
        :m-plus ::undefined
        }
        ) 
    )

И пример из Почему свободные монады имеют значение :

Определение языка игрушек.

    ;; Toy language
    ;; 
    (defn output [c n] [{:t :output :v c}, n])
    (defn bell [n] [{:t :bell}, n]) 
    (defn done [] [{:t :done}, nil]) 
    (defn toy-fmap [f]
    (fn [[e c]]
    (if (= :done (:t e))
        [e c]
        [e (f c)] 
        ))  
    )

Определение монады для языка игрушек + вспомогательные функции 

    ;;
    (def tt-monad 
    (free-monad toy-fmap))


    (defn liftF [toy]
    (impure ((toy-fmap (fn [c] (pure c))) toy))
    )

    (defn m-output [x] (liftF (output x nil)))
    (defn m-bell [] (liftF (bell nil)))
    (defn m-done [] (liftF (done)))
    (defn f-m-done [_] (m-done))

И проверка некоторых правил: 

    ;; return "a" >>= output  is Free(Output "a", ())
    ;; {:t :impure, :v [{:t :output, :v \a} {:t :pure, :v nil}]}  
    (with-monad tt-monad
    (m-bind (m-result \a) m-output)
    )


    ;; output "a" >>= return  is Free(Output "a", ())
    ;; {:t :impure, :v [{:t :output, :v \a} {:t :pure, :v nil}]}
    (with-monad tt-monad
    (m-bind (m-output \a) m-result)
    )

    ;; ((output 'A' >> done) >> output 'C')
    (with-monad tt-monad
    (m-bind (m-bind (m-output \a) f-m-done) (fn [_] (m-output \c))))

    ;;(output 'A' >> (done >> output 'C')) is output 'A' Done
    (with-monad tt-monad
    (m-bind (m-output \a) (fn [x] (m-bind (m-done) (fn [_] (m-output \c))))))
Это можно было бы значительно улучшить с точки зрения читаемости структуры данных. Комментарии и улучшения приветствуются.
4

Это определенно может быть сделано, но ключевым моментом является то, что идиоматическая реализация свободных монад Хаскелла основана на использовании системы типов для обеспечения определенного вида модульности и гарантий правильности формы. Используемые идиомы вполне могут не быть идиоматическими в Clojure, и, возможно, лучше всего придумать другой вид реализации.

Просто посмотрите на полное определение монады Free в Хаскелле: 
data Free f r = Free (f (Free f r)) | Pure r

instance Functor f => Monad (Free f) where
    -- Construct a "pure value" leaf node
    return = Pure

    -- Replace every "pure value" leaf node with the tree obtained by 
    -- applying `f` to its value.  (Remember that Haskell is lazy, so this
    -- tree is only created as it is consumed, and only those branches that are
    -- in fact consumed.)
    Pure a >>= f = f a
    Free fa >>= f = Free (fmap (>>=f) fa)

Здесь используется следующий Хаскелл особенности:

  1. классы типов: Functor и Monad
  2. рекурсивные типы данных: Free является рекурсивным типом
  3. полиморфизм более высокого рода: обратите внимание, что переменная типа f в Free f r фактически используется в качестве конструктора типа -определение абстрагируется от типа контейнера, ограничивая тип элемента.

Тогда он также использует конструкцию фиксированной точки уровня типа, технику, которая не существует в Clojure. Самый простой версия этого типа: 

newtype Fix f = Fix (f (Fix f))
Если вы когда-нибудь читали о y-комбинаторе, вы можете думать об этом как об аналоге его, но на уровне типов, а не значений. Но отложив все это в сторону, давайте сосредоточимся здесь на существенной структуре: свободная монада-это в основном своего рода лениво порожденная, возможно, бесконечная древовидная структура. Functor, используемый в свободной монаде, делает две вещи:
  1. определите, какие типы узлов существуют в дереве и какие данные переносится в каждом узле
  2. разрешить универсальному свободному коду монады отображать функцию над дочерними элементами любого узла.

(не впадайте в заблуждение, рассматривая свободное монадическое дерево как "абстрактное синтаксическое дерево"; узлы дерева не представляют выражения или что-то подобное.)

Основной универсальный код свободной монады тогда обеспечивает две вещи:

  1. тип узла Pure, который гарантированно существует в каждой свободной монаде. Эти узлы просто содержат ценность, и никаких детей.
  2. метод привязки, который лениво заменяет все листья Pure результатом применения их значения к функции.
После этого, предоставив подходящий функтор, вы можете использовать универсальный код свободной монады для построения ленивых деревьев в соответствии со структурой, которую предоставляет ваш функтор. Эти деревья-просто инертные значения; вы потребляете их, записывая функции интерпретатора, которые перемещаются по дереву в соответствии с некоторой стратегией, чтобы произвести результаты, которые вам нужны. Но на самом деле, вы хотели бы, чтобы ваша бесплатная библиотека монад имела некоторые подходящие общие утилиты, которые помогут вам легче писать интерпретаторы. Например: 
-- | Generic recursive fold over a free monadic tree.
iter :: Functor f => (f a -> a) -> Free f a -> a
iter f (Pure a) = a
iter f (Free fa) = f (fmap (iter f) fa)

-- | If you can map any node to a corresponding action in another monad, you can map 
-- the whole free monadic tree to a monadic action as well...
interpret :: (Functor f, Monad m) => (forall x. f x -> m x) -> Free f a -> m a
Таким образом, очевидный вопрос, если кто-то хочет написать это в Clojure (или любом другом Lisp), заключается в следующем: почему бы это сделать вместо того, чтобы просто написать интерпретатор DSL s-выражения? Ну, одна вещь, которую дают вам свободные монады, - это своего рода представление монадических программ в нормальной форме. Например, подумайте о следующие похожие фрагменты кода Clojure и Haskell: 
;;; Clojure; these two expressions always produce the same result and
;;; have the same effects
(do a (do b c))
(do (do a b) c)

-- Haskell counterparts
(a >> b) >> c
a >> (b >> c)
Синтаксис s-выражений в формах Clojure позволяет писать два различных выражения, которые, тем не менее, должны всегда вести себя одинаково. В Haskell, с другой стороны, определение монады Free гарантирует, что два приведенных выше выражения вычисляют точно такое же значение -никакая программа не может их различить! Таким образом, вы можете написать багги интерпретатор s-exp или макрос, который обработал эти два Clojure формы различны, но не таковы для свободных монадических деревьев. Еще один набор потенциальных преимуществ заключается в том, что свободные монады предоставляют некоторые стандартные методы для реализации языковых функций, таких как backtracking (используйте некоторый список в качестве своего функтора, представляя альтернативы в порядке их рассмотрения) и pausing/resuming интерпретации программы (свободные монады тесно связаны со стилем продолжения-передачи).

Но для максимальной идиоматичности в a Лисп, вы, вероятно, хотите объединить оба метода: использовать s-exprs в качестве интерфейса, который вы переводите, используя некоторую универсальную библиотеку, в свободное представление монады в соответствии с предоставленными клиентом определениями специальных операций DSL. Обеспечьте также общие функции для упрощения задачи клиента по написанию переводчиков для своего свободного монадического языка.

8

Это были два удивительных ответа, которые непосредственно отвечают на ваш вопрос и должны быть отложены.

Я все еще учусь сам и хотел бы расширить вопрос, упомянув, что свободные монады часто сопровождаются интерпретаторами, и ниже приводится простой пример, который я построил для свободной монады, упомянутой @cotarmanach's.

Это могло бы подключаться и играть с ним, чтобы обеспечить интерпретатор печати для структуры данных, построенной в следующем domonad выражение: 

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; INTERPRETER
;;

(def pavlov (domonad tt-monad [a (m-output "hi there pavlov")
                               b (m-bell)
                               c (m-output "howdya like me now?")
                               d (m-bell)
                               e (m-bell)
                               f (m-bell)
                               g (m-done)]
                     g))

(defn bell-interpreter [program]
  (let [{ft           :t ; free type: impure or pure?
         [{t :t
           v :v} next] :v} program]
    (if (= :pure ft)
      "error, shouldn't have a `pure` type"
      (case t
        :output (do (prn v) (bell-interpreter next))
        :bell (do (prn "rinnnng") (bell-interpreter next))
        :done "done!"
        :otherwise "uh oh, that's not a type I recognize"))))

  1. Для каждого узла проверьте, является ли он Free/Impure или Pure.

  2. Если это Impure, то это один из наших" определенных " типов, поэтому мы можем интерпретировать его. Создайте обращение для каждого из наших "типов" и обязательно вызовите следующий член этого рекурсивного типа данных.

0