修复OCaml中的数据类型 [英] FIx data type in OCaml

问题描述

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

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

推荐答案

我已经answered this question on the mailing-list了(我必须说，您在两个不同的地方问这个问题没有几天的好时间，我有点不高兴，因为这可能会引起重复的努力)，但是让我们在这里重复一下。

这里有一个困难，因为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还支持等递归，而不是 ISO递归类型，这允许您在 每个递归层。为此，您必须编译合并模块 (以及所有通过 接口)，并使用"-rectype"选项。然后您可以写：

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会跳到它？

这篇关于修复OCaml中的数据类型的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！