haskell - 修复 OCaml 中的数据类型

Question

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

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

Answer 1

我已经在邮件列表上回答了这个问题（我必须说我有点不高兴你在两个不同的地方问这个问题而没有几天的延迟，因为它可能会引起重复工作），但是让我们在这里复制它。

这里有一个困难，因为 OCaml 不支持更高级别的类型变量。在这个声明中，f不是一个“类型”，而是一个“类型操作符”（kind * -> *）。要在 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”选项编译现有模块（以及所有通过接口也看到此等递归的模块）。然后你可以写：

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 转换器确实会变得复杂，这也是它在这里不是很流行的风格的原因之一。您还可以通过考虑支持它们的语言中高级变量的缺陷来分散自己的注意力；对构造函数多态性而不是任意类型级函数的限制使它们的表现力不如您想要的那样。那天我们解决了绝对完美的高阶类型抽象的细节，也许 OCaml 会跳到它上面？

Answer 2

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

$ 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 = [[[...]]]

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