51

有哪些方法可以完成 Haskell 的类型类在 OCaml 中的功能？基本上，我想写一个多态函数而不写太多代码。进行多态的典型方法是提供一个额外的参数，告诉函数它当前正在处理什么类型。例如，假设我想对一个整数列表进行排序，我必须向函数传递一个额外的比较器。

type comparison = Lesser | Equal | Greater

my_sort : (a' -> a' -> comparison) -> 'a list -> 'a list

有没有办法告诉 OCaml 我的类型是可比较的，而无需为我想要排序的每种类型编写比较器函数？这意味着我的排序函数看起来就像这样：

my_sort : 'a list -> 'a list
4

5 回答 5

30

这真的取决于你想要实现什么。

如果您对 OCaml 多态比较函数（它不适用于循环和函数值）感到满意，您可以简单地编写：

let my_sort l = List.sort Pervasives.compare l

模仿类型类的更通用的方法是使用仿函数：

module type COMPARABLE = sig
  type t
  val compare: t -> t -> int
end

module MySort (C: COMPARABLE) = struct
  let sort l = List.sort C.compare l
end

(* You can now use instantiate the functor *)
module IntAscending = struct
  type t = int
  let compare = (-)
end
module IntDescending = struct
  type t = int
  let compare x y = y - x (* Reverse order *)
end

module SortAsc = MySort(IntAscending)
module SortDesc = MySort(IntDescending)
于 2013-02-18T11:09:43.283 回答
29

Derek Dreyer、Robert Harper 和 Manuel MT Chakravarty在“模块化类型类”中对此进行了详细解释。在第 34 届 ACM SIGPLAN - SIGACT 编程语言原理研讨会论文集上，ACM 出版社，2007 年。摘自：

ML 模块和 Haskell 类型类已被证明是用于程序结构的高效工具。模块强调程序组件的显式配置和数据抽象的使用。类型类强调隐式程序构造和即席多态性。在本文中，我们通过将类型类视为一种特定的模块使用模式，展示了如何在显式类型化模块语言的框架内支持类型类编程的隐式类型化风格。此视图提供了模块和类型类的和谐集成，其中类型类特征（例如类层次结构和相关类型）是作为现有模块语言结构（例如模块层次结构和类型组件）的使用而自然出现的。此外，程序员可以明确控制在给定范围内哪些类型类实例可供类型推断使用。我们将我们的方法形式化为 Harper-Stone 风格的细化关系，并提供了一种合理的类型推理算法作为实现指南。

于 2013-02-18T12:03:58.537 回答
15

我遇到了一篇非常好的文章，展示了 Haskell 中的类型和类型类以及 OCaml 中的模块和模块类型之间的转换：http: //conway.rutgers.edu/~ccshan/wiki/blog/posts/Translations/

基本上，正如@Thomas 所示，Haskell 中的类型类成为 OCaml 中的模块类型，具有一个类型（实现类型类的类型）和一堆使用该类型的值。

然后，对应于 Haskell 中类型类的“实例”，您在 OCaml 中有一个实现模块类型的模块，类型是实例的类型，值是类型类中值的实现.

然后，每次在 Haskell 中有一个“使用”受该类型类约束的类型的函数时，都需要将该函数包装在 OCaml 的模块中。这个模块（实际上是一个仿函数）将接受一个参数模块，它对应于我们正在使用的类型类的实例。

每次使用该函数时，您都需要首先使用该函子创建一个适当的模块，并将类型类的正确实例传递给它。

你会注意到 Haskell 和 OCaml 的一个很大的不同之处在于，在 Haskell 中，当你使用最后一个函数时，编译器会为你推断出正确的类型类实例；而使用 OCaml 的方式，用户必须明确指定要使用的实例。

于 2013-02-18T20:34:19.230 回答
10

尽管不像模块那样接近 Haskell，但对象类层次结构上的类类型并没有清楚地解释。

请参阅类类型定义。

更新：工作示例：

type comparison = Lesser | Equal | Greater

class type comparable = object ('a)
  method compareTo: 'a -> comparison
end ;;

class type textualizable = object
  method toString: string
end ;;

(* this corresponds in Haskell to a multiparameter type class *)
class type ['b] printable = object ('a)
  constraint 'b = #textualizable         
  method printWithPrefix: 'b -> unit
end ;;

class type ['b] comparableAndPrintable = object ('a)
  inherit comparable
  inherit ['b] printable
end ;;

(* -------------- *)

class textile (str_init:string): textualizable = object
   val str = str_init
   method toString = str
end ;;

class comparableAndPrintableImpl1 (x_init: int) = object (this:'a)

  constraint 'a = 'b #comparableAndPrintable    (* interface implementation requirement *)
  constraint 'b = textualizable (* concrete type parameter *)

  val x = x_init
  method getx = x
  method compareTo (that:'a) = let r = this#getx - that#getx in
                               match r with
                               | 0 -> Equal
                               | _ when r < 0 -> Lesser
                               | _ -> Greater

  method printWithPrefix (pref: 'b)  = Printf.printf "%s %d\n" pref#toString x
end ;;

let boxSort (pivot: #comparable) (lows, equals, highs) (x: #comparable) =
      match x#compareTo pivot with
                    | Lesser -> x :: lows, equals, highs
                    | Equal -> lows, x :: equals, highs
                    | Greater -> lows, equals, x :: highs
      ;;

let rec qsort (li : #comparable list) =
      match li with
          [] | [_] -> li
          | [a;b] -> (match a#compareTo b with
                     Lesser | Equal -> [a;b]
                     | Greater -> [b;a]
                     )
          | x :: xs -> let (lows, equals, highs) = List.fold_left (boxSort x) ([], [], []) xs in
                       qsort lows @ (x :: equals) @ qsort highs
  ;;


let print_myList (prefix: 'a) (li: 'a #printable list) =
    let print_it it = it#printWithPrefix prefix in
    print_endline "\nlist: " ;
    List.iter print_it li
    ;;

let intlist (lfrom: int) (lto: int) =
   let open BatLazyList in
   to_list (range lfrom lto)              (* lazy range generator from BatLazyList *)
   ;;

let myComparableAndPrintableList =
  List.map (new comparableAndPrintableImpl1) (List.rev (intlist 1 5))
  ;;

let myprefix = new textile "x ="

let sortAndPrint (li: 'a #comparableAndPrintable list) =
   let sorted = qsort li in
   print_myList myprefix li ;
   print_myList myprefix sorted
   ;;

sortAndPrint myComparableAndPrintableList ;;

编译和链接：

ocamlfind ocamlc -package batteries -linkpkg test.ml -o test
于 2013-02-18T19:47:49.537 回答
3

通常，由于 OCaml 不支持隐式参数，因此您需要某种字典参数来显式传递类型类实例。这可以根据多态记录、一流模块或对象来实现。我有一个示例项目显示了使用模块的方法：https ://github.com/hongchangwu/ocaml-type-classes

于 2016-11-20T20:19:02.653 回答