Phép trừ số nhà thờ trong haskell

Question

Tôi đang cố gắng để thực hiện các số nhà thờ trong Haskell, nhưng tôi đã gặp phải một vấn đề nhỏ. Haskell phàn nàn của một loại vô hạn với

Xảy ra kiểm tra: không thể xây dựng các loại vô hạn: t = (t -> t1) -> (t1 -> t2) -> t2

khi tôi cố gắng và làm phép trừ. Tôi 99% tích cực rằng tính toán lambda của tôi là hợp lệ (mặc dù nếu nó không phải là, xin vui lòng cho tôi biết). Những gì tôi muốn biết, là liệu có bất kỳ điều gì tôi có thể làm để làm cho haskell làm việc với các chức năng của tôi.

module Church where 

type (Church a) = ((a -> a) -> (a -> a)) 

makeChurch :: Int -> (Church a) 
makeChurch 0 = \f -> \x -> x 
makeChurch n = \f -> \x -> f (makeChurch (n-1) f x) 

numChurch x = (x succ) 0 

showChurch x = show $ numChurch x 

succChurch = \n -> \f -> \x -> f (n f x) 

multChurch = \f2 -> \x2 -> \f1 -> \x1 -> f2 (x2 f1) x1 

powerChurch = \exp -> \n -> exp (multChurch n) (makeChurch 1) 

predChurch = \n -> \f -> \x -> n (\g -> \h -> h (g f)) (\u -> x) (\u -> u) 

subChurch = \m -> \n -> (n predChurch) m 

Answer 1

Định nghĩa này là predChurchdoesn't work in simply typed lambda calculus, chỉ trong phiên bản chưa được nhập. Bạn có thể tìm thấy phiên bản predChurch hoạt động trong Haskell here.

Answer 2

Vấn đề là predChurch là quá đa hình được suy luận chính xác theo suy luận kiểu Hindley-Milner. Ví dụ: bạn có thể viết:

predChurch :: Church a -> Church a 
predChurch = \n -> \f -> \x -> n (\g -> \h -> h (g f)) (\u -> x) (\u -> u) 

nhưng loại này không chính xác. A Church a lấy làm đối số đầu tiên của nó là a -> a, nhưng bạn đang vượt qua n một hàm hai đối số, rõ ràng là lỗi loại.

Vấn đề là Church a không mô tả đúng số nhà thờ. Số nhà thờ chỉ đơn giản là đại diện cho một số - thông số loại đó có ý nghĩa gì trên trái đất? Ví dụ:

foo :: Church Int 
foo f x = f x `mod` 42 

Lỗi đánh máy đó, nhưng chắc chắn không phải là số nhà thờ. Chúng ta cần phải hạn chế loại. Số của Giáo hội cần phải làm việc cho bất kỳa, không chỉ là a cụ thể. Định nghĩa chính xác là:

type Church = forall a. (a -> a) -> (a -> a) 

Bạn cần có {-# LANGUAGE RankNTypes #-} ở đầu tệp để bật các loại như thế này.

Bây giờ chúng ta có thể cung cấp cho các loại chữ ký, chúng tôi mong đợi:

predChurch :: Church -> Church 
-- same as before 

Bạn phải cho một chữ ký kiểu ở đây vì loại hạng cao hơn được không inferrable bởi Hindley-Milner.

Tuy nhiên, khi chúng tôi đi đến thực hiện subChurch vấn đề khác được đặt ra:

Couldn't match expected type `Church' 
     against inferred type `(a -> a) -> a -> a' 

Tôi không chắc chắn 100% lý do tại sao điều này xảy ra, tôi nghĩ rằng forall đang được quá tự do mở ra bởi các typechecker. Nó không làm tôi ngạc nhiên; các loại xếp hạng cao hơn có thể hơi giòn vì những khó khăn mà chúng xuất hiện cho trình biên dịch.Ngoài ra, chúng tôi không nên sử dụng một số type để trừu tượng trừu tượng, chúng tôi sẽ sử dụng newtype (điều này giúp chúng tôi linh hoạt hơn trong định nghĩa, giúp trình biên dịch có đánh máy và đánh dấu những nơi chúng tôi sử dụng việc triển khai trừu tượng) :

newtype Church = Church { unChurch :: forall a. (a -> a) -> (a -> a) } 

và chúng ta phải sửa đổi predChurch để cuộn và cuộn khi cần thiết:

predChurch = \n -> Church $ 
    \f -> \x -> unChurch n (\g -> \h -> h (g f)) (\u -> x) (\u -> u) 

Cùng với subChurch:

subChurch = \m -> \n -> unChurch n predChurch m 

Nhưng chúng tôi không cần chữ ký kiểu nữa - có đủ thông tin trong cuộn/bỏ chọn để suy ra các loại một lần nữa.

Tôi luôn khuyên bạn nên newtype giây khi tạo một trừu tượng mới. Thường xuyên type từ đồng nghĩa khá hiếm trong mã của tôi.

Answer 3

Tôi đã gặp phải vấn đề tương tự. Và tôi đã giải quyết nó mà không cần thêm chữ ký kiểu.

Đây là giải pháp, với conscar được sao chép từ SICP.

cons x y = \m -> m x y 
car z = z (\p q -> p) 
cdr z = z (\p q -> q) 

next z = cons (cdr z) (succ (cdr z)) 
pred n = car $ n next (cons undefined zero) 

sub m n = n pred m 

Bạn có thể tìm nguồn đầy đủ here.

Tôi thực sự ngạc nhiên sau khi viết sub m n = n pred m và tải nó bằng ghci mà không có lỗi loại!

Mã Haskell thật ngắn gọn! :-)