OCaml中的FIx数据类型

Question

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

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

Answer 1

我已经在邮件列表上回答了这个问题(我必须说我有点不高兴你在两个不同的地方提出这个问题而没有好几天的延迟,因为它可能引起的重复工作),但是让我们在这里重现它.

这里存在一个困难,因为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还支持等递归而不是等递归类型,它允许您在每个递归层删除"In"包装器.为此,您必须使用"-rectypes"选项编译incumbing模块(以及通过接口也看到此equirecursion的所有模块).然后你可以写:

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

模块的语法很重,可能看起来很可怕.如果你坚持认为你可以使用一流的模块将其中一些用途从仿函数转移到简单的函数.我选择以"简单"的方式开始.

较高级别的变量嫉妒可能是OCaml型崇拜者(或Haskellers,因为某些(好的!)原因在功能县的这些部分徘徊)最严重的疾病.在实践中我们没有它没有太多的问题,但是大量使用monad变换器确实很复杂,这个functor步骤,这是它不是一个非常流行的风格的原因之一.你也可以通过考虑支持它们的语言中高等级变量的不完美来分散注意力; 构造函数多态性的限制而不是任意类型级函数使它们的表达力低于你想要的.在我们计算绝对完美的高阶类型抽象的细节的那一天,也许OCaml会跳到它？

Answer 2

我认为 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 = [[[...]]]

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