Yc的使用场景

接触函数式编程不可避免的要碰到yc(y combinator)这个让人无法轻易理解的东西。简单的说就是让lambda表达式拥有了递归能力。在我的脑海中我会把递归想像成一个绳结。当一个绳结比较松散，就代表了一个普通的递归，这样的递归你能看清楚他的意思。当我把绳子拉到最紧的状态，这个结就收缩到一个点上让人无法看清，yc也是这样，把递归的特性浓缩在一个点上了，所以让人无法看清楚。我到现在为止每次回忆yc脑子里还是需要推演一番。先打一个松散的结，然后一步一步把绳子抽紧才能得到结果。

虽然yc非常重要但是在我粗浅的编程生涯中还一次都没有直接的使用过。所以我难免就感觉这个东西太过理论化了，现实世界的递归哪会用到这个。但是前两天居然被我发现了一个使用场景。

当时我正在使用我写的一个类型校验库，这个库提供一系列函数比如Num, Str, Bool等等。当我输入一个正确的类型函数会原封不动返回这个值（当然也可以是从字符串parse之后的值，比如Num('1')返回1）如果不是正确的类型就会报错。并且还有一些列的类型组合工具比如Obj， Arr。这样我就能组合出我想校验的任何类型了。比如我需要校验一个布尔类型的数组我可以构造这样一个校验Arr(Bool)。

然后问题就出现了。如果我想构建一棵树类型我应该如何去构建？我最初自然而然的写下了如下代码

const NumTree = Obj({
  value: Num,
  left: Or(NumTree, Null),
  right: Or(NumTree, Null), //子树可以为空
})

以上代码毫无疑问的报错了，因为我定义NumTree的时候使用了自己。更不要说我还想把这个类型再抽象成一个类型组合器。下面的代码在构造类型的时候会无限的调用Tree。

const Tree = Type => Obj({
  value: Type,
  left: Or(Tree(Type), Null),
  right: Or(Tree(Type), Null),
})

这个时候就到yc登场了，因为我的检测工具是一些列函数，简直就是为了yc而生的。完美解决问题。

const y = g => (f => f(f))(n => g((...p) => n(n)(...p)))
const NumTree = y(Self => Obj({
  value: Num,
  left: Or(Self, Null),
  right: Or(Self, Null),
}))

const Tree = Type => y(Self => Obj({
  value: Type,
  left: Or(Self, Null),
  right: Or(Self, Null),
}))