OCaml中的FIx数据类型

Question

Haskell中的以下数据类型如何在OCaml或SML中表示？

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

Answer 1

我不认为OCaml可以让你抽象类型构造函数。对于Fix的特定应用，我认为可以使用-rectypes获得类似的效果。

$ ghci 
GHCi, version 7.4.2: http://www.haskell.org/ghc/ :? for help 
Loading package ghc-prim ... linking ... done. 
Loading package integer-gmp ... linking ... done. 
Loading package base ... linking ... done. 
Prelude> newtype Fix f = In (f (Fix f)) 
Prelude> type L = Fix [] 
Prelude> let w = In [] :: L 
Prelude> let x = In [x] :: L 

$ ocaml -rectypes 
     OCaml version 4.00.0 

# type l = l list;; 
type l = l list 
# ([] : l);; 
- : l = [] 
# let rec x = [x];; 
val x : 'a list as 'a = [[[...]]] 
# (x : l);; 
- : l = [[[...]]] 

我不是一个模块类型的专家。可能有一种方法可以使用模块来比这更近。一切似乎都可以使用模块系统。

Answer 2

我已经answered this question on the mailing-list（我必须说，我对你在两个不同的地方问这个问题有点不高兴，因为它会引起重复的努力），但是让我们在这里重现它。

这里有一个困难，因为OCaml不支持排名较高的 类型变量。在此声明中，f不是“类型”，而是“类型 运算符”（种类* -> *）。要在OCaml中做同样的事情，你可以使用一个 仿函数（不是一个Haskell仿函数;在OCaml中，“仿函数”一词表示一个 高阶模块，可能依赖于其他模块/仿函数）。 仿函数更高。

module type ParamType = sig 
    type ('a, 'b) t 
end 

module Fix (M : ParamType) = struct 
    type 'b fix = In of ('b fix, 'b) M.t 
end 

module List = struct 
    module Param = struct 
    type ('a, 'b) t = Nil | Cons of 'b * 'a 
    end 
    include Fix(Param) 
end 

open List.Param 
open List 

let rec to_usual_list = 
    function 
    | In Nil -> [] 
    | In (Cons (x, xs)) -> x :: to_usual_list xs 

的好消息是，OCaml中还支持相等递归而不是 异递归类型，它允许你删除“在”包装在 每个递归层。为此，必须使用“-rectypes”选项编译管理模块 （以及所有也可通过 界面查看该等值线的模块）。然后你可以写：

module type ParamType = sig 
    type ('a, 'b) t 
end 

module EqFix (M : ParamType) = struct 
    type 'b fix = ('b fix, 'b) M.t 
end 

module EqList = struct 
    module Param = struct 
    type ('a, 'b) t = Nil | Cons of 'b * 'a 
    end 
    include EqFix(Param) 
end 

open EqList.Param 

let rec to_usual_list = 
    function 
    | Nil -> [] 
    | (Cons (x, xs)) -> x :: to_usual_list xs 

模块的语法很重，可能会显得很可怕。如果 您坚持您可以使用一流的模块将这些用途中的一些 从仿函数转移到简单函数。我选择以“简单” 的方式首先做到这一点。

更高kinded变量嫉妒可能是最严重的疾病有关 OCaml的类型崇拜者（或Haskellers，对于一些（好！）原因 进来职能县的这些地方徘徊）。在实践中，我们做 没有它没有太多的问题，但大量使用monad 变压器确实会由于这个函数步骤而变得复杂，其中 是它在这里不是很流行的原因之一。 你也可以通过考虑支持它们的语言中更高级变量的不完善来分散注意力; 限制构造函数多态而不是任意 类型级别的函数使它们不如您想要的那样具有表现力。 当我们研究绝对完美的高阶 类型抽象的细节时，也许OCaml会跳到它？