lambda演算

[hqman]

lambda算子是函数式编程的基础。

定义

λ演算的语法只有三条： • <表达式> ::= <标识符> • <表达式> ::= λ <标识符+>. <表达式> • <表达式> ::= (<表达式> <表达式>)

学习资料

g9 λ专题 手把手教你做λ 简易版

curry化 单参来替代多参

按照定义函数和变量都是λ项，可以使用组合函数来实现多参数函数的形式，这就是curry化。 例如： x+y 先构造一个传入x的函数，此时x已经固定值然后在构造一个y+x的函数

λx.(λy.y+x)

lambda算子规则

1. Alpha转换
   传入参数变量可以用任何字符来替换 ，变量名不重要。 λx.x+2 等价 λy.y+2

2. Beta简化 参数代入规则 （ λx.x+2）3 x用3 代入为 3+2 多重嵌套的参数代入规则。 如：λ y . (λ x . x + y)) q 先把y 代入q 此时y=q 然后返回结果为 x + q 再如:2个参数的情况 (λ x y. x y) (λ z . z * z) 3 先把 z_z 代入前面的 x得出λ z.z_z，然后再把3 应用到y上得出3*3。

   综合例子: (λ z . ( x . x + z)) (x + 2) x变量重复用第一个规则把最外面的x换一个名字， 得出(λ z . (λ x . x + z)) (y + 2) 代入z 得出λx.x+y+2

[hqman]

lambda 数字

[hqman]

lambda 条件判断 布尔值

/**
*  λ 中不需要 if 这样的关键字
*  甚至不需要 true  false
*/

import _ from "ramda";

// var IF = function(cond) {
//   return function(then){
//     return function(els){
//       return cond(then)(els);
//     }
//   }
// }
var IF = _.curry((cond,then,els)=>cond(then)(els));

// var tru = function(then){
//   return function(els){
//     return then;
//   }
// }
var tru = _.curry((then,els)=>then);

// var fal = function(then){
//   return function(els){
//     return els;
//   }
// }
var fal = _.curry((then,els)=>els);
console.log(IF(tru)(1)(2));

console.log(IF(fal)(1)(2));

[hqman]

神器的Y 组合子 来实现匿名递归

知乎讨论->

// 普通的阶乘函数
var F1 = function(n) {
    if (n == 0) {
        return 1;
    } else {
        return n * F1(n - 1);
    }
}

console.log(F1(4))

var F2 = function(n) {
    function inner(n) {
        if (n == 0) {
            return 1;
        } else {
            return n * inner(n - 1);
        }
    }
    return inner(n);
}

// 省略内部引用函数名称  f(f)     f(x x)
var F3 = function(f) {
    return function(n) {
        if (n == 0) {
            return 1;
        } else {
            return n * f(f)(n - 1);
        }
    }
}

console.log(F3(F3)(4));

// lambda f. (lambda x. (f(x x)) lambda x. (f(x x)))
// Y Y == Y (Y Y)
var Y = function(g){
    var h= function(f){
      return function(n){
        return g(f(f))(n);
      }
    }
    return h(h);
}

var rel= Y(function(h){
  return function(n){
    if (n == 0) {
            return 1;
        } else {
            return n*h(n-1);
        }

}
});
console.log(rel(4));