Quelle est la chose la plus proche des classes de type de Haskell en OCaml ?

Question

Quels sont les moyens de réaliser en OCaml ce que font les classes de type de Haskell ? Fondamentalement, je veux écrire une fonction polymorphe sans écrire trop de code. La façon typique de faire du polymorphisme est de fournir un argument supplémentaire indiquant à la fonction le type sur lequel elle travaille actuellement. Par exemple, si je veux trier une liste d'ints, je dois passer un comparateur supplémentaire à la fonction.

type comparison = Lesser | Equal | Greater

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

Existe-t-il un moyen de dire à OCaml que mon type est comparable sans écrire une fonction de comparaison pour chaque type que je veux trier ? Ce qui signifie que ma fonction de tri ressemblerait à ceci :

my_sort : 'a list -> 'a list

Answer 1

Cela dépend vraiment de ce que vous voulez obtenir.

Si vous êtes satisfait de la fonction de comparaison polymorphe d'OCaml (qui ne fonctionne pas sur les valeurs cycliques et fonctionnelles), vous pouvez simplement écrire :

let my_sort l = List.sort Pervasives.compare l

La façon la plus générique d'imiter les classes de type est d'utiliser des foncteurs :

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)

Answer 2

Ceci est expliqué en détail dans " Classes de type modulaire "par Derek Dreyer, Robert Harper et Manuel M. T. Chakravarty. In Proceedings of The 34th Annual ACM SIGPLAN - SIGACT Symposium on Principles of Programming Languages, ACM Press, 2007. Extrait du résumé :

Les modules ML et les classes de type Haskell se sont révélés être des outils très efficaces pour structurer les programmes. Les modules mettent l'accent sur la configuration explicite des composants du programme et sur l'utilisation de l'abstraction des données. Les classes de types mettent l'accent sur la construction implicite de programmes et le polymorphisme ad hoc. Dans cet article, nous montrons comment le style implicitement typé de la programmation par classes de types peut être pris en charge dans le cadre d'un langage de modules explicitement typé en considérant les classes de types comme un mode particulier d'utilisation des modules. Ce point de vue offre une intégration harmonieuse des modules et des classes de types, où les caractéristiques des classes de types, telles que les hiérarchies de classes et les types associés, apparaissent naturellement comme des utilisations de constructions existantes du langage de modules, telles que les hiérarchies de modules et les composants de types. En outre, les programmeurs ont un contrôle explicite sur les instances de classes de types disponibles pour l'inférence de types dans un champ d'application donné. Nous formalisons notre approche sous la forme d'une relation d'élaboration de type Harper-Stone, et nous fournissons un algorithme d'inférence de type solide comme guide d'implémentation.

Answer 3

Je suis tombé sur un article très intéressant démontrant la traduction entre les types et les classes de types en Haskell et les modules et les types de modules en OCaml : http://conway.rutgers.edu/~ccshan/wiki/blog/posts/Translations/

En fait, comme l'a montré @Thomas, les classes de type en Haskell deviennent des modules types en OCaml avec un type (le type implémentant la classe de type) et un tas de valeurs utilisant ce type.

Alors, correspondant à une "instance" de la classe de type en Haskell, vous avez un module en OCaml qui implémente le type de module, avec le type étant le type de l'instance, et les valeurs étant l'implémentation des valeurs dans la classe de type.

Ensuite, chaque fois que vous avez une fonction qui "utilise" un type contraint par cette classe de type en Haskell, vous devez envelopper cette fonction à l'intérieur d'un module en OCaml. Ce module (en fait un foncteur) prendra un module en argument qui correspond à l'instance de la classe de type que nous utilisons.

Et chaque fois que vous utiliserez cette fonction, vous devrez d'abord créer un module approprié en utilisant ce foncteur et en lui passant la bonne instance de la classe de type.

Vous remarquerez qu'une grande différence entre les méthodes Haskell et OCaml est qu'en Haskell, lorsque vous utilisez cette dernière fonction, le compilateur déduit la bonne instance de la classe de type pour vous, alors qu'avec la méthode OCaml, l'utilisateur doit explicitement spécifier l'instance à utiliser.

Answer 4

Bien qu'il ne soit pas aussi proche de Haskell que les modules, types de classes sur la hiérarchie des classes d'objets ne sont pas clairement expliquées.

Véase définitions des types de classes .

Mise à jour : exemple de travail :

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 ;;

compiler et lier :

ocamlfind ocamlc -package batteries -linkpkg test.ml -o test

Answer 5

En général, comme OCaml ne supporte pas les paramètres implicites, vous avez besoin d'une sorte de paramètre dictionnaire pour passer explicitement des instances de classes de types. Cela peut être implémenté en termes d'enregistrements polymorphes, de modules de première classe ou d'objets. J'ai un exemple de projet qui montre une façon d'utiliser les modules : https://github.com/hongchangwu/ocaml-type-classes