教會在F編碼自由單體＃

Question

我想表達F＃自由單體的教會編碼。 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') 
      ) 

我得到的第三個參數類型錯誤Free.runFree的interpret函數中：

... 

(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）解決，但我不知道如何應用它。

任何指針將不勝感激。

邁克爾

Answer 1

你不需要做任何事情有，編譯建議類型實際上是正確的（在與runFree型線）。

看來，你在想什麼的還有斯科特編碼（從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>是一個仿函數 - 在粘貼的代碼中沒有使用這個事實）。