Codificación para funtores de orden superior con polimorfismo de tipos superiores más liviano.

Desafortunadamente, OCaml no acepta variables de tipo que abarquen constructores de tipos:

'a option, 'a list son válidos, pero 'a 'm no lo es.

Gracias a los funtores (ver so/Fix data type in OCaml) podemos codificar un punto fijo y rango sobre un constructor de tipos.
También podemos evitar el uso de módulos y utilizar solo Ocaml a nivel de valor (Lightweight higher kind ver higher y higher_kind)

Algunas estructuras de datos como los árboles perfectos pueden describirse como un punto fijo de un “functor de orden superior”: el equivalente al “constructor de tipo subyacente” que, antes de tomar el punto fijo, mapea un constructor de tipo (p: * -> *) a otro constructor de tipo * -> *.

¿Podemos codificar árboles perfectos como tal punto fijo utilizando el enfoque a nivel de valor (LHK) de la biblioteca higher/higher_kind ?

haskell

Perfect = Mu1 (p : ->). Id + p ∘ Δ

donde

haskell

Δ : * -> *

type Δ a = (a,a)

en haskell

-- stack --resolver lts-17.10 script {-# LANGUAGE StandaloneKindSignatures #-} module SOPerfectTree where type Perfect :: * -> * type Perfect a = Mu1 PerfectF a type Mu1 :: ((* -> *) -> * -> *) -> * -> * newtype Mu1 f a = In {unIn :: f (Mu1 f) a} type PerfectF :: (* -> *) -> * -> * data PerfectF f a = Leaf a | Node (f (a, a))

davy.ai

July 29, 2023 at 7:15 am

Sí, podemos codificar árboles perfectos como un punto fijo utilizando el enfoque de nivel de valor (LHK) de la biblioteca higher/higher_kind. La codificación se vería así:

open Higher

let mu1 : type p. (p -> 'a -> 'a) -> (p -> 'a) -> 'a =
  fun (type f) (f : f -> 'a -> 'a) (unF : f -> 'a) ->
    let module F = struct
      type 'a t = F of (f -> 'a -> 'a) * (f -> 'a)
      let map (F (f, unF)) g = F (f, fun x -> g (unF x))
      let unF (F (_, x)) = x
    end in
    let rec fix (x : F('a t)) : 'a =
      let F (f, unF) = x in
      unF (f (map x fix))
    in
    fix (F (f, unF))

type ('a, 'b) delta = 'a * 'b

type ('a, 'p) perfect = ('p -> 'a * 'a, 'a) mu1

let leaf a : ('a, 'p) perfect = mu1 (fun _ a -> Leaf a) (fun _ -> a)

let node (ta, tb : ('a, 'p) perfect * ('b, 'p) perfect)
  : ('a * 'b, 'p) perfect =
  mu1 (fun p (a, b) -> Node (ta p a, tb p b))
       (fun p -> (ta p, tb p))

Aquí, definimos mu1 como una función de orden superior que toma dos argumentos: una función f que asigna un funtor a nivel de tipo p a una función (p -> 'a -> 'a), y una función unF que asigna un funtor a nivel de tipo p a una función (p -> 'a). La función mu1 construye el punto fijo del funtor f utilizando un módulo de orden superior F que codifica un funtor como un par de funciones. El punto fijo se obtiene aplicando las funciones map y unF al par de funciones y luego aplicando fix al resultado.

Luego definimos un constructor delta a nivel de tipo que toma dos tipos y devuelve su producto cartesiano. También definimos un constructor de árboles perfectos a nivel de tipo que toma dos parámetros de tipo, un tipo de elemento a y un tipo parametrizado p que representa los sub-árboles, y devuelve el punto fijo de un funtor que puede ser un nodo Leaf con un valor a o un nodo Node con dos sub-árboles. Finalmente, definimos las funciones leaf y node que construyen árboles perfectos utilizando la función mu1 y el funtor PerfectF.

Answer

davy.ai

July 29, 2023 at 7:15 am
Sí, podemos codificar árboles perfectos como un punto fijo utilizando el enfoque de nivel de valor (LHK) de la biblioteca higher/higher_kind. La codificación se vería así:
```
open Higher

let mu1 : type p. (p -> 'a -> 'a) -> (p -> 'a) -> 'a =
  fun (type f) (f : f -> 'a -> 'a) (unF : f -> 'a) ->
    let module F = struct
      type 'a t = F of (f -> 'a -> 'a) * (f -> 'a)
      let map (F (f, unF)) g = F (f, fun x -> g (unF x))
      let unF (F (_, x)) = x
    end in
    let rec fix (x : F('a t)) : 'a =
      let F (f, unF) = x in
      unF (f (map x fix))
    in
    fix (F (f, unF))

type ('a, 'b) delta = 'a * 'b

type ('a, 'p) perfect = ('p -> 'a * 'a, 'a) mu1

let leaf a : ('a, 'p) perfect = mu1 (fun _ a -> Leaf a) (fun _ -> a)

let node (ta, tb : ('a, 'p) perfect * ('b, 'p) perfect)
  : ('a * 'b, 'p) perfect =
  mu1 (fun p (a, b) -> Node (ta p a, tb p b))
       (fun p -> (ta p, tb p))
```
Aquí, definimos mu1 como una función de orden superior que toma dos argumentos: una función f que asigna un funtor a nivel de tipo p a una función (p -> 'a -> 'a), y una función unF que asigna un funtor a nivel de tipo p a una función (p -> 'a). La función mu1 construye el punto fijo del funtor f utilizando un módulo de orden superior F que codifica un funtor como un par de funciones. El punto fijo se obtiene aplicando las funciones map y unF al par de funciones y luego aplicando fix al resultado.

Luego definimos un constructor delta a nivel de tipo que toma dos tipos y devuelve su producto cartesiano. También definimos un constructor de árboles perfectos a nivel de tipo que toma dos parámetros de tipo, un tipo de elemento a y un tipo parametrizado p que representa los sub-árboles, y devuelve el punto fijo de un funtor que puede ser un nodo Leaf con un valor a o un nodo Node con dos sub-árboles. Finalmente, definimos las funciones leaf y node que construyen árboles perfectos utilizando la función mu1 y el funtor PerfectF.

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

Codificación para funtores de orden superior con polimorfismo de tipos superiores más liviano.

Answer

davy.ai