opciones - programa en haskell

¿Qué es lo más parecido a las clases de Haskell en OCaml?

Question

¿De qué maneras puedo lograr lo que hacen las clases de Haskell en OCaml? Básicamente, quiero escribir una función polimórfica sin escribir demasiado código. La forma típica de hacer polimorfismo es proporcionar un argumento adicional que diga que la función es en qué tipo está trabajando actualmente. Por ejemplo, digamos que quiero ordenar una lista de entradas, tengo que pasar un comparador adicional a la función.

type comparison = Lesser | Equal | Greater

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

¿Hay alguna forma de decirle a OCaml que mi tipo es comparable sin escribir una función de comparación para cada tipo que quiero ordenar? Lo que significa que mi función de clasificación se vería así:

my_sort : ''a list -> ''a list

Answer 1

Aunque no está tan cerca de Haskell como los módulos, los tipos de clases sobre la jerarquía de clases de objetos no se explican con claridad.

Ver definiciones de tipo de clase .

Actualización: ejemplo de trabajo:

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

compilar y vincular:

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

Answer 2

En general, dado que OCaml no admite parámetros implícitos, se necesita algún tipo de parámetro de diccionario para pasar las instancias de clase de tipo explícitamente. Esto se puede implementar en términos de registros polimórficos, módulos de primera clase u objetos. Tengo un proyecto de muestra que muestra una forma de usar módulos: https://github.com/hongchangwu/ocaml-type-classes

Answer 3

Esto se explica en detalle en " Clases de tipos modulares " por Derek Dreyer, Robert Harper y Manuel MT Chakravarty. En Actas del 34º Simposio Anual ACM SIGPLAN - SIGACT sobre Principios de Lenguajes de Programación, ACM Press, 2007. Del resumen:

Los módulos ML y las clases de tipo Haskell han demostrado ser herramientas altamente efectivas para la estructuración de programas. Los módulos enfatizan la configuración explícita de los componentes del programa y el uso de la abstracción de datos. Las clases de tipo enfatizan la construcción de programa implícito y el polimorfismo ad hoc. En este documento, mostramos cómo el estilo implícitamente tipado de la programación de clase de tipo puede ser soportado dentro del marco de un lenguaje de módulo de tipo explícito viendo clases de tipos como un modo particular de uso de módulos. Esta vista ofrece una integración armoniosa de módulos y clases de tipos, donde las características de clase de tipo, como las jerarquías de clase y los tipos asociados, surgen naturalmente como usos de construcciones de lenguaje de módulo existentes, como jerarquías de módulo y componentes de tipo. Además, los programadores tienen control explícito sobre las instancias de clase de tipo que están disponibles para su uso por tipo de inferencia en un ámbito determinado. Formalizamos nuestro enfoque como una relación de elaboración de estilo Harper-Stone y proporcionamos un algoritmo de inferencia de tipo de sonido como guía para la implementación.

Answer 4

Me encontré con un artículo muy bueno que demuestra la traducción entre tipos y clases de tipos en Haskell y módulos y tipos de módulos en OCaml: http://conway.rutgers.edu/~ccshan/wiki/blog/posts/Translations/

Básicamente, como mostró @Thomas, las clases de tipos en Haskell se convierten en tipos de módulos en OCaml con un tipo (el tipo que implementa la clase de tipo) y un conjunto de valores que usan ese tipo.

Luego, correspondiente a una "instancia" de la clase de tipo en Haskell, tiene un módulo en OCaml que implementa el tipo de módulo, siendo el tipo el tipo de instancia y los valores siendo la implementación de los valores en la clase de tipo .

Y luego, cada vez que tiene una función que "usa" un tipo restringido por esa clase de tipo en Haskell, debe ajustar esa función dentro de un módulo en OCaml. Este módulo (en realidad, un funtor) tomará un módulo de argumento que corresponde a la instancia de la clase de tipo que estamos utilizando.

Y cada vez que use esa función, primero deberá crear un módulo apropiado utilizando ese funtor y pasarlo a la instancia correcta de la clase de tipo.

Notarás que una gran diferencia en las formas Haskell y OCaml de hacerlo, es que en Haskell, cuando usas esa última función, el compilador deduce la instancia adecuada de la clase de tipo para ti; mientras que con la forma OCaml de hacerlo, el usuario debe especificar explícitamente la instancia a usar.

Answer 5

Realmente depende de lo que quieras lograr.

Si está contento con la función de comparación polimórfica OCaml (que no funcionará en valores cíclicos y funcionales), simplemente puede escribir:

let my_sort l = List.sort Pervasives.compare l

La forma más genérica de imitar las clases de tipo es usar funtores:

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)