Sơ đồ tổng quát để viết một hàm theo kiểu pointfree là gì?

Question

Tôi đang làm việc qua 20 Intermediate Haskell Exercises vào lúc này, đây là một bài tập khá thú vị. Nó liên quan đến việc thực hiện các trường hợp khác nhau của typeclasses Functor và Monad (và các chức năng mất Functor s và Monad s làm đối số) nhưng với các tên dễ thương như Furry và Misty để che giấu những gì chúng tôi đang làm (làm cho một số mã thú vị).

Tôi đã cố gắng thực hiện một số điều này theo kiểu không có điểm, và tôi tự hỏi liệu có một phương án chung để chuyển định nghĩa point-ful (?) Thành định nghĩa không điểm. Ví dụ, đây là typeclass cho Misty:

class Misty m where 
    unicorn :: a -> m a 
    banana :: (a -> m b) -> m a -> m b 

(các chức năng unicorn và banana là return và >>=, trong trường hợp nó không rõ ràng) và đây là thực hiện của tôi apple (tương đương với flip ap):

apple :: (Misty m) => m a -> m (a -> b) -> m b 
apple x f = banana (\g -> banana (unicorn . g) x) f 

Các phần sau của bài tập có bạn thực hiện các phiên bản liftM, liftM2 vv. Dưới đây là các giải pháp của tôi:

appleTurnover :: (Misty m) => m (a -> b) -> m a -> m b 
appleTurnover = flip apple 

banana1 :: (Misty m) => (a -> b) -> m a -> m b 
banana1 = appleTurnover . unicorn 

banana2 :: (Misty m) => (a -> b -> c) -> m a -> m b -> m c 
banana2 f = appleTurnover . banana1 f 

banana3 :: (Misty m) => (a -> b -> c -> d) -> m a -> m b -> m c -> m d 
banana3 f x = appleTurnover . banana2 f x 

banana4 :: (Misty m) => (a -> b -> c -> d -> e) -> m a -> m b -> m c -> m d -> m e 
banana4 f x y = appleTurnover . banana3 f x y 

Bây giờ, banana1 (tương đương liftM hoặc fmap) Tôi đã có thể triển khai theo kiểu không có điểm, theo định nghĩa phù hợp là appleTurnover. Nhưng với ba hàm khác tôi đã phải sử dụng các tham số.

Câu hỏi của tôi là: có công thức để chuyển định nghĩa như thế này thành các định nghĩa không điểm?

Answer 1

Như được minh họa bởi tiện ích pointfree, bạn có thể tự động thực hiện bất kỳ chuyển đổi nào như vậy. Tuy nhiên, kết quả thường bị làm xáo trộn hơn cải thiện. Nếu mục tiêu của một người là tăng cường tính dễ đọc hơn là phá hủy nó, thì mục tiêu đầu tiên phải là xác định lý do tại sao một biểu thức có cấu trúc cụ thể, tìm cách trừu tượng phù hợp và xây dựng mọi thứ theo cách đó.

Cấu trúc đơn giản nhất chỉ đơn giản là ghép các thứ lại với nhau trong một đường ống tuyến tính, đó là thành phần chức năng đơn giản. Điều này khiến chúng tôi khá xa chỉ riêng của mình, nhưng khi bạn nhận thấy nó không xử lý tất cả mọi thứ.

Một khái quát hóa là hoạt động với các đối số bổ sung, có thể được xây dựng theo từng bước. Dưới đây là một ví dụ: Xác định onResult = (. (.)).Bây giờ, áp dụng onResult n lần cho giá trị ban đầu là id cho bạn thành phần chức năng với kết quả của hàm n-ary. Vì vậy, chúng tôi có thể xác định comp2 = onResult (.), và sau đó viết comp2 not (&&) để xác định một hoạt động NAND.

Một khái quát khác - bao gồm các điều trên, thực sự - là xác định toán tử áp dụng hàm cho thành phần có giá trị lớn hơn. Ví dụ ở đây sẽ là first và second trong Control.Arrow, hoạt động trên 2 bộ. Conal Elliott's Semantic Editor Combinators được dựa trên phương pháp này.

Trường hợp khác một chút là khi bạn có chức năng đa đối số trên một số loại b và hàm a -> b và cần kết hợp chúng thành hàm đa đối số sử dụng a. Đối với trường hợp chung của hàm 2-ary, mô-đun Data.Function cung cấp bộ phối hợp on, mà bạn có thể sử dụng để viết các biểu thức như compare `on` fst để so sánh 2 bộ trên các phần tử đầu tiên của chúng.

