Fechamentos e quantificação universal
-
25-09-2019 - |
Pergunta
Eu tenho tentado descobrir como implementar tipos de dados codificados pela igreja em Scala. Parece que ele requer tipos de classificação-n, pois você precisaria de uma primeira classe const
função do tipo forAll a. a -> (forAll b. b -> b)
.
No entanto, pude codificar pares assim:
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)
}
Para listas, pude codificar 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))
}
}
No entanto, a lista vazia é mais problemática e não consegui fazer com que o compilador Scala unifique os tipos.
Você pode definir nulo, de modo que, dada a definição acima, as seguintes compilam?
cons(1)(cons(2)(cons(3)(nil)))
Solução
Obrigado a Mark Harrah por concluir esta solução. O truque é que Function1
Nas bibliotecas padrão não é definido de maneira geral o suficiente.
Meu traço de "fechamento" na questão é realmente uma transformação natural entre os funções. Esta é uma generalização do conceito de "função".
trait ~>[F[_],G[_]] { def apply[B](f: F[B]): G[B] }
Uma função a -> b
Então deve ser uma especialização dessa característica, uma transformação natural entre dois endofunctos na categoria de tipos de Scala.
trait Const[A] { type Apply[B] = A }
type ->:[A,B] = Const[A]#Apply ~>: Const[B]#Apply
Const[A]
é um functor que mapeia todo tipo de A
.
E aqui está o nosso tipo de lista:
type CList[A] = ({type f[x] = Fold[A,x]})#f ~> Endo
Aqui, Endo
é apenas um pseudônimo para o tipo de funções que mapeiam um tipo em si (um endofunção).
type Endo[A] = A ->: A
E Fold
são o tipo de funções que podem dobrar uma lista:
type Fold[A,B] = A ->: Endo[B]
E então, finalmente, aqui estão nossos construtores de lista:
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
}
Uma ressalva é a necessidade de converter explicitamente (a ->: b) para (a => b) para ajudar o sistema de tipos de Scala. Portanto, ainda é terrivelmente detalhado e tedioso dobrar uma lista uma vez criada. Aqui está o equivalente Haskell para comparação:
nil p z = z
cons x xs p z = p x (xs p z)
A construção da lista e a dobra na versão Haskell é concisa e sem ruído:
let xs = cons 1 (cons 2 (cons 3 nil)) in xs (+) 0