第3讲-链表+重录计划(可报名),lambda演算用函数模拟链表
零=道=>道;
前继 = 自然数=>自然数();
后继 = 自然数=>()=>自然数;
一 = ()=>零;//1
二 = ()=>()=>零;//2
三 = ()=>()=>()=>零;//3
四 = ()=>()=>()=>()=>零;//4
五 = ()=>()=>()=>()=>()=>零;//5
真 = (选择一,选择二)=>选择一();
假 = (选择一,选择二)=>选择二();
如果 = (条件,选择一,选择二)=>条件(选择一,选择二);
非 = (条件)=>如果(条件,()=>假,()=>真);
或 = (条件一,条件二) =>
如果(条件一,()=>真,()=>如果(条件二,()=>真,()=>假));
与 = (条件一,条件二) =>
如果(条件一,()=>如果(条件二,()=>真,()=>假),()=>假);
为零=(自然数)=>自然数===零?真:假;
加 = (数一,数二) =>
如果(为零(数二)
,()=>数一
,()=>加(后继(数一),前继(数二))
);
减 = (数一,数二) =>
如果(为零(数一)
,()=>零
,()=>如果(为零(数二)
,()=>数一
,()=>减(前继(数一),前继(数二))
)
);
为一 = (自然数) => 如果(为零(自然数)
,()=>假
,()=>如果(为零(前继(自然数))
,()=>真
,()=>假)
);
乘非零 = (数一,数二) =>
如果(为一(数二)
,()=>数一
,()=>乘非零(加(数一,数一),减(数二,一))
);
乘 = (数一,数二) =>
如果(为零(数二)
,()=>零
,()=>乘非零(数一,数二)
);
相等=(数一,数二)=>如果(
与(为零(减(数一,数二)),
为零(减(数二,数一)))
,()=>真
,()=>假);
小于=(数一,数二) => 如果(
与(为零(减(数一,数二)),
非(为零(减(数二,数一))))
,()=>真
,()=>假);
大于=(数一,数二) => 如果(
与(非(为零(减(数一,数二))),
为零(减(数二,数一)))
,()=>真
,()=>假);
// 斐波那契数
// 第一个月初有一对刚诞生的兔子
// 第二个月之后（第三个月初）它们可以生育
// 每月每对可生育的兔子会诞生下一对新兔子
// 兔子永不死去
// 过了100个月,总计有多少兔子?
//1,1,2,3,5,8,13,……,斐(第88个月),斐(第89个月),斐(第88个月)+斐(第89个月),
斐波那契数 = (第几个月) =>
如果(或(为零(第几个月),为一(第几个月)),
()=>一,
()=>加(斐波那契数(减(第几个月,一))
,斐波那契数(减(第几个月,二)))
);
展现自然数 = (自然数) =>
如果(
为零(自然数),
() => '',
() => 展现自然数(前继(自然数)) + '壹'
);
// 链表
对子 = (左,右) => 取子 => 取子(左,右);
取左 = (左,右) => 左 ;
取右 = (左,右) => 右 ;
创建链表 = () => 取子 => 取子(真,真);
插入 = (链表,元素) => 对子(链表,元素);
链表头 = 创建链表();
链表一 = 插入(链表头,一);
链表二 = 插入(链表一,二);
链表三 = 插入(链表二,三);
链表四 = 插入(链表三,四);
链表五 = 插入(链表四,五);
空 = (链表)=> 链表(取左)===真?真:假;
展现链表 = (链表,展示方式) => 如果(空(链表)
,()=>'头'
,()=>展现链表(链表(取左),展示方式) + '->' + 展示方式(链表(取右)))
;
展现链表(链表四,展现自然数);
存在 = (链表,条件)=> 如果(空(链表)
,()=>假
,()=>如果(条件(链表(取右))
,()=>真
,()=>存在(链表(取左),条件)
));
展现真假 = (条件)=>如果(条件,()=>'真',()=>'假');
展现真假(存在(链表二,(数)=>大于(数,三)));
展现真假(存在(链表三,(数)=>大于(数,三)));
展现真假(存在(链表四,(数)=>大于(数,三)));
查找 = (链表,条件) => 如果(空(链表)
,()=>假
,()=>如果(条件(链表(取右))
,()=>链表(取右)
,()=>查找(链表(取左),条件)
));
查找(链表一,(数)=>相等(数,三));
查找(链表三,(数)=>相等(数,三));
查找(链表四,(数)=>相等(数,三));
映射 = (链表,条件) => 如果(空(链表)
,()=>链表
,()=>插入(映射(链表(取左),条件),条件(链表(取右))));
展现链表(映射(链表四,(内容)=>真),展现真假);
展现链表(映射(链表四,(内容)=>大于(内容,二)),展现真假);
逆序临时 = (链表,新链表) => 如果(空(链表)
,()=> 新链表
,()=> 逆序临时(链表(取左),插入(新链表,链表(取右)))
)
;
逆序 = (链表) => 逆序临时(链表,创建链表());
展现链表(逆序(链表五),展现自然数);
聚合 = (链表,聚方法,处理空) => 如果(空(链表)
,()=> 处理空
,()=> 聚方法(聚合(链表(取左),聚方法,处理空)
,链表(取右))
)
;
// 链表求和
聚合(链表一,(前,后)=>加(前,后),零);
求和 = (链表) => 聚合(链表,(前,后)=>加(前,后),零);
聚合(链表四,
(前,后)=> 前 + '->' + 展现自然数(后),
'头');
展现链表 = (链表,展现方式) =>
聚合(链表,
(前,后)=> 前 + '->' + 展现方式(后),
'头');
展现自然数链表 = (链表) => 展现链表(链表,展现自然数);
