Giá trị của kiểu dữ liệu đại số đệ quy được mã hóa đa hình là gì?

Question

Câu hỏi sau liên quan đến Recursive algebraic data types via polymorphism in Haskell.

Loại dữ liệu đại số đệ quy có thể được thực hiện bằng bất kỳ ngôn ngữ nào có khả năng của Hệ thống F sử dụng đa hình tham số phổ quát. Ví dụ, loại số tự nhiên có thể được giới thiệu (trong Haskell) như

newtype Nat = Nat { runNat :: forall t. (t -> (t -> t) -> t) } 

với 'bình thường' số tự nhiên n được thực hiện như

\ x0 f -> f(f(...(f x0)...)) 

với n lặp của f sử dụng.

Tương tự, các loại Booleans có thể được giới thiệu như là

newtype Bool = Bool { runBool :: forall t. t -> t -> t } 

với các giá trị dự kiến ​​'true' và 'sai' được thực hiện như

true = \ t f -> t 
false = \ t f -> f 

Q: Có phải tất cả về loại Bool hoặc Nat hoặc bất kỳ loại dữ liệu đại số có khả năng đệ quy nào khác (được mã hóa theo cách này) của biểu mẫu trên, tối đa một số quy tắc giảm của ngữ nghĩa hoạt động?

Ví dụ 1 (số tự nhiên): Là bất kỳ hạn của loại forall t. t -> (t -> t) -> t 'tương đương' trong một số ý nghĩa với thời hạn dưới hình thức \ x0 f -> f (f (... (f x0) ...))?

Ví dụ 2 (Booleans): Là bất kỳ hạn của loại forall t. t -> t -> t 'tương đương' trong một nghĩa nào đó cho một trong hai \ t f -> t hoặc \ t f -> f?

Phụ Lục (phiên bản nội bộ): Trong trường hợp các ngôn ngữ đang được xem xét thậm chí còn có khả năng thể hiện sự bình đẳng mệnh đề, câu hỏi meta-toán học này có thể được internalized như sau, và tôi sẽ rất hạnh phúc nếu ai đó sẽ đưa ra một giải pháp cho nó:

đối với bất kỳ functor m chúng ta có thể xác định các mô-đun phổ quát và một số chức năng giải mã mã hóa trên đó như sau:

type ModStr m t = m t -> t 
UnivMod m = UnivMod { univProp :: forall t. (ModStr m t) -> t } 

classifyingMap :: forall m. forall t. (ModStr m t) -> (UnivMod m -> t) 
classifyingMap f = \ x -> (univProp x) f 

univModStr :: (Functor m) => ModStr m (UnivMod m) 
univModStr = \ f -> UnivMod $ \ g -> g (fmap (classifyingMap g) f) 

dec_enc :: (Functor m) => UnivMod m -> UnivMod m 
dec_enc x = (univProp x) univModStr 

Q : Trong trường hợp ngôn ngữ có khả năng diễn đạt điều này: là loại bình đẳng dec_enc = id có người ở không?

Answer 1

Trong hệ thống F (AKA λ2), tất cả các cư dân của ∀α.α→α→α có thực sự λ tương đương với K hoặc K*.

Thứ nhất, nếu M : ∀α.α→α→α sau đó nó có hình thức bình thường N (kể từ khi hệ thống F được bình thường) và bởi lý giảm đối tượng (xem Barendregt: Lambda calculi with types) cũng N : ∀α.α→α→α.

Hãy xem xét cách các biểu mẫu bình thường này trông như thế nào. (Chúng tôi sẽ sử dụng Bổ đề thế hệ cho λ2, xem cuốn sách của Barendregt để biết chi tiết chính thức.)

Nếu một hình thức bình thường, N (hoặc bất kỳ biểu thức con nào) phải ở dạng bình thường, đó là một biểu thức có dạng λx1 ... xn. y P1 ... Pk, nơi n và/hoặc k có thể cũng 0.

Đối với trường hợp N, phải có ít nhất một λ, bởi vì ban đầu chúng tôi không có bất kỳ biến ràng buộc trong bối cảnh mà có thể gõ thay thế y. Vì vậy, N = λx.U và x:α |- U:α→α.

Bây giờ lại phải có ít nhất một λ trong trường hợp U, bởi vì nếu U chỉ là y P1 ... Pk sau đó y sẽ có một loại chức năng (ngay cả đối với k = 0 chúng tôi cần y:α→α), nhưng chúng ta chỉ x:α trong bối cảnh. Vì vậy, N = λxy.V và x:α, y:α |- V:α.

Nhưng V không thể là λ.., vì sau đó nó sẽ có loại chức năng τ→σ. Vì vậy, V phải là dạng z P1 ... Pk, nhưng vì chúng tôi không có bất kỳ loại chức năng nào trong ngữ cảnh, k phải bằng 0 và do đó V chỉ có thể là x hoặc y.

Vì vậy, chỉ có hai cụm từ ở dạng bình thường của loại ∀α.α→α→α: λxy.x và λxy.y và tất cả các cụm từ khác thuộc loại này bằng β bằng một trong số các cụm từ này.

---

Sử dụng lý do tương tự chúng tôi có thể chứng minh rằng tất cả các cư dân của ∀α.α→(α→α)→α đều bằng số nhà thờ. (Và tôi nghĩ rằng đối với loại ∀α.(α→α)→α→α tình hình là hơi tồi tệ hơn;. Chúng ta cũng cần η-bình đẳng, như λf.f và λfx.fx tương ứng với 1, nhưng không phải là β-bình đẳng, chỉ βη-tương đương)

Answer 2

Nếu chúng ta bỏ qua đáy và công cụ unsafe, thì điều duy nhất bạn có thể làm phổ biến với chức năng a -> a là soạn chúng. Tuy nhiên, điều đó không hoàn toàn ngăn cản chúng tôi tại các biểu thức hữu hạn f (f (... (f x0) ...)): chúng tôi cũng có thành phần vô hạn infty x f = f $ infty x f.

Tương tự, chỉ không đệ quy các giá trị boolean có thực sự \t _ -> t và \_ f -> f, nhưng bạn cũng có thể buộc hải lý ở đây, như

blarg t f = blarg (blarg t f) (blarg f t)