Haskell函数组合与Map函数

你测试过

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

这确实是错误的。该物业实际上是

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

其中 LHS 关联为

test p . f = (test p) . f

请记住，函数应用程序比任何用户可定义的运算符都更紧密地绑定，就像 .两个彼此相邻的标识符始终是前缀函数应用程序的一部分。（除了 as-patterns： means .） 的情况。infixl 10f xs@ys zsf (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)315map (*3) . test ((<15) . (*3))15

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

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

换句话说，它说使用某个函数修改一个值，然后，给定一些合适的谓词，应用在它上面与使用后修改值是一样的（通过用 组合谓词来适当地修改谓词，使其适合未修改值的类型）。fptest ptestf

接下来，我们来考虑一下：test

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

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

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

• 参数化：一无所有的钱和免费定理，作者是 Bartosz Milewski，如果你想更深入地挖掘，这是一个很好的阐述，指向关键的主要来源。

• fmap Preserve是什么？，就你而言，这并不完全是关于自由定理的，但它以一种（希望）易于理解的方式呈现了一些相关的主题。

• 相关 Stack Overflow 帖子：amalloy 对多态推理的回答;键入永远没有意义的签名。

• Lambdabot 可以为您生成免费定理。您可以将其用作命令行工具，也可以通过在 #haskell Freenode IRC 频道上运行的机器人使用它。