Verschlüsse und universelle Quantifizierung

Question

Ich habe versucht, herauszufinden, wie Church-codierte Datentypen in Scala implementiert werden. Es scheint, dass es Rang-n-Typen erfordert, da Sie eine erstklassige const-Funktion des Typs forAll a. a -> (forAll b. b -> b) benötigen.

aber ich in der Lage war Paare zu kodieren thusly:

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) 
    } 

Für Listen, ich war in der Lage zu kodieren 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)) 
    } 
} 

jedoch die leere Liste ist problematischer und ich habe nicht in der Lage, den Scala-Compiler zu bekommen, um die Typen zu vereinheitlichen.

Können Sie Nil definieren, so dass die folgenden Kompilierungen gemäß der obigen Definition vorliegen?

cons(1)(cons(2)(cons(3)(nil))) 

Answer 1

Dank Mark Harrah für die Fertigstellung dieser Lösung. Der Trick ist, dass Function1 in den Standardbibliotheken nicht allgemein genug definiert ist.

Meine "Closure" Eigenschaft in der Frage ist eigentlich eine natürliche Transformation zwischen Funktoren. Dies ist eine Verallgemeinerung des Begriffs "Funktion".

trait ~>[F[_],G[_]] { def apply[B](f: F[B]): G[B] } 

Eine Funktion a -> b dann sollte eine Spezialisierung dieses Merkmal sein, eine natürliche Transformation zwischen zwei endofunctors auf die Kategorie der Scala Typen.

trait Const[A] { type Apply[B] = A } 
type ->:[A,B] = Const[A]#Apply ~>: Const[B]#Apply 

Const[A] ist ein Funktor, der jede Art zu A abbildet.

Und hier ist unsere Liste Typ:

type CList[A] = ({type f[x] = Fold[A,x]})#f ~> Endo 

Hier Endo nur ein Alias ​​für die Art von Funktionen, die eine Art auf sich selbst abbilden (ein endofunction).

type Endo[A] = A ->: A 

Und Fold ist die Art von Funktionen, die eine Liste falten kann:

type Fold[A,B] = A ->: Endo[B] 

Und dann endlich, hier sind unsere Liste Bauer:

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 
} 

Ein Nachteil ist die Notwendigkeit, konvertiere explizit (A ->: B) in (A => B), um Scalas Typsystem zu unterstützen. Es ist also immer noch schrecklich langwierig, eine einmal erstellte Liste zu falten. Hier ist das Äquivalent Haskell zum Vergleich:

nil p z = z 
cons x xs p z = p x (xs p z) 

Liste Bau und in der Haskell-Version Falten ist kurz und bündig und rauschfrei:

let xs = cons 1 (cons 2 (cons 3 nil)) in xs (+) 0