Abschlüsse und universelle Quantifizierung

Question

Ich habe versucht herauszufinden, wie ich von der Kirche kodierte Datentypen in Scala implementieren kann.Es scheint, dass es Rang-n-Typen erfordert, da Sie einen erstklassigen benötigen würden const Funktion des Typs forAll a. a -> (forAll b. b -> b).

Allerdings konnte ich Paare folgendermaßen kodieren:

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

Allerdings ist die leere Liste problematischer und ich konnte den Scala-Compiler nicht dazu bringen, die Typen zu vereinheitlichen.

Können Sie nil definieren, sodass bei gegebener Definition oben Folgendes kompiliert wird?

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

Answer 1

Vielen Dank an Mark Harrah für die Vervollständigung dieser Lösung.Der Trick ist das Function1 in den Standardbibliotheken ist nicht allgemein genug definiert.

Mein „Abschluss“-Merkmal 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 es eine Spezialisierung dieses Merkmals geben, eine natürliche Transformation zwischen zwei Endofunktoren in der 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, dem jeder Typ zugeordnet wird A.

Und hier ist unser Listentyp:

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

Hier, Endo ist nur ein Alias ​​für den Funktionstyp, der einen Typ auf sich selbst abbildet (an Endofunktion).

type Endo[A] = A ->: A

Und Fold ist die Art von Funktionen, die eine Liste falten können:

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

Und schließlich sind hier unsere Listenkonstruktoren:

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
}

Eine Einschränkung besteht darin, dass eine explizite Konvertierung erforderlich ist (A ->:B) zu (A => B), um Scalas Typensystem weiterzuentwickeln.Daher ist es immer noch furchtbar ausführlich und mühsam, eine einmal erstellte Liste tatsächlich zu falten.Hier ist das entsprechende Haskell zum Vergleich:

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

Die Listenkonstruktion und -faltung in der Haskell-Version ist knapp und geräuschlos:

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