Zamknięcia i uniwersalne kwantyfikacja

Question

Próbowałem dowiedzieć się, jak wdrożyć kodowane przez Kościół typy danych w Scali. Wygląda na to, że wymaga on typów rang-n, ponieważ potrzebna byłaby pierwsza funkcja klasy const typu forAll a. a -> (forAll b. b -> b).

Jednak udało mi się zakodować pary wygląda następująco:

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

przypadku list, byłem w stanie zakodować 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)) 
    } 
} 

jednak pusta lista jest bardziej problematyczne i mam nie udało się uzyskać kompilatora Scala w celu ujednolicenia typów.

Czy można zdefiniować zero, tak, biorąc pod uwagę powyższą definicję, następujące kompiluje?

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

Answer 1

Podziękowania dla Marka Harraha za uzupełnienie tego rozwiązania. Sztuczka polega na tym, że Function1 w standardowych bibliotekach nie jest wystarczająco ogólny zdefiniowany.

Moja cecha "Zamknięcie" w tym pytaniu jest w rzeczywistości naturalną transformacją między funktorami. Jest to uogólnienie pojęcia "funkcja".

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

Funkcja a -> b następnie powinna być specjalizacja tej cechy, naturalna transformacja między dwoma endofunctors od kategorii typów Scala.

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

Const[A] to funktor, który odwzorowuje każdy rodzaj do A.

A oto nasza lista typ:

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

Tutaj Endo tylko aliasem dla typu funkcji, które zmapować typu na siebie (AN endofunction).

type Endo[A] = A ->: A 

I Fold to rodzaj funkcji, które można złożyć listę:

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

i wreszcie, oto nasze lista konstruktorów:

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 
} 

Jedno zastrzeżenie jest konieczne jawnie przekonwertuj (A ->: B) do (A => B), aby pomóc systemowi Scala. Tak więc wciąż jest strasznie gadatliwa i nużąca, aby faktycznie spasować listę raz stworzoną. Oto odpowiednik Haskell Dla porównania:

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

budowy listy i składane w wersji Haskell jest lakoniczny i wolne od szumów:

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