Haskell多功能組合

Question

我試圖瞭解Haskell中的函數組合。

根據ZVON http://zvon.org/other/haskell/Outputprelude/filter_f.html
過濾器函數應該有兩個參數，一個bool函數和一個列表。

例filter (>5) [1,2,3,4,5,6,7,8]返回任何大於5： [6,7,8]

問題，如何以下行具有若干功能的組合物在一個布爾通爲濾波器利用？

map fst . filter snd . assocs . soeA

它不應該是地圖FST。過濾器（== True）snd。聯合。 soeA

爲了分析我運行該組合物的前兩個功能，並通過一個參數：assocs . soeA $ 9返回 [(0,False),(1,False),(2,True),(3,True),(4,False),(5,True),(6,False),(7,True),(8,False),(9,False)]

soe 9返回[2,3,5,7]

不知何故被用來在soeA的每個陣列元素的布爾值，但任何幫助解釋這種組合如何工作將非常感激。

的完整代碼： `

module FastSeive where 

import Control.Monad 
import Control.Monad.ST 
import Data.Array.ST 
import Data.Array.Unboxed 



soeST :: forall s. Int -> ST s (STUArray s Int Bool) 
soeST n = do 
    arr <- newArray (0, n) True 
    mapM_ (\i -> writeArray arr i False) [0, 1] 
    let n2 = n `div` 2 

    let loop :: Int -> ST s() 
     loop i | i > n2 = return() 
     loop i = do 
      b <- readArray arr i 

      let reset :: Int -> ST s() 
       reset j | j > n = return() 
       reset j = writeArray arr j False >> reset (j + i) 

      when b (reset (2*i)) 

      loop (succ i) 

    loop 2 
    return arr 


soeA :: Int -> UArray Int Bool 
soeA n = runST (soeST n >>= freeze) 


soe :: Int -> [Int] 
soe = map fst . filter snd . assocs . soeA 


soeCount :: Int -> Int 
soeCount = length . filter id . elems . soeA 

`

Answer 1

簡短的回答是：在這裏，snd是Bool -returning功能filter預期。在你寫的表達中：map fst . filter (==True) snd . assocs . soeA。 snd將是filter的第二個參數，而(==True)將是第一個參數。當然，它不會檢查，因爲filter已經應用於兩個參數，並且不能在函數組合中使用：它不再是一個函數。

---

對於較長的答案，我們可以實際應用(.)的定義，找出發生了什麼：

(f . g) x = f (g x) 
-- In haskell, it is defined as being right associative 

-- Meaning that if we put explicit parenthesises, we'd have: 
soe = (map fst . (filter snd . (assocs . soeA))) 
-- That only really matters for the compiler, though, 
-- because we know function composition is associative. 

soe = map fst . filter snd . assocs . soeA 
-- "Un-pointfree-ing" it: 
soe x = (map fst . filter snd . assocs . soeA) x 
-- Applying (.)'s definition: 
soe x = map fst ((filter snd . assocs . soeA) x) 
-- Again: 
soe x = map fst (filter snd ((assocs . soeA) x)) 
-- And again: 
soe x = map fst (filter snd (asocs (soeA x))) 

現在很清楚的是snd是filter的第一個參數，而第二個參數將評估什麼assocs (soeA x)將評估。

更一般地，當一個寫f . g . h，這可以被讀從右到左爲第一適用h到它的參數，然後g該結果，然後f到下一個結果的函數，併產生該最終值。

---

現在，對於更長的答案，我們可以看看如何推斷表達式的類型。它會告訴我們爲什麼snd是Bool -returning函數filter預計即使它有一個snd :: (a, b) -> b類型簽名。

聲明：我沒有編譯器工程的背景;我將要使用的術語可能不準確。

filter的類型是(a -> Bool) -> [a] -> [a]。 snd的類型是(a, b) -> b。

這些實際上是參數化類型。我們可以讓類型參數明確：

filter :: forall a. (a -> Bool) -> [a] -> [a] 
snd :: forall a b. (a, b) -> b 

我們也將重新命名filter的類型參數，以使其成爲非曖昧我們接下來會寫：

filter :: forall c. (c -> Bool) -> [c] -> [c] 

filter得到首先應用於snd。所以，我們可以嘗試和統一c -> Bool從filter與(a, b) -> b，snd的類型。我們得到以下公式：

c -> Bool = (a, b) -> b 

=== 

c = (a, b) 
b = Bool 

=== 

c = (a, Bool) 
b = Bool 

我們假設assocs (soeA x)的類型是[(Int, Bool)]。由於filter的第二個參數的類型爲[c]，我們可以進一步統一：

[c] = [(Int, Bool)] 

=== 

c = (Int, Bool) 

這也給了我們：

(Int, Bool) = c = (a, Bool) 

=== 

a = Int 

於是，經過類型的應用，我們得到這些具體類型爲我們的子表情：

filter :: ((Int, Bool) -> Bool) -> [(Int, Bool)] -> [(Int, Bool)] 
snd :: (Int, Bool) -> Bool 

嘛，當然，我們可以一直使用GHC的類型推斷告訴我們的是，無論是使用GHCI，或通過文字編輯器的插頭哈斯克爾在。