Haskell 函数组合与 Map 函数

Question

我正在阅读 Richard Bird 的“使用 Haskell 进行函数式思考”一书，其中有一部分我无法理解他在哪里证明了过滤器方法的属性。他证明的是:

filter p . map f = map f . filter (p . f)

之前在书中，他将过滤器定义为:

filter p = concat . map (test p)
test p x = if p x then [x] else []

这就是他证明第一个等式的方法:

    filter p . map f
= {second definition of filter} -- He's referring to the definition I gave above
    concat . map (test p) . map f
= {functor property of map}
    concat . map (test p . f)
= {since test p . f = map f . test (p . f)}
    concat . map (map f . test (p . f))
= {functor property of map}
    concat . map (map f) . map (test (p . f))
= {naturality of concat}
    map f . concat . map (test (p . f))
= {second definition of filter}
    map f . filter (p . f)

我无法理解的是 test p . f等于 map f . test (p . f) .

这就是我尝试测试它的方式:

test :: (a -> Bool) -> a -> [a]
test p x = if p x then [x] else []

test ((<15) . (3*)) 4 -- test p .f, returns [4]
(map (3*) . test((<15) . (3*))) 4 -- map f . test (p . f), returns [12]

谁能解释一下我在这里缺少什么？

Answer 1

你测试了

test (p . f) = map f . test (p . f)

这确实是错误的。该属性(property)实际上是

test p . f = map f . test (p . f)

LHS 关联的地方

test p . f = (test p) . f

请记住，函数应用程序比任何用户可定义的运算符绑定(bind)得更紧密，就像 infixl 10 一样。 .两个相邻的标识符始终是前缀函数应用程序的一部分。 (除了 as-patterns: f xs@ys zs 表示 f (xs@ys) zs。)

证明性质:

    test p . f
={definition of (.)}
    \x -> test p (f x)
={definition of test}
    \x -> if p (f x) then [f x] else []
={definition of map, multiple times}
    \x -> if p (f x) then map f [x] else map f []
={float map f out of cases}
    \x -> map f (if p (f x) then [x] else [])
={definition of (.)}
    \x -> map f (if (p . f) x then [x] else [])
={definition of test}
    \x -> map f (test (p . f) x)
={definition of (.)}
    map f . test (p . f)

调整您的示例， test (<15) . (*3)意思是“乘以 3 ，确保结果小于 15 。” map (*3) . test ((<15) . (*3))意思是“确保三次输入小于 15，如果是，则返回三次输入。”