免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 46935 | 回复: 6

突然想起来一个关于lambda演算的问题 [复制链接]

论坛徽章:
0
发表于 2010-01-05 21:49 |显示全部楼层
考虑所有的lambda函数的等价类(因为有许多形式上不一样的函数表达同一个东西)的集合,能否给这个集合一个代数结构?
如果我们把一个lambda函数以另一个为参数作用,看作是一个非交换的运算,那么这个集合已经接近构成一个群或者半群((lambda (x) x)是幺元,并且任何两个函数的结合还是函数),但是这似乎还不够,我觉得我无法说明一个lambda函数有逆,也无法否定它.
哦,还有,lambda演算是否满足结合率?似乎是满足的:f(g(h)) = (f(g))(h)?
各位大牛能否给出一个比较简洁的说法,或者推荐一些参考资料呢?谢谢!

[ 本帖最后由 PeterGhostWolf 于 2010-1-5 21:56 编辑 ]

论坛徽章:
0
发表于 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 编辑 ]

论坛徽章:
0
发表于 2010-01-06 13:55 |显示全部楼层
楼主应该把问题陈述得更精确一些。至少把  domain 和  codomain 明确下来,否则 f g 有意义, g f 就不一定有意义了。由于一个映射不必是单的,所以不一定有逆。在代数中,有如下结论:

1、一个集合到自身的变换构成一个幺半群;
2、一个集合到自身的一一变换构成一个群。

如果要求 domain 和 codomain 不同,可以参考范畴方面的材料。

[ 本帖最后由 win_hate 于 2010-1-6 13:57 编辑 ]

论坛徽章:
0
发表于 2010-01-06 16:48 |显示全部楼层
domain和codomain是所有lambda函数等价类构成的集合,因为每一个lambda函数作用在另一个lambda函数上还是得到一个lambda函数.
我纠结在"逆"这里,我不能确定一个lambda函数可以成为一个这个集合的变换,也没有什么思路.这样看起来它似乎已经是一个含幺半群了,我觉得还有再向前走的能力....
范畴学我一无所知,要过一段时间才有机会学到(现在知识还不足以接触T T)

论坛徽章:
0
发表于 2015-03-02 17:49 |显示全部楼层
本帖最后由 luochen1990 于 2015-03-03 14:41 编辑

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)

后来又想了一下,如果不取apply,而是用combine作为定义半群的二元运算,那么应该可以构成一个幺半群

后续讨论可以见我在知乎的提问:www DOT zhihu DOT com/question/28481538

论坛徽章:
6
2015年辞旧岁徽章
日期:2015-03-05 16:13:092015年迎新春徽章
日期:2015-03-05 16:13:092015小元宵徽章
日期:2015-03-06 15:58:1815-16赛季CBA联赛之浙江
日期:2016-11-05 14:38:4115-16赛季CBA联赛之新疆
日期:2016-11-11 18:38:06
发表于 2015-03-03 16:02 |显示全部楼层
((lambda (x) x)是幺元,那零元如何表示呢?

论坛徽章:
1
数据库技术版块每日发帖之星
日期:2015-09-25 06:20:00
发表于 2015-09-22 16:28 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP