Haskell中的點自由問題

Question

我試圖將下面的haskell代碼轉換爲點自由樣式，但無濟於事。

bar f g xs = filter f (map g xs) 

我是新來的Haskell和任何幫助將是巨大的

Answer 1

轉換爲無點風格可以完全機械地完成，雖然很難理解Haskell語法的基本原理，如左關聯函數應用，x + y與(+) x y相同。我會假設你對Haskell語法很熟悉;如果沒有，我建議先閱讀LYAH的前幾章。

您需要以下組合器，它們位於標準庫中。我也從combinator演算中給出他們的標準名稱。

id :: a -> a         -- I 
const :: a -> b -> a       -- K 
(.) :: (b -> c) -> (a -> b) -> (a -> c)  -- B 
flip :: (a -> b -> c) -> (b -> a -> c)   -- C 
(<*>) :: (a -> b -> c) -> (a -> b) -> (a -> c) -- S 

一次處理一個參數。將左側的參數移動到右側的lambdas，例如

f x y = Z 

成爲

f = \x -> \y -> Z 

我喜歡在一個時間，而不是所有做這一個參數一次，它只是看起來更清潔。

然後根據以下規則消除剛創建的lambda。我將用小寫字母表示文字變量，用大寫字母表示更復雜的表達式。

1. 如果你有\x -> x，更換id
2. 如果你有\x -> A，其中A是在x不會發生，與const A
3. 取代如果你有\x -> A x，其中x不會發生任何表情在A中，替換爲A。這被稱爲「eta收縮」。
4. 如果你有\x -> A B，然後
   1. 如果x同時出現在A和B，更換(\x -> A) <*> (\x -> B)。
   2. 如果發生在短短Ax，與flip (\x -> A) B
   3. 更換如果發生在短短Bx，更換A . (\x -> B)，
   4. 如果x沒有在任何A或B發生，那麼，還有我們應該用另一個規則已經。

然後向內進行，省去您創建的lambda表達式。讓我們來看看這個例子：

f x y z = foo z (bar x y) 
-- Move parameter to lambda: 
f x y = \z -> foo z (bar x y) 
-- Remember that application is left-associative, so this is the same as 
f x y = \z -> (foo z) (bar x y) 
-- z appears on the left and not on the right, use flip 
f x y = flip (\z -> foo z) (bar x y) 
-- Use rule (3) 
f x y = flip foo (bar x y) 

-- Next parameter 
f x = \y -> flip foo (bar x y) 
-- Application is left-associative 
f x = \y -> (flip foo) (bar x y) 
-- y occurs on the right but not the left, use (.) 
f x = flip foo . (\y -> bar x y) 
-- Use rule 3 
f x = flip foo . bar x 

-- Next parameter 
f = \x -> flip foo . bar x 
-- We need to rewrite this operator into normal application style 
f = \x -> (.) (flip foo) (bar x) 
-- Application is left-associative 
f = \x -> ((.) (flip foo)) (bar x) 
-- x appears on the right but not the left, use (.) 
f = ((.) (flip foo)) . (\x -> bar x) 
-- use rule (3) 
f = ((.) (flip foo)) . bar 
-- Redundant parentheses 
f = (.) (flip foo) . bar 

現在就去嘗試一下吧！決定使用哪種規則並沒有真正的巧妙：使用適用的任何規則，並且您將取得進展。

Answer 2

我問lambdabot，誰各種Haskell的IRC頻道掛出一個機器人，自動計算出自由點等價的。該命令是@pl（毫無意義的）。的bar

10:41 <frase> @pl bar f g xs = filter f (map g xs) 
10:41 <lambdabot> bar = (. map) . (.) . filter 

點免費版是：

bar = (. map) . (.) . filter 

這比原始（非點免費）碼可以說少理解。在決定是否逐個使用無點式時，請使用您的判斷力。

最後，如果你不喜歡IRC也有基於Web的免費點 轉換器，例如Blunt（由@TaylorFausak），該pointfree命令行程序，和其他工具。

Answer 3

這兩個現有的答案都沒有真正以一種闡明的方式回答你的具體問題：一個是「這裏是規則，爲你自己工作」，另一個是「這裏是答案，沒有任何信息規則如何產生它。「

前三個步驟非常簡單，包括通過編寫h = f . g從h x = f (g x)的格式中刪除共同的x。本質上，它在說：「如果你可以寫在表格a $ b $ c $ ... $ y $ z的事情，你要刪除的z，改變所有的美元，以點，a . b . c . ... . y：

bar f g xs = filter f (map g xs) 
      = filter f $ (map g xs) 
      = filter f $ map g $ xs -- because a $ b $ c == a $ (b $ c). 
bar f g = filter f . map g 
      = (filter f .) (map g) 
      = (filter f .) $ map $ g 
bar f  = (filter f .) . map 

所以這最後f是唯一棘手的部分，它的。棘手的，因爲f是不是在表達的「終點」，但看着它，我們看到，這是適用於表達式的其餘部分的功能部(. map)：

bar f = (.) (filter f) . map 
bar f = (. map) $ (.) $ filter $ f 
bar = (. map) . (.) . filter 

，這就是你如何減小表達，當你沒有複雜的事情l其中出現ike f x x等。通常有一個功能flip f x y = f y x它「翻轉參數」;你總是可以使用它將f移動到另一邊。如果您包含顯式翻轉呼叫，則我們有flip (.) map . (.) . filter。