什么(f.).在Haskell中意味着什么？

Question

我已经看到很多函数是根据模式定义的(f .) . g.例如:

countWhere = (length .) . filter
duplicate  = (concat .) . replicate
concatMap  = (concat .) . map

这是什么意思？

Answer 1

点运算符(即(.))是函数组合运算符.它的定义如下:

infixr 9 .
(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)

正如您所看到的,它需要类型函数和类型的b -> c另一个函数,a -> b并返回一个类型的函数a -> c(即将第二个函数的结果应用于第一个函数).

函数组合运算符非常有用.它允许您将一个函数的输出传递给另一个函数的输入.例如,你可以在Haskell中编写一个tac程序,如下所示:

main = interact (\x -> unlines (reverse (lines x)))

不太可读.但是使用函数组合,您可以按如下方式编写它:

main = interact (unlines . reverse . lines)

正如您所看到的,功能组合非常有用,但您无法在任何地方使用它.例如,您无法将输出传递filter给length使用函数组合:

countWhere = length . filter -- this is not allowed

这是不允许的原因是因为filter类型(a -> Bool) -> [a] -> [a].与它相比a -> b我们发现它a是类型(a -> Bool)和b类型[a] -> [a].这导致类型不匹配,因为Haskell期望length是类型b -> c(即([a] -> [a]) -> c).然而它实际上是类型[a] -> Int.

解决方案非常简单:

countWhere f = length . filter f

然而,有些人不喜欢那种额外的悬空f.他们喜欢写countWhere在pointfree风格如下:

countWhere = (length .) . filter

他们怎么得到这个？考虑:

countWhere f xs = length (filter f xs)

-- But `f x y` is `(f x) y`. Hence:

countWhere f xs = length ((filter f) xs)

-- But `\x -> f (g x)` is `f . g`. Hence:

countWhere f = length . (filter f)

-- But `f . g` is `(f .) g`. Hence:

countWhere f = (length .) (filter f)

-- But `\x -> f (g x)` is `f . g`. Hence:

countWhere = (length .) . filter

你可以看到(f .) . g很简单\x y -> f (g x y).这个概念实际上可以迭代:

f . g             --> \x -> f (g x)
(f .) . g         --> \x y -> f (g x y)
((f .) .) . g     --> \x y z -> f (g x y z)
(((f .) .) .) . g --> \w x y z -> f (g w x y z)

它不漂亮,但它完成了工作.给定两个函数,您还可以编写自己的函数组合运算符:

f .: g = (f .) . g
f .:: g = ((f .) .) . g
f .::: g = (((f .) .) .) . g

使用(.:)运算符,您可以编写countWhere如下代码:

countWhere = length .: filter

有趣的是,虽然你也可以写(.:)点自由风格:

f .: g = (f .) . g

-- But `f . g` is `(.) f g`. Hence:

f .: g = (.) (f .) g

-- But `\x -> f x` is `f`. Hence:

(f .:) = (.) (f .)

-- But `(f .)` is `((.) f)`. Hence:

(f .:) = (.) ((.) f)

-- But `\x -> f (g x)` is `f . g`. Hence:

(.:) = (.) . (.)

同样我们得到:

(.::)  = (.) . (.) . (.)
(.:::) = (.) . (.) . (.) . (.)

正如你所看到的(.:),(.::)并且(.:::)仅仅是权力(.)(即它们迭代函数的(.)).对于数学中的数字:

x ^ 0 = 1
x ^ n = x * x ^ (n - 1)

类似于数学中的函数:

f .^ 0 = id
f .^ n = f . (f .^ (n - 1))

如果f是的(.)话:

(.) .^ 1 = (.)
(.) .^ 2 = (.:)
(.) .^ 3 = (.::)
(.) .^ 4 = (.:::)

这使我们接近本文的结尾.对于最后的挑战,让我们以无点样式编写以下函数:

mf a b c = filter a (map b c)

mf a b c = filter a ((map b) c)

mf a b = filter a . (map b)

mf a b = (filter a .) (map b)

mf a = (filter a .) . map

mf a = (. map) (filter a .)

mf a = (. map) ((filter a) .)

mf a = (. map) ((.) (filter a))

mf a = ((. map) . (.)) (filter a)

mf = ((. map) . (.)) . filter

mf = (. map) . (.) . filter

我们可以进一步简化如下:

compose f g = (. f) . (.) . g

compose f g = ((. f) . (.)) . g

compose f g = (.) ((. f) . (.)) g

compose f = (.) ((. f) . (.))

compose f = (.) ((. (.)) (. f))

compose f = ((.) . (. (.))) (. f)

compose f = ((.) . (. (.))) (flip (.) f)

compose f = ((.) . (. (.))) ((flip (.)) f)

compose = ((.) . (. (.))) . (flip (.))

使用compose你现在可以写mf为:

mf = compose map filter

是的它有点难看,但它也是一个令人难以置信的令人难以置信的概念.现在,您可以编写形式的任何功能\x y z -> f x (g y z)的compose f g,这是非常整齐.

Answer 2

这是一个品味问题,但我发现这种风格令人不愉快.首先,我将描述它的意义,然后我建议我更喜欢的替代方案.

你需要知道这一点(f . g) x = f (g x)以及(f ?) x = f ? x任何运营商?.由此我们可以推断出这一点

countWhere p = ((length .) . filter) p
              = (length .) (filter p)
              = length . filter p

所以

countWhere p xs = length (filter p xs)

我更喜欢使用一个名为的函数 .:

(.:) :: (r -> z) -> (a -> b -> r) -> a -> b -> z
(f .: g) x y = f (g x y)

然后countWhere = length .: filter.就个人而言,我发现这一点更加清晰.

(.:也在Data.Composition其他地方定义.)