Quy tắc viết lại Haskell và thành phần chức năng

Question

Tại sao haskell yêu cầu nhiều quy tắc viết lại tùy thuộc vào kỹ thuật và chiều dài thành phần chức năng? Có cách nào để tránh điều này không?

Ví dụ, với đoạn mã sau ...

{-# RULES 
"f/f" forall a. f (f a) = 4*a 
    #-} 
f a = 2 * a 

này làm việc cho

test1 = f (f 1) 

tuy nhiên chúng ta cần thêm một quy tắc cho

test2 = f . f $ 1 

và

test3 = f $ f 1 

lại cho chúng tôi với các quy tắc sau

{-# RULES 
"f/f1" forall a. f (f a) = 4 * a 
"f/f2" forall a. f . f $ a = 4 * a 
"f/f3" forall a. f $ f $ a = 4 * a 
    #-} 

Tuy nhiên, khi chúng tôi chuỗi này lại với nhau hoặc sử dụng một số hình thức khác của thành phần các quy tắc không bắn.

test4 = f . f . f $ 1 
test5 = f $ f $ f $ 1 
test6 = f $ 1 

Tại sao điều này? Tôi có phải viết các quy tắc viết lại cho mọi triển khai có thể không?

Answer 1

Nguyên tắc không cháy, trong nhiều trường hợp bởi vì chức năng rất đơn giản f được inlined trước sự cai trị đã có một cơ hội để bắn. Nếu bạn trì hoãn việc nội tuyến,

{-# INLINE [1] f #-} 

sự cai trị

{-# RULES "f/f" forall a. f (f a) = 4*a #-} 

nên bắn cho tất cả những trường hợp này (làm việc ở đây với 7.2.2 và 7.4.1).

Lý do là trình kết hợp quy tắc không quá phức tạp, nó chỉ khớp các biểu thức có dạng cú pháp của quy tắc (không hoàn toàn đúng, thân quy tắc cũng trải qua một số chuẩn hóa). Biểu thức f $ f 3 hoặc f . f $ 4 không khớp với dạng cú pháp của quy tắc. Để quy tắc khớp, một số viết lại phải diễn ra, ($) và (.) phải được đặt trước khi quy tắc khớp với biểu thức. Nhưng nếu bạn không ngăn không cho f được inline trong giai đoạn đầu của bộ khuếch đại, nó sẽ được thay thế bởi cơ thể của nó trong cùng một hoạt động như ($) và (.) được gạch chân, vì vậy trong lần lặp tiếp theo, bộ khuếch đại không nhìn thấy f nữa, nó chỉ thấy 2*(2*x), không khớp với quy tắc.

Answer 2

Tôi đã có thể nghĩ rằng điều này sẽ làm việc theo mặc định, nhưng bạn có thể thêm hai quy tắc viết lại nhiều hơn để làm cho ./$ giảm xuống lambdas/ứng dụng, do đó điều này sẽ luôn luôn phù hợp:

{-# RULES 
"f/f" forall a. f (f a) = 4*a 

"app" forall f x. f $ x = f x 
"comp" forall f g. f . g = (\x -> f (g x)) 
    #-} 

f a = 3 * a -- make this 3*a so can see the difference 

Một thử nghiệm :

main = do 
    print (f . f $ 1) 
    print (f (f 1)) 
    print (f $ f 1) 
    print (f $ f $ 1) 
    print (f $ f $ f $ f $ 1) 
    print (f . f . f . f $ 1) 
    print (f $ f $ f $ 1) 
    print (f . f . f $ 1) 
    print (f $ 1) 

Output:

4 
4 
4 
4 
16 
16 
12 
12 
3 

này cũng sẽ làm việc trong một số (nhưng không phải tất cả) mơ hồ hơn c ases, do các quy tắc viết lại khác. Ví dụ, tất cả trong số này sẽ làm việc:

mapf x = map f $ map f $ [x] 
mapf' x = map (f.f) $ [x] 
mapf'' x = map (\x -> f (f x)) $ [x]