是否可以在Clojure中进行免费Monad？

Question

Konrad Hinsen,Jim Duey和Leonardo Borges在Clojure中与Monads进行了一些出色的合作.

我的问题是 - 是否有可能在Clojure中做免费Monad？

这是一篇关于Scala文章的Haskell示例:

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

它绝对可以完成,但关键是自由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功能:

1. 输入类:Functor和Monad
2. 递归数据类型:Free是递归类型
3. 更高级别的多态性:请注意,类型变量fin Free f r实际上用作类型构造函数 - 定义在约束元素类型时抽象容器类型.

然后它也使用了类型级别的定点构造,这是Clojure中不存在的一种技术.最简单的版本是这种类型:

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

如果您曾经读过Y组合器,您可以将其视为它的类比,但是在类型层面而不是值.

但抛开所有这些,让我们专注于这里的基本结构:一个免费的monad基本上是一种懒惰生成的,可能是无限的树结构.在Functor一个自由的单子用来做两件事情:

1. 定义树中存在哪些类型的节点,以及每个节点上携带的数据
2. 允许通用的免费monad代码在任何节点的子节点上映射函数.

(不要陷入将自由monadic树视为"抽象语法树"的错误观念;树的节点不代表表达式或类似的东西.)

核心通用免费monad代码然后提供两件事:

1. 甲Pure这是保证节点类型为在每一个自由单子存在.这些节点只包含一个值,而不包含子节点.
2. 一种绑定方法,它懒惰地替换所有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解释器？

好吧,免费monad给你的一件事是monadic程序的一种正常形式表示.例如,考虑以下类似的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表达式语法允许您编写两个不同的表达式,但仍然需要这些表达式始终表现相同.另一方面,在Haskell中,Freemonad定义保证上面的两个表达式评估完全相同的值 - 没有程序可以区分它们!因此,您可以编写一个有缺陷的s-exp解释器或宏,以不同的方式处理这两个Clojure表单,但对于免费的monadic树则不然.

另一组潜在的优点是,免费monad提供了一些标准技术来实现回溯等语言功能(使用某种列表作为你的函子,代表它们被考虑的顺序的替代品)以及暂停/恢复a的解释程序(免费monad与延续传递风格密切相关).

但是对于Lisp中的最大惯用性,您可能希望结合使用这两种技术:根据客户端提供的特殊操作定义,使用s-exprs作为前端,使用一些通用库将其转换为自由monad表示. DSL.还提供通用函数,以简化客户端为其免费monadic语言编写解释器的任务.

Answer 2

是的，按照 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))))))

这在数据结构的可读性方面可以得到很大改善。评论和改进最受欢迎。