Tại sao loại chức năng này (a -> a) -> a?

Question

Tại sao loại chức năng này (a -> a) -> a?

Prelude> let y f = f (y f) 
Prelude> :t y 
y :: (t -> t) -> t 

Đây có phải là loại vô hạn/đệ quy không? Tôi sẽ cố gắng và đưa vào từ những gì tôi nghĩ rằng đó là loại, nhưng tôi chỉ không thể làm điều đó vì một lý do nào đó.

y :: (t -> t) -> ?WTFIsGoingOnOnTheRHS? 

Tôi không hiểu cách f (y f) giải quyết một giá trị. Những điều sau đây có ý nghĩa hơn một chút đối với tôi:

Prelude> let y f x = f (y f) x 
Prelude> :t y 
y :: ((a -> b) -> a -> b) -> a -> b 

Nhưng nó vẫn vô cùng khó hiểu. Chuyện gì vậy?

Answer 1

Vâng, y phải thuộc loại (a -> b) -> c, đối với một số a, b và c chúng tôi chưa biết; sau khi tất cả, nó có một hàm, f và áp dụng nó cho một đối số, do đó, nó phải là một hàm lấy hàm.

Kể từ y f = f x (một lần nữa, đối với một số x), chúng ta biết rằng kiểu trả về của y phải là kiểu trả về của f riêng của mình. Vì vậy, chúng tôi có thể tinh chỉnh loại y một chút: phải là (a -> b) -> b đối với một số a và b mà chúng tôi chưa biết.

Để tìm hiểu xem a là gì, chúng tôi chỉ cần xem loại giá trị được chuyển đến f. Đó là y f, là biểu thức mà chúng tôi đang cố gắng tìm ra loại ngay bây giờ. Chúng tôi đang nói rằng loại y là (a -> b) -> b (đối với một số a, b, v.v.), vì vậy chúng tôi có thể nói rằng ứng dụng này là y f phải thuộc loại b.

Vì vậy, loại đối số là f là b. Đặt tất cả lại với nhau, và chúng tôi nhận được (b -> b) -> b - đó là, tất nhiên, cùng một điều như (a -> a) -> a.

Dưới đây là chế độ xem trực quan hơn nhưng kém chính xác hơn: chúng tôi đang nói rằng y f = f (y f), chúng tôi có thể mở rộng đến tương đương y f = f (f (y f)), y f = f (f (f (y f))), v.v. Vì vậy, chúng ta biết rằng chúng ta luôn có thể áp dụng f xung quanh toàn bộ điều, và vì "toàn bộ điều" trong câu hỏi là kết quả của việc áp dụng f cho một đối số, f phải có loại a -> a; và kể từ khi chúng tôi kết luận rằng toàn bộ điều là kết quả của việc áp dụng f cho một đối số, kiểu trả về của y phải là của số f chính nó - đến với nhau, một lần nữa, như (a -> a) -> a.

Answer 2

@ ehird đã thực hiện tốt công việc giải thích loại, vì vậy tôi muốn hiển thị cách nó có thể giải quyết cho một giá trị bằng một số ví dụ.

f1 :: Int -> Int 
f1 _ = 5 

-- expansion of y applied to f1 
y f1 
f1 (y f1) -- definition of y 
5   -- definition of f1 (the argument is ignored) 

-- here's an example that uses the argument, a factorial function 
fac :: (Int -> Int) -> (Int -> Int) 
fac next 1 = 1 
fac next n = n * next (n-1) 

y fac :: Int -> Int 
fac (y fac) -- def. of y 
    -- at this point, further evaluation requires the next argument 
    -- so let's try 3 
