首页 文章

教会编码F＃免费monad

提问于
浏览 次
2

我试图在F＃中表达Free monad的教会编码 . Free 专门用于特定的仿函数 Effect .

我能够写出 return_ : 'T -> Free<'T> 和 bind: ('T -> Free<'U>) -> Free<'T> -> Free<'U> 没有任何问题 .

我的实现草图如下 .

type Effect<'T>
    = GetStr of (string -> 'T)
    | PutStr of string * 'T


module Effect = 

    let map (f: 'a -> 'b) : Effect<'a> -> Effect<'b> = function
        | GetStr k -> 
            GetStr(f << k)

        | PutStr (s,t) -> 
            PutStr(s, f t)


type Free<'T> =
    abstract Apply : ('T -> 'R) -> (Effect<'R> -> 'R) -> 'R

module Free = 
    let inline runFree (f:Free<'T>) (kp: 'T -> 'R) (kf: Effect<'R> -> 'R) : 'R = 
        f.Apply kp kf

    let return_ (x: 'a) : Free<'a> = 
        { new Free<'a>
            with
                member __.Apply kp _ = 
                    kp x
        }

    let bind (f: 'a -> Free<'b>) (m: Free<'a>) : Free<'b> = 
        { new Free<'b>
            with
                member __.Apply kp kf = 
                    runFree m
                        (fun a -> 
                            runFree (f a) kp kf
                        )
                        kf
        }

当我尝试为这种编码编写解释器时，我遇到了一个问题 .

给出以下代码：

module Interpret = 

    let interpretEffect = function 
        | GetStr k -> 
            let s = System.Console.ReadLine()             
            (k s , String.length s)

        | PutStr(s,t) -> 
            do System.Console.WriteLine s 
            (t , 0) 

    let rec interpret (f: Free<string * int>) = 
        Free.runFree
            f
            (fun (str,len) -> (str,len))
            (fun (a: Effect<Free<string*int>>) -> 
                let (b,n) = interpretEffect a 
                let (c,n') = interpret b 
                (c, n + n')
            )

我在 interpret 函数中的 Free.runFree 的第三个参数中得到一个类型错误：

...

(fun (a: Effect<Free<string*int>>) -> 
      ^^^^^^^^^^^^^^^^^^ ------ Expecting a Effect<string * int> but given a Effect<Free<string*int>>

我理解为什么会发生这种情况（第一个函数的结果类型确定 'R === string*int ）并且怀疑可以使用rank-2函数（可以用F＃编码，例如http://eiriktsarpalis.github.io/typeshape/#/33）来解决，但我不知道如何应用它 .

任何指针都将非常感激 .

迈克尔

f# existential-type free-monad rank-n-types

1 回答

  • 1

    你不需要在那里做任何事情，编译器建议的类型实际上是正确的（并且符合 runFree 的类型） .

    看来你在想的是Scott编码（从this Haskell question撕掉）：

    runFree :: Functor f => (a -> r) -> (f (F f a) -> r) -> F f a -> r

    F f a 将是你的 Effect -specialised Free<'a> ，而 f (F f a) 将是 Effect<Free<'a>> ，这是你正在尝试使用的 .

    教会编码将是：

    runFree :: Functor f => (a -> r) -> (f r -> r) -> F f a -> r

    其中 f r 是 Effect<'a> - 因此更容易用F＃表达（这就是为什么我假设你首先使用它 .

    这就是我对 interpret 的看法：

    let rec interpret (f: Free<string * int>) = 
    Free.runFree
        f
        (fun (str,len) -> (str,len))
        (fun (a: Effect<_>) -> 
            let (b,n) = interpretEffect a 
            let (c,n') = interpret (Free.pureF b)
            (c, n + n')
        )

    其中 pureF 是

    let pureF (x: 'a) : Free<'a> = 
    { new Free<'a> with member __.Apply kp _ = kp x }

    即你的 return_ 功能 .

    我认为定义相应的 freeF 函数会清除一些东西（比如为什么 Effect<'a> 是一个仿函数 - 你没有在你粘贴的代码中的任何地方利用这个事实） .

    回复于

相关问题