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

Question

Произошла некоторая выдающаяся работа с Монадами в Клоюре на Konrad Hinsen, Jim Duey и Leonardo Borges.

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

This is an example in 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) 
    } 
    ... 
} 

Answer 1

Да, после ответа Луиса Касильяса, вот реализация в 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 
     } 
     ) 
    ) 

И пример из Why free monads matter:

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

;; 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)))))) 

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

Answer 2

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

Просто посмотрите на полное определение Free монады в Haskell:

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) 

Это использует следующий Haskell показывает:

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

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

newtype Fix f = Fix (f (Fix f)) 

Если вы когда-нибудь читали о Y combinator, вы можете думать об этом как аналог его, но на уровне типов, а не значений.

Но отложив все это, давайте сосредоточимся на существенной структуре здесь: свободная монада - это в основном своего рода лениво сгенерированная, возможно бесконечная древовидная структура. 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 гарантирует, что два выражения выше оценивают точно такое же значение -no программа может их отличить! Таким образом, вы можете написать интерпретатор s-exp с ошибкой или макрос, который обрабатывал эти две формы Clojure по-разному, но не так для свободных монадических деревьев.

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

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

Answer 3

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

Я все еще изучаю себя и хотел бы расширить вопрос, отметив, что бесплатные монады часто сопровождаются переводчиками, а следующее является простым, которое я построил для свободной монады, упомянутой @ 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, то это один из наших «определенных» типов, поэтому мы можем его интерпретировать. Создайте случай для каждого из наших «типов» и обязательно вызовите следующий член этого рекурсивного типа данных.