Đóng cửa và định lượng phổ quát

Question

Tôi đã cố gắng tìm hiểu cách triển khai các kiểu dữ liệu được mã hóa của Giáo Hội trong Scala. Có vẻ như nó đòi hỏi các loại rank-n vì bạn sẽ cần một hàm const hạng nhất của loại forAll a. a -> (forAll b. b -> b).

Tuy nhiên, tôi đã có thể mã hóa cặp 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) 
    } 

Đối với danh sách, tôi đã có thể mã hóa 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)) 
    } 
} 

Tuy nhiên, danh sách rỗng là có vấn đề hơn và tôi đã không thể có được trình biên dịch Scala để thống nhất các loại.

Bạn có thể xác định không, do đó, với định nghĩa ở trên, các bản dịch sau đây?

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

Answer 1

Nhờ Mark Harrah đã hoàn thành giải pháp này. Bí quyết là Function1 trong các thư viện chuẩn không được định nghĩa theo cách tổng quát.

Đặc điểm "Đóng cửa" của tôi trong câu hỏi thực sự là một sự chuyển đổi tự nhiên giữa các functors. Đây là khái quát về khái niệm "hàm".

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

Một chức năng a -> b sau đó nên được một chuyên môn của đặc điểm này, một sự biến đổi tự nhiên giữa hai endofunctors trên chủng loại loại Scala.

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

Const[A] là một functor ánh xạ mọi loại tới A.

Và đây là loại danh sách của chúng tôi:

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

Ở đây, Endo chỉ là một bí danh cho các loại chức năng mà bản đồ một loại vào bản thân (một endofunction).

type Endo[A] = A ->: A 

Và Fold là loại chức năng mà có thể gấp một danh sách:

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

Và cuối cùng, đây là nhà xây dựng danh sách của chúng tôi:

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 
} 

Một caveat là sự cần thiết phải chuyển đổi rõ ràng (A ->: B) thành (A => B) để giúp hệ thống kiểu Scala cùng. Vì vậy, nó vẫn khủng khiếp tiết tú và tẻ nhạt để thực sự gấp một danh sách sau khi tạo ra. Đây là Haskell tương đương để so sánh:

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

Danh sách xây dựng và gấp trong phiên bản Haskell là ngắn gọn và tiếng ồn miễn phí:

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