fac (y fac) 3 :: Int 
3 * (y fac) 2    -- def. of fac 
3 * (fac (y fac) 2)  -- def. of y 
3 * (2 * (y fac) 1)  -- def. of fac 
3 * (2 * (fac (y fac) 1) -- def. of y 
3 * (2 * 1)    -- def. of fac 

Bạn có thể thực hiện theo các bước tương tự với bất kỳ chức năng nào bạn muốn xem điều gì sẽ xảy ra. Cả hai ví dụ này hội tụ với các giá trị, nhưng điều đó không phải lúc nào cũng xảy ra.

Answer 3

Để tôi kể về một bộ tổ hợp.Nó được gọi là "fixpoint combinator" và nó có tính chất sau:

Các tài sản: các "fixpoint combinator" mất chức năng f :: (a -> a) và phát hiện ra một "điểm cố định" x :: a của chức năng đó mà f x == x. Một số triển khai của bộ kết hợp điểm cố định có thể tốt hơn hoặc tệ hơn khi "khám phá", nhưng giả sử nó kết thúc, nó sẽ tạo ra một điểm cố định của hàm đầu vào. Bất kỳ hàm nào thỏa mãn Thuộc tính đều có thể được gọi là "bộ kết hợp điểm cố định".

Gọi "bộ kết hợp điểm cố định" y này. Dựa trên những gì chúng tôi vừa nói, những điều sau đây là đúng:

-- as we said, y's input is f :: a -> a, and its output is x :: a, therefore 
y :: (a -> a) -> a 

-- let x be the fixed point discovered by applying f to y 
y f == x -- because y discovers x, a fixed point of f, per The Property 
f x == x -- the behavior of a fixed point, per The Property 

-- now, per substitution of "x" with "f x" in "y f == x" 
y f == f x 
-- again, per substitution of "x" with "y f" in the previous line 
y f == f (y f) 

Vì vậy, có bạn đi. Bạn có được xác địnhy về mặt tài sản thiết yếu của bộ kết hợp điểm cố định:
y f == f (y f). Thay vì giả định rằng y f phát hiện x, bạn có thể giả định rằng x đại diện cho một tính toán khác nhau và vẫn đến cùng một kết luận (iinm).

Vì hàm của bạn thỏa mãn Thuộc tính, chúng tôi có thể kết luận rằng đó là bộ kết hợp điểm cố định và các thuộc tính khác mà chúng tôi đã nêu, bao gồm loại, được áp dụng cho chức năng của bạn.

Đây không phải là bằng chứng vững chắc, nhưng tôi hy vọng nó cung cấp thông tin chi tiết bổ sung.

Answer 4

Chỉ cần thêm hai điểm để thêm vào câu trả lời của người khác.

Hàm bạn đang xác định thường được gọi là fix và là fixed-point combinator: một hàm tính toán fixed point của một hàm khác. Trong toán học, điểm cố định của hàm f là đối số x sao cho f x = x. Điều này đã cho phép bạn suy ra rằng loại fix phải là (a -> a) -> a; "chức năng có chức năng từ a đến a và trả lại a".

Bạn đã được gọi là chức năng của bạn y, mà có vẻ là sau khi Y combinator, nhưng đây là một cái tên không chính xác: các combinator Y là một cụ combinator điểm cố định, nhưng không giống như một trong những bạn đã xác định đây.

Tôi không hiểu cách f (y f) phân giải thành giá trị.

Vâng, mẹo là Haskell là ngôn ngữ không nghiêm ngặt (a.k.a. "lazy"). Việc tính toán f (y f) có thể chấm dứt nếu f không cần phải đánh giá đối số y f của mình trong mọi trường hợp. Vì vậy, nếu bạn định nghĩa giai thừa (như John L minh họa), fac (y fac) 1 sẽ đánh giá 1 mà không đánh giá y fac.

Ngôn ngữ nghiêm ngặt không thể thực hiện việc này, vì vậy trong những ngôn ngữ đó, bạn không thể xác định bộ kết hợp điểm cố định theo cách này. Trong những ngôn ngữ đó, bộ kết hợp điểm cố định của sách giáo khoa là bộ kết hợp Y thích hợp.