clojure - Is it possible to do the Free Monad in Clojure?

Question

There has been some outstanding work with Monads in Clojure by Konrad Hinsen, Jim Duey and Leonardo Borges.

My question is - is it possible to do the Free Monad in Clojure?

This is an example in Haskell from an article on Scala:

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

This is the corresponding Scala example

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)
  }
  ...
}

score 8 · Accepted Answer

这绝对可以做到，但关键是自由 monad 的惯用 Haskell 实现是基于利用类型系统来提供某种模块化和格式良好的保证。在 Clojure 中使用的惯用语可能不是惯用的，最好提出一种不同的实现方式。

看看FreeHaskell 中 monad 的完整定义：

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 功能：

类型类：Functor和Monad
递归数据类型：Free是递归类型
更高种类的多态性：请注意，类型变量finFree f r实际上用作类型构造函数——定义是对容器类型进行抽象，同时约束元素类型。

然后它还使用了类型级别的定点构造，这是 Clojure 中不存在的一种技术。最简单的版本是这种类型：

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

如果您曾经阅读过Y 组合器，您可以将其视为它的类似物，但在类型级别而非值级别。

但抛开这一切，让我们关注这里的基本结构：一个自由的 monad 基本上是一种惰性生成的，可能是无限的树结构。在Functor自由单子中使用的做两件事：

定义树中存在哪些类型的节点，每个节点承载哪些数据
允许通用的自由 monad 代码将函数映射到任何节点的子节点。

（不要误以为将自由单子树视为“抽象语法树”；树的节点不代表表达式或类似的东西。）

核心的通用自由 monad 代码然后提供了两件事：

Pure保证存在于每个自由 monad 中的节点类型。这些节点只包含一个值，没有子节点。
Pure一种绑定方法，它用将它们的值应用于函数的结果懒惰地替换所有叶子。

有了这个之后，通过提供合适的函子，您可以使用通用的免费 monad 代码根据函子提供的结构构造惰性树。这些树只是惰性值；您可以通过编写解释器函数来使用它们，这些函数根据某种策略导航树以产生您需要的结果。但实际上，您希望您的免费 monad 库具有一些合适的通用实用程序函数来帮助您更轻松地编写解释器。例如：

-- | 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）中编写此代码，显而易见的问题是：为什么要这样做而不是编写一个 s-expression DSL 解释器？

好吧，免费单子给你的一件事是单子程序的一种范式表示。例如，想想以下 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)

Clojure 表单中的 s-expression 语法允许您编写两个不同的表达式，但要求它们始终表现相同。另一方面，在 Haskell 中，Freemonad 定义保证上面的两个表达式的计算结果完全相同——没有程序可以区分它们！因此，您可以编写一个错误的 s-exp 解释器或宏，以不同方式处理这两种 Clojure 形式，但对于自由单子树则不然。

另一组潜在的优势是免费的 monad 提供了一些标准技术来实现语言特性，比如回溯（使用某种列表作为你的函子，按照它们被考虑的顺序表示替代方案）和暂停/恢复对 a 的解释程序（自由单子与延续传递风格密切相关）。

但是为了在 Lisp 中获得最大的惯用性，您可能希望将这两种技术结合起来：使用 s-exprs 作为前端，使用一些通用库，根据客户端提供的特殊操作的定义，将其转换为免费的 monad 表示。 DSL。还提供通用函数来简化客户为他们的自由一元语言编写解释器的任务。

score 5 · Accepted Answer

是的，按照 Luis Casillas 的回答，这里是 clojure 中Freemonad 的 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)] 
        ))  
    )

玩具语言 + 辅助函数的 monad 定义

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

就数据结构的可读性而言，这可以大大改善。欢迎评论和改进。

score 0 · Accepted Answer

这是两个很棒的答案，直接回答了你的问题，应该推迟。

我仍在学习自己，并想通过提及 Free Monad 经常伴随解释器来扩展问题，以下是我为@cotarmanach 提到的免费 monad 构建的一个简单的问题。

这可以与他的即插即用，为以下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"))))

对于每个节点，检查它是否是Free/Impure或Pure。
如果它是Impure，那么它就是我们的“定义”类型之一，所以我们可以解释它。为我们的每个“类型”创建一个案例，并确保调用此递归数据类型的下一个成员。

clojure - Is it possible to do the Free Monad in Clojure?

3 回答 3

Related

Reference