Закрытие и универсальное количество количественной оценки
-
25-09-2019 - |
Вопрос
Я пытался выработать, как реализовать типы данных, закодированные церкви в Scala. Похоже, что это требует типа ранга, так как вам понадобится первый класс const
Функция типа forAll a. a -> (forAll b. b -> b)
.
Тем не менее, я смог кодировать пары таким образом:
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)
}
Для списков я смог кодировать 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))
}
}
Однако пустой список более проблематичен, и я не смог заставить компилятор Scala унифицировать типы.
Можете ли вы определить Nil, так что, учитывая определение выше, следующие компиляции?
cons(1)(cons(2)(cons(3)(nil)))
Решение
Благодаря Марку Харруру за завершение этого решения. Хитрость в том, что Function1
В стандартных библиотеках не определяется в целом достаточно.
Моя «закрытие» черта в вопросе на самом деле является естественной трансформацией между функторами. Это обобщение концепции «функции».
trait ~>[F[_],G[_]] { def apply[B](f: F[B]): G[B] }
Функция a -> b
Тогда должна быть специализация этой черты, естественным преобразованием между двумя эндомундуками на категории типов Scala.
trait Const[A] { type Apply[B] = A }
type ->:[A,B] = Const[A]#Apply ~>: Const[B]#Apply
Const[A]
это функтор, который отображает каждый тип, чтобы A
.
И вот наш тип списка:
type CList[A] = ({type f[x] = Fold[A,x]})#f ~> Endo
Здесь, Endo
это просто псевдоним для типа функций, которые отображают тип на себя ( эндофункция).
type Endo[A] = A ->: A
А также Fold
Является ли тип функций, которые могут сложить список:
type Fold[A,B] = A ->: Endo[B]
А потом, наконец, вот наш список конструкторов:
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
}
Одно предостережение - это необходимость явного преобразования (A ->: b) (a => b), чтобы помочь системе Тип Scala. Так что это все еще ужасно многословно и утомительно, чтобы фактически сложить список после создания. Вот эквивалентный Haskell для сравнения:
nil p z = z
cons x xs p z = p x (xs p z)
Список Строительство и складные в версии Haskell Terse и без шума:
let xs = cons 1 (cons 2 (cons 3 nil)) in xs (+) 0