[ 本帖最后由 PeterGhostWolf 于 2010-1-5 21:56 编辑 ]作者: roy_hu 时间: 2010-01-06 00:57
你说的有点category theory的意思。函数确实组成一个monoid：
(f . g) . h = f . (g . h)
id . f = f
f . id = f
[ 本帖最后由 roy_hu 于 2010-1-6 15:28 编辑 ]作者: win_hate 时间: 2010-01-06 13:55
楼主应该把问题陈述得更精确一些。至少把 domain 和 codomain 明确下来，否则 f g 有意义， g f 就不一定有意义了。由于一个映射不必是单的，所以不一定有逆。在代数中，有如下结论：
lambda演算确实可以看做是一个代数结构，其元素是lambda算子，相关的二元运算是apply（apply f x ，就是我们通常写的 f(x)）。
但是，这个代数结构，既不是群，也不是半群，而是比他们都更一般。
因为群比半群更特殊，所以我直接说为什么它不是半群了：因为半群要求相关的二元运算满足结合律，而apply是不满足结合律的。
(apply f (apply g x)) = (apply (combine f g) x)
!= (apply (apply f g) x)
where:
apply = lambda f. lambda a. f a = lambda f. lambda g. lambda x. (f g) x （这里逆用了eta规约，为了与下面更好对比）
combine = lambda f. lambda g. lambda x. f (g x)