Haskell 函数与map函数的组合

Question

我正在阅读 Richard Bird 的 "Thinking Functionally with 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)

这确实是错误的。属性实际上是

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

LHS 关联为

test p . f = (test p) . f

请记住，函数应用程序比任何用户可定义的运算符都更紧密地绑定，表现得像 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) 表示 "multiply by 3, ensuring that the result is less than 15." map (*3) . test ((<15) . (*3)) 表示 "ensure that thrice the input is less than 15, and, if so, return thrice the input."

Answer 2

涵盖了您的测试用例以及如何使用 test 的定义来证明方程。不过，我想说仍然存在一个潜在的问题：我们应该从哪个帽子得出这个等式——我们为什么要考虑它是真的可能性？为了回答这个问题，让我们首先再看一下等式：

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

换句话说，它表示使用一些 f 函数修改值，然后给定一些合适的谓词 p，对其应用 test p 与修改值相同在使用 test 之后（通过将谓词与 f 组合进行适当修改，使其适合未修改值的类型）。

接下来，让我们考虑test的类型：

-- I'm adding the implicit forall for the sake of emphasis.
forall a. (a -> Bool) -> a -> [a]

这里的关键是具有这种类型的函数必须适用于 a 的任何选择。如果它可以是任何东西，我们在用这种类型实现函数时事先不知道任何事情，比如 test。这严重限制了这样一个函数的功能：特别是，结果列表的元素（如果有的话）必须与提供的类型 a 的值相同（我们怎么能在不知道的情况下将其更改为其他内容它的类型提前？），并且谓词必须被忽略或应用于相同的值（我们还要将它应用于什么？）。考虑到这一点，等式现在说的很自然：我们在 test 之前或之后用 f 更改值并不重要，因为 test 不会更改值靠自己。

使这种推理变得严格的一种方法是通过自由定理。由于参数多态性，类型的自由定理保证始终适用于该类型的任何可能值，并且您不需要除类型以外的任何东西来计算它。碰巧 forall a. (a -> Bool) -> a -> [a] 的自由定理恰好是 test p . f = map f . test (p . f)。由于我不能在这些简短的行中公正地对待这个主题，这里有一些关于自由定理的参考资料：

Parametricity: Money for Nothing and Theorems for Free，作者 Bartosz Milewski，是一个很好的阐述，如果你想深入挖掘的话，它提供了指向主要主要来源的指针。
What Does fmap Preserve?，真的，不完全是关于自由定理，但它以（希望）一种易于访问的方式呈现了一些相关主题。
相关 Stack Overflow 帖子：amalloy's answer to Polymorphic reasoning; Type signatures that never make sense.
lambdabot 可以为您生成免费的定理。您可以将其用作命令行工具或通过在#haskell Freenode IRC 频道上运行的机器人来使用。

Haskell 函数与map函数的组合

Haskell Function Composition with Map Function

haskell

equality

proof

function-composition

map-function