Vấn đề phức tạp hơn khi một đối số được sử dụng nhiều lần, nhưng có các mẫu định kỳ có ý nghĩa ở đây cũng có thể được trích xuất. Một trường hợp phổ biến ở đây là áp dụng nhiều hàm cho một đối số, sau đó thu thập các kết quả bằng một hàm khác. Điều này xảy ra tương ứng với cá thể Applicative cho các hàm, cho phép chúng ta viết các biểu thức như (&&) <$> (> 3) <*> (< 9) để kiểm tra xem một số có thuộc một phạm vi nhất định hay không.

Điều quan trọng, nếu bạn muốn sử dụng bất kỳ điều này trong mã thực tế, là suy nghĩ về biểu thức có nghĩa là và cách phản ánh trong cấu trúc. Nếu bạn làm điều đó, và sau đó tái cấu trúc nó thành kiểu vô hướng bằng cách sử dụng các bộ phối hợp có ý nghĩa, bạn thường sẽ tạo mục đích của mã rõ ràng hơn nếu không, không giống như đầu ra điển hình của pointfree.

Answer 2

Có! Một trong những thủ thuật là viết các dấu chấm của bạn trong ký hiệu tiền tố thay vì nhập vào. Sau đó, bạn sẽ có thể tìm thấy những thứ mới trông giống như thành phần chức năng. Dưới đây là ví dụ:

banana2 f = appleTurnover . banana1 f 
      = (.) appleTurnover (banana1 f) 
      = ((.) appleTurnOver) . banana1 $ f 
banana2 = (appleTurnover .) . banana1 

Mã nguồn cho tiện ích pointfree chứa nhiều hơn, nhưng điều này xử lý nhiều trường hợp.

banana4 f x y = appleTurnover . banana3 f x y 
       = (.) appleTurnover ((banana3 f x) y) 
       = ((.) appleTurnover) . (banana3 f x) $ y 
banana4 f x = ((.) appleTurnover) . (banana3 f x) 
      = (.) ((.) appleTurnover) (banana3 f x) 
      = ((.) ((.) appleTurnover)) ((banana3 f) x) 
      = ((.) ((.) appleTurnover)) . (banana3 f) $ x 
banana4 f = ((.) ((.) appleTurnover)) . (banana3 f) 
      = (.) ((.) ((.) appleTurnover)) (banana3 f) 
      = ((.) ((.) ((.) appleTurnover))) (banana3 f) 
      = ((.) ((.) ((.) appleTurnover))) . banana3 $ f 
banana4 = ((.) ((.) ((.) appleTurnover))) . banana3 
     = (((appleTurnover .) .) .) . banana3 

Answer 3

Có một gói pointfree mà phải mất một định nghĩa hàm Haskell và cố gắng viết lại nó trong một phong cách pointfree. Tôi muốn đề nghị thử nghiệm với nó để có được những ý tưởng mới. Xem this page để biết thêm chi tiết; gói có sẵn here.

Answer 4

tôi sử dụng hệ thống viết lại hạn sau đây:

\x -> f x ------> f 
f y x ----------> flip f x y 
\x -> f (g x) --> f . g 

Đó là chưa đầy đủ (đọc tại sao trong cuốn sách về logic combinatory), nhưng nó đủ:

Đây là banana2:

banana2 f = appleTurnover . banana1 f 

Viết lại dưới dạng lambda:

banana2 = \f -> appleTurnover . banana1 f 

Viết theo kiểu tiền tố (.):

banana2 = \f -> (.) appleTurnover (banana1 f) 

Lưu ý rằng

banana2 = \f -> ((.) appleTurnover) (banana1 f) 

Vì vậy, quy tắc 3 có thể được áp dụng.f là (.) appleTurnover và g là banana:

banana2 = ((.) appleTurnover) . banana1 

Answer 5

Kể từ khi phong cách pointfree là combinators phong cách, chỉ cần áp dụng định nghĩa combinators biết, đọc chúng ngược trở lại để thực hiện việc thay thế:

B f g x = f (g x)  -- (.) , <$> for ((->) a) 
C f x y = f y x  -- flip 
K x y = x    -- const 
I x = x    -- id 
S f g x = f x (g x) -- <*> , ap for ((->) a) 
W f x = f x x   -- join 
(f >>= g) x = g (f x) x 
(f =<< g) x = f (g x) x 

lúc liftMx, liftAx, sequence , sequenceA có thể đơn giản hóa mọi thứ. Tôi cũng xem xét foldr, unfoldr, iterate, until, v.v ... như bộ kết hợp cơ bản.

Thông thường, sử dụng các phần tử giúp quá:

op a b = (a `op` b) = (`op` b) a = (a `op`) b 

Một số mô hình có thể trở nên quen thuộc và vì vậy, sử dụng trực tiếp:

((f .) . g) x y = f (g x y) 
((. f) . g) x y = g x (f y) 

(((f .) .) . g) x y z = (f .) (g x y) z = f (g x y z) 
(((. f) .) . g) x y z = (. f) (g x y) z = g x y (f z) 

, vv