Chức năng Haskell đơn giản theo kiểu không điểm

Question

Tôi đang cố gắng hiểu cách chuyển đổi các hàm thành ký hiệu không có điểm trong Haskell. Tôi thấy this example, nhưng nó phức tạp hơn những gì tôi đang tìm kiếm. Tôi cảm thấy như tôi hiểu logic đằng sau nó, nhưng khi tôi đang cố gắng để thực hiện một số ví dụ đơn giản trong mã tôi nhận được lỗi biên dịch. Tôi muốn thử và viết chức năng này trong phong cách điểm miễn phí:

f x = 5 + 8/x mà tôi sắp xếp lại như f x = (+) 5 $ (/) 8 x

Vì vậy, tôi nghĩ rằng nó có thể là một cái gì đó như thế này:

f = (+) 5 $ (/) 8 

nhưng khi tôi chạy điều này trong ghci Tôi nhận được thông báo này:

No instance for (Num (a0 -> a0)) 
    arising from the literal `5' at Test.hs:3:9 
Possible fix: add an instance declaration for (Num (a0 -> a0)) 
In the first argument of `(+)', namely `5' 
In the first argument of `($)', namely `(+) 5' 
In the expression: (+) 5 $ (/) 8 
Failed, modules loaded: none. 

Tôi không hiểu thông báo "Không có trường hợp ...". Tôi cần phải làm gì để viết chức năng này theo kiểu không có điểm?

Answer 1

$ có mức ưu tiên rất thấp. Vì vậy, f x = (+) 5 $ (/) 8 x thực sự có nghĩa là f x = (+) 5 $ ((/) 8 x). Thay vào đó, hãy viết lại rằng dưới dạng

f x = (+) 5 ((/) 8 x) 
f x = ((+) 5) (((/) 8) x) 
f x = ((+) 5) . (((/) 8)) x 
f = ((+) 5) . ((/) 8) 
f = (5+) . (8/) 

Biểu thức cuối cùng có ý nghĩa: f là thành phần của hai hoạt động, trước tiên chia 8 thành cái, sau đó thêm 5 vào kết quả. Hãy nhớ rằng, g.h có nghĩa là "áp dụng h, sau đó áp dụng g kết quả của điều đó".

Answer 2

Chương trình "pointfree" có thể được cài đặt với cabal install pointfree và cho bạn biết cách viết biểu thức theo kiểu chấm điểm. Ví dụ:

$ pointfree "f x = 5 + 8/x" 
f = (5 +) . (8 /) 

Giải thích về chuyển đổi này:

1. Bạn có thể sử dụng "phần" cho các chức năng ghi vào/nhà điều hành. (a +) == \b -> a + b và (+ a) == \b -> b + a
2. Hàm . lấy kết quả của tham số thứ hai, là hàm một đối số và áp dụng nó cho đối số đầu tiên.

Answer 3

Bạn đã thực sự thân thiết. Cho phép tôi thêm một người nữa $ để minh họa:

f x = (+) 5 $ (/) 8 $ x 

Nó nên được rõ ràng rằng sự biểu hiện (+) 5 là một hàm mang theo một đầu vào số và tạo ra một đầu ra số. Cũng vậy với biểu thức (/) 8. Vì vậy, bạn lấy bất kỳ số nào là đầu vào, x và trước tiên áp dụng hàm "(/) 8" và sau đó áp dụng hàm "(+) 5".

Bất cứ khi nào bạn có một chuỗi các chức năng ngăn cách bởi $, bạn có thể thay thế tất cả ngoại trừ ngoài cùng bên phải với . Ý nghĩa, nếu bạn có a $ b $ c $ d, điều này tương đương với a . b . c $ d.

f x = (+) 5 . (/) 8 $ x 

Tại thời điểm này, chúng ta hãy thực sự loại bỏ các $ và nghĩ giải lao để thay thế.

f x = ((+) 5 . (/) 8) x 

Bây giờ nó phải rõ ràng mà bạn có thể loại bỏ các dấu x từ cả hai phía:

f = (+) 5 . (/) 8 

Đó là ý tưởng chính. Nếu bạn có f x = expr x, bạn có thể "eta reduce" nó thành f = expr. Để tạo mã pointfree, bạn chỉ cần nhận ra cách hàm lớn hơn bao gồm các hàm nhỏ hơn. Một phần ứng dụng đôi khi cần thiết cho mã điểm miễn phí (như trong trường hợp này, (+) 5 và (/) 8 được áp dụng một phần). Chương trình "pointfree" khá hữu ích khi bạn không muốn nghĩ về nó; Lambdabot trên kênh #haskell irc sử dụng chương trình này làm plugin, vì vậy bạn thậm chí không phải tự cài đặt nó; chỉ cần hỏi:

<DanBurton> @pl let f x = 5 + 8/x in f 
<lambdabot> (5 +) . (8 /) 

Answer 4

Chuyển đổi từ lambda-calculus (mà Haskell là một biến thể của) các điều khoản để trượt tuyết về (hoàn toàn chức năng pointfree, chỉ sử dụng const (K), id (tôi) và <*> (S)) có thể được thực hiện với các quy tắc đơn giản sau:

1. \x -> x dịch để id;
2. \x -> y mà không cần x xảy ra trong y dịch sang const y;
3. \x -> f g dịch để f' <*> g' nơi
   • f' là một bản dịch của \x -> f và
   • g' là một bản dịch của \x -> g.

Bây giờ bạn có thể tự hỏi nơi nào . đến trong Có một trường hợp đặc biệt của bản dịch cuối cùng:. Nếu f không có bất kỳ sự cố miễn x, sau đó \x -> f g dịch để const f <*> (\x -> g), tương đương đến f . (\x -> g).

Sử dụng những quy tắc chúng ta có thể chuyển đổi chức năng của bạn:

f = \x -> ((+) 5) (((/) 8) x) = -- by the special-case (.) rule 
((+) 5) . (\x -> (((/) 8) x)) = -- by eta-reduction ((\x -> f x) = f) 
((+) 5) . ((/) 8) 

Eta-giảm là không cần thiết để hoàn thành bản dịch, nhưng mà không có nó chúng ta sẽ có được một cái gì đó Messier. Ví dụ: bước cuối cùng sẽ mang lại ((+) 5) . ((/) 8) . id thay thế.