應用性重寫（Haskell）

當我不掌握Haskell中的表達式如何工作時，我經常發現它有助於將它分解爲更基本的形式。應用性重寫（Haskell）

使用下列定義

sequenceA :: (Applicative f) => [f a] -> f [a] 
sequenceA [] = pure [] 
sequenceA (x:xs) = (:) <$> x <*> sequenceA xs 

instance Applicative ((->) r) where 
    pure x = (\_ -> x) 
    f <*> g = \x -> f x (g x)

我改寫sequenceA [(+3),(+2)] 3作爲

(\_ -> (:)) <*> (+3) <*> ((\_ -> (:)) <*> (+2) <*> (\_-> [])) $ 3

然後把它變成（請原諒的格式，我不知道該約定是什麼分割線）

(\d ->(\c->(\b -> (\a -> (\_ -> (:)) a (+3) a) b (\_ -> (:)) b) c (+2) c) d (\_ -> []) d) 3

這似乎是正確的，但我無法讓GHCi接受它。我在這裏做錯了什麼？我的第二個問題是如何從這種形式轉換爲功能組合。我已經試過各種組合substituing點，但GHCI拒絕所有的人....

來源

2012-08-10 planarian

作爲一個懶散的好人，我以爲我會讓電腦爲我做擴展。所以到ghci中，我輸入

let pu x = "(\\_ -> " ++ x ++ ")" 
let f >*< a = "(\\g -> " ++ f ++ " g (" ++ a ++ " g))"

所以現在我有pure和<*>搞笑版本哪個地圖的字符串看起來像表達式字符串，它看起來像更復雜的表達式。然後，我同樣定義了sequenceA的模擬，用字符串替換函數。

let sqa [] = pu "[]" ; sqa (f : fs) = (pu "(:)" >*< f) >*< sqa fs

我然後能夠生成的示例的擴展形式如下

putStrLn $ sqa ["(+3)","(+2)"] ++ " 3"

其正式印製

(\g -> (\g -> (\_ -> (:)) g ((+3) g)) g ((\g -> (\g -> (\_ -> (:)) g ((+2) g)) g ((\_ -> []) g)) g)) 3

這最後，複製到提示，得到

[6,5]

Co彙總我的「元程序」的輸出結果，問題中的嘗試顯示較短的初始lambda表達式前綴，由較淺的嵌套操作產生。記住，這是

(pure (:) <*> (+3)) <*> ((pure (:) <*> (+2)) <*> pure [])

所以外(:)應該只有三個lambda表達式深。我懷疑所提出的擴大可對應於上述的不同括號的版本，也許

pure (:) <*> (+3) <*> pure (:) <*> (+2) <*> pure []

事實上，當我評價

putStrLn $ pu "(:)" >*< "(+3)" >*< pu "(:)" >*< "(+2)" >*< pu "[]" ++ " 3 "

我得到

(\g -> (\g -> (\g -> (\g -> (\_ -> (:)) g ((+3) g)) g ((\_ -> (:)) g)) g ((+2) g)) g ((\_ -> []) g)) 3

它看起來像它匹配（更新後）

(\d -> (\c -> (\b -> (\a -> (\_ -> (:)) a ((+3) a)) b ((\_ -> (:)) b)) c ((+2) c)) d ((\_ -> []) d)) 3

我希望這個機器輔助調查有助於澄清發生了什麼。

來源

2012-08-10 18:05:01 pigworker

您的方法論已經過去了，但這絕對是我第一個問題的答案。有關第二個的任何想法？（翻譯成（。）符號） – planarian 2012-08-10 18:59:56

我的方法是通過生成相關表達式作爲字符串來機械化「寫出擴展」的過程。在「純」計算常量函數的地方，「pu」計算常量函數的*文本*。與此同時，我對翻譯的主要思考是不斷地發揮作用，因爲這樣做不會特別有啓發性。讓我們通過組合來表達'<*>'，並且...因爲第三個（*環境*）參數被複制，所以這是一個麻煩。我們需要一個複印機，例如'加入f a = f a a'，然後'（<*>）=（join。）。（（。）。翻轉）'這不是很亮。 – pigworker 2012-08-10 19:27:08

如果你認爲我自己想到了這一點，我最好指出一下關於組合邏輯的方便頁面：http：//en.wikipedia.org/wiki/B,C,K,W_System'Applicative'實例對於'（（ - >）a）'作爲K combinator，''純''作爲S combinator'<*>'。將應用式表達式轉換成合成量可將SK-組合器術語轉換爲BCKW-組合術語，這是可行的（兩個系統都是完整的）但又髒兮兮的。 – pigworker 2012-08-10 19:31:22

你改寫(\_ -> (:)) <*> (+3)爲\a -> (\_ -> (:)) a (+3) a，這是改寫f <*> g爲f x g x而不是f x (g x)。我認爲你犯了每個<*>的錯誤。

來源

2012-08-10 17:25:57

你是對的，但添加圓括號不能解決它。這是更新：（\ d - >（\ c - >（\ b - >（\ a - >（\ _ - >（:)）a（（+3）a））b（（\ >（:)）b））c（（+2）c））d（（\ _ - > []）d））3 – planarian 2012-08-10 17:49:51

使用組合器可能更容易，例如， _S和_K，象徵性的，而不是其定義爲lambda表達式，

_S f g x = f x (g x) 
_K x y = x

隨着功能，fmap是(.)和<*>是_S，正如其他人已經提到。所以，

sequenceA [(+3),(+2)] 3 == 
    (((:) <$> (+3)) <*> sequenceA [(+2)]  ) 3 == 
    _S ((:).(+3)) (((:) <$> (+2)) <*> pure []) 3 == 
    _S ((:).(+3)) (_S ((:).(+2)) (_K []) ) 3 == 
     ((:).(+3)) 3 (_S ((:).(+2)) (_K []) 3) == 
     ((:).(+3)) 3 ( ((:).(+2)) 3 (_K [] 3) ) == 
    (6:) ((5:) []) == 
    [6,5]

因此，它可能會更容易分解表達式下降到基本功能和組合程序，並停在那裏（即不分解他們他們的lambda表達式），利用其「重寫規則」操縱表達式找到其更易於理解的形式。

如果你想，你現在就可以寫下自己更抽象的，非正式的重寫規則sequenceA作爲

sequenceA [f,g,..., z] == 
    _S ((:).f) . _S ((:).g) . _S ..... . _S ((:).z) . _K []

等

sequenceA [f,g,..., z] a == 
    ((:).f) a $ ((:).g) a $ ..... $ ((:).z) a $ _K [] a == 
    (f a:) $ (g a:) $ ..... $ (z a:) $ []  == 
    [f a, g a, ..., z a]

，因此

sequenceA fs a == map ($ a) fs == flip (map . flip ($)) fs a

to wit，

Prelude Control.Applicative> flip (map . flip ($)) [(+3),(+2)] 3 
[6,5]

來源

2012-08-11 19:51:31

應用性重寫（Haskell）

回答

相關問題