Les bouclages et la quantification universelle
-
25-09-2019 - |
Question
J'ai essayé de trouver comment mettre en œuvre les types de données codées-Eglise à Scala. Il semble qu'il exige des types de rang n puisque vous auriez besoin d'une première classe fonction const
de type forAll a. a -> (forAll b. b -> b)
.
Cependant, j'ai pu encoder des paires ainsi:
import scalaz._
trait Compose[F[_],G[_]] { type Apply = F[G[A]] }
trait Closure[F[_],G[_]] { def apply[B](f: F[B]): G[B] }
def pair[A,B](a: A, b: B) =
new Closure[Compose[({type f[x] = A => x})#f,
({type f[x] = B => x})#f]#Apply, Id] {
def apply[C](f: A => B => C) = f(a)(b)
}
Pour les listes, j'ai pu coder cons
:
def cons[A](x: A) = {
type T[B] = B => (A => B => B) => B
new Closure[T,T] {
def apply[B](xs: T[B]) = (b: B) => (f: A => B => B) => f(x)(xs(b)(f))
}
}
Cependant, la liste vide est plus problématique et je n'ai pas été en mesure d'obtenir le compilateur Scala pour unifier les types.
Pouvez-vous définir nulle, de sorte que, compte tenu de la définition ci-dessus, les compiles suivants?
cons(1)(cons(2)(cons(3)(nil)))
La solution
Merci à Mark Harrah pour compléter cette solution. L'astuce est que Function1
dans les bibliothèques standard n'est pas définie d'une manière assez générale.
Mon trait « fermeture » dans la question est en fait une transformation naturelle entre foncteurs. Ceci est une généralisation du concept de « fonction ».
trait ~>[F[_],G[_]] { def apply[B](f: F[B]): G[B] }
Une fonction a -> b
doit donc être une spécialisation de cette caractéristique, une transformation naturelle entre deux endofunctors de la catégorie de types Scala.
trait Const[A] { type Apply[B] = A }
type ->:[A,B] = Const[A]#Apply ~>: Const[B]#Apply
Const[A]
est un foncteur qui associe tous les types de A
.
Et voici notre type de liste:
type CList[A] = ({type f[x] = Fold[A,x]})#f ~> Endo
Ici, Endo
est juste un alias pour le type de fonctions qui tracent un type sur lui-même ( endofonction ).
type Endo[A] = A ->: A
Et Fold
est le type de fonctions qui peuvent se replier une liste:
type Fold[A,B] = A ->: Endo[B]
Et puis enfin, voici nos constructeurs de liste:
def cons[A](x: A) = {
new (CList[A] ->: CList[A]) {
def apply[C](xs: CList[A]) = new CList[A] {
def apply[B](f: Fold[A,B]) = (b: B) => f(x)(xs(f)(b))
}
}
}
def nil[A] = new CList[A] {
def apply[B](f: Fold[A,B]) = (b: B) => b
}
Une mise en garde est la nécessité de convertir explicitement (A -> B) à (A => B) pour aider le système de type Scala le long. Il est donc encore terriblement bavard et fastidieux à plier en fait une liste une fois créée. Voici le Haskell équivalent à titre de comparaison:
nil p z = z
cons x xs p z = p x (xs p z)
Liste de construction et de pliage dans la version Haskell est laconique et sans bruit:
let xs = cons 1 (cons 2 (cons 3 nil)) in xs (+) 0