代码之家 › 专栏 › 技术社区 › Sean

OCAML检查元素是否存在于元组的右手边

type-inference ocaml tuples list

Sean · 技术社区 · 6 年前

我目前正在尝试使用OCaml语言实现类型推理算法(统一算法)。我遇到了一些执行方面的困难,希望有人能给我一些帮助。

让我提供一些我正在尝试实现的背景信息。

[(TypeVar "t1", TypeFunc (TypeVar "t2", TypeVar "t3"))]

这个 (type * type) list t1 映射到的函数 t2 -> t3 .

[(TypeVar "t1", TypeFunc (TypeVar "t1", TypeVar "t3"))]

这会给我们一个错误,因为 t1 = t1 -> t3

下面是我试图实现的实际OCaml函数,以捕捉这一矛盾:

let contradiction_check (a, t) =
  List.exists (fun (x, _) -> x = a) t;;

let t1 = TypeVar "t1";;
let t2 = TypeFunc (TypeVar "t2", TypeVar "t3");;

这段代码的问题首先是 t2 [(TypeVar "t1", TypeFunc (TypeVar "t2", TypeVar "t3"))] 并检查元组的左侧是否出现在右侧。

我想我的具体问题是:是否有可能实现 List.exists 作为元组的版本?我试过手动编写函数,但似乎比我最初想象的要复杂。

[(TypeVar "t1", TypeFunc (TypeFunc (TypeVar "t2", TypeVar "t3"),
  TypeFunc (TypeVar "t1", TypeVar "t4")))]

(** t1 = (t2 -> t3) -> (t1 -> t4) **)

欢迎任何反馈。谢谢您。

1 回复 | 直到 6 年前

Dan Robertson 6 年前

您应该编写一个递归函数来搜索:

(** [is_free ~varname t] is [true] iff [varname] appears as a free type variable in [t] *)
let is_free ~varname =
  let rec r = function
    | TypeVar n when String.( = ) n varname -> true
    | TypeVar _ -> false
    | TypeFunc s t -> r s || r t
    | TypaApp c t -> r c || r t (* if c is just a name not a type you donât want [r c] here *)
    | TypeForall n t -> 
      if String.( = ) n varname
      then false
      else r t
  in
  r

我不知道你所有的案例都是什么样子,但是你会写一个类似于上面的函数。

然后看看你能不能把事情统一起来:

let can_unify = function
  | TypeVar t1, TypeVar t2 when String.( = ) t1 t2 -> (* decide what to do here *)
  | TypeVar varname, t -> not (is_free ~varname t)
  | _ -> (* throw an error or fix your types so this case canât happen *)

推荐文章

Zachary Bechhoefer · ocamlopt:链接期间出错

6 年前

Tosh · ocaml获取语法错误[已关闭]

6 年前

Beta Ziliani · OCaml-与类型别名混淆(警告40)

6 年前

Jheel rathod · 带有构造函数的ocaml递归类型记录

6 年前

HegoDamask · (OCaml:非穷举模式匹配)

6 年前

Flux · 如何以静默方式加载顶级模块

6 年前

Flux · 如何编写显示HTML或重定向到其他页面的服务

6 年前

Daiwen · ocaml中GADT的异构列表[重复]

6 年前

nejifnjalz · OCaml语法错误-有趣的模式匹配

6 年前

M. Walker · 无法键入多态[%bs.raw函数

6 年前