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
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í:
Aquí, definimos
mu1
como una función de orden superior que toma dos argumentos: una funciónf
que asigna un funtor a nivel de tipop
a una función(p -> 'a -> 'a)
, y una funciónunF
que asigna un funtor a nivel de tipop
a una función(p -> 'a)
. La funciónmu1
construye el punto fijo del funtorf
utilizando un módulo de orden superiorF
que codifica un funtor como un par de funciones. El punto fijo se obtiene aplicando las funcionesmap
yunF
al par de funciones y luego aplicandofix
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 parametrizadop
que representa los sub-árboles, y devuelve el punto fijo de un funtor que puede ser un nodoLeaf
con un valora
o un nodoNode
con dos sub-árboles. Finalmente, definimos las funcionesleaf
ynode
que construyen árboles perfectos utilizando la funciónmu1
y el funtorPerfectF
.