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，或通过文字编辑器的插头哈斯克尔在。