如何读懂并写出装逼的函数式代码

如何读懂并写出装逼的函数式代码

drawing-recursive今天在微博上看到了 有人分享了下面的这段函数式代码,我把代码贴到下面,不过我对原来的代码略有改动,对于函数式的版本,咋一看,的确令人非常费解,仔细看一下,你可能就晕掉了,似乎完全就是天书,看上去非常装逼,哈哈。不过,我感觉解析那段函数式的代码可能会一个比较有趣过程,而且,我以前写过一篇《函数式编程》的入门式的文章,正好可以用这个例子,再升华一下原来的那篇文章,顺便可以向大家更好的介绍很多基础知识,所以写下这篇文章。

先看代码

这个代码平淡无奇,就是从一个数组中找到一个数,O(n)的算法,找不到就返回 null。

下面是正常的 old-school 的方式。不用多说。

//正常的版本
function find (x, y) {
  for ( let i = 0; i < x.length; i++ ) {
    if ( x[i] == y ) return i;
  }
  return null;
}

let arr = [0,1,2,3,4,5]
console.log(find(arr, 2))
console.log(find(arr, 8))

结果到了函数式成了下面这个样子(好像上面的那些代码在下面若影若现,不过又有点不太一样,为了消掉if语言,让其看上去更像一个表达式,动用了 ? 号表达式):

//函数式的版本
const find = ( f => f(f) ) ( f =>
  (next => (x, y, i = 0) =>
    ( i >= x.length) ?  null :
      ( x[i] == y ) ? i :
        next(x, y, i+1))((...args) =>
          (f(f))(...args)))

let arr = [0,1,2,3,4,5]
console.log(find(arr, 2))
console.log(find(arr, 8))

为了讲清这个代码,需要先补充一些知识。

Javascript的箭头函数

首先先简单说明一下,ECMAScript2015 引入的箭头表达式。箭头函数其实都是匿名函数,其基本语法如下:

(param1, param2, …, paramN) => { statements } 
(param1, param2, …, paramN) => expression
     // 等于 :  => { return expression; } 

// 只有一个参数时,括号才可以不加:
(singleParam) => { statements }
singleParam => { statements }

//如果没有参数,就一定要加括号:
() => { statements }

下面是一些示例:

var simple = a => a > 15 ? 15 : a; 
simple(16); // 15
simple(10); // 10

let max = (a, b) => a > b ? a : b;

// Easy array filtering, mapping, ...

var arr = [5, 6, 13, 0, 1, 18, 23];
var sum = arr.reduce((a, b) => a + b);  // 66
var even = arr.filter(v => v % 2 == 0); // [6, 0, 18]
var double = arr.map(v => v * 2);       // [10, 12, 26, 0, 2, 36, 46]

看上去不复杂吧。不过,上面前两个 simple 和 max 的例子都把这箭头函数赋值给了一个变量,于是它就有了一个名字。有时候,某些函数在声明的时候就是调用的时候,尤其是函数式编程中,一个函数还对外返回函数的时候。比如下在这个例子:

function MakePowerFn(power) {
  return function PowerFn(base) {
    return Math.pow(base, power);
  } 
}

power3 = MakePowerFn(3); //制造一个X的3次方的函数
power2 = MakePowerFn(2); //制造一个X的2次方的函数

console.log(power3(10)); //10的3次方 = 1000
console.log(power2(10)); //10的2次方 = 100

其实,在 MakePowerFn 函数里的那个 PowerFn 根本不需要命名,完全可以写成:

function MakePowerFn(power) {
  return function(base) {
    return Math.pow(base, power);
  } 
}

如果用箭头函数,可以写成:

MakePowerFn = power  => {
  return base => {
    return Math.pow(base, power);
  } 
}

我们还可以写得更简洁(如果用表达式的话,就不需要 { 和 }, 以及 return 语句 ):

MakePowerFn = power => base => Math.pow(base, power)

我还是加上括号,和换行可能会更清楚一些:

MakePowerFn = (power) => (
  (base) => (Math.pow(base, power))
)

好了,有了上面的知识,我们就可以进入一个更高级的话题——匿名函数的递归。

匿名函数的递归

函数式编程立志于用函数表达式消除有状态的函数,以及for/while循环,所以,在函数式编程的世界里是不应该用for/while循环的,而要改用递归(递归的性能很差,所以,一般是用尾递归来做优化,也就是把函数的计算的状态当成参数一层一层的往下传递,这样语言的编译器或解释器就不需要用函数栈来帮你保存函数的内部变量的状态了)。

好了,那么,匿名函数的递归该怎么做?

一般来说,递归的代码就是函数自己调用自己,比如我们求阶乘的代码:

function fact(n){
  return n==0 ? 1 :  n * fact(n-1);
};
result = fact(5);

在匿名函数下,这个递归该怎么写呢?对于匿名函数来说,我们可以把匿名函数当成一个参数传给另外一个函数,因为函数的参数有名字,所以就可以调用自己了。 如下所示:

function combinator(func) {
  func(func);
}

这个是不是有点作弊的嫌疑?Anyway,我们再往下,把上面这个函数整成箭头函数式的匿名函数的样子。

(func) => (func(func)) 

现在你似乎就不像作弊了吧。把上面那个求阶乘的函数套进来是这个样子:

首先,先重构一下fact,把fact中自己调用自己的名字去掉:

function fact(func, n) {
  return n==0 ? 1 :  n * func(func, n-1);
}

fact(fact, 5); //输出120

然后,我们再把上面这个版本变成箭头函数的匿名函数版:

var fact = (func, n) => ( n==0 ? 1 :  n * func(func, n-1) )
fact(fact, 5)

这里,我们依然还要用一个fact来保存这个匿名函数,我们继续,我们要让匿名函数声明的时候,就自己调用自己。

也就是说,我们要把

(func, n) => ( n==0 ? 1 :  n * func(func, n-1) )

这个函数当成调用参数,传给下面这个函数:

(func, x) => func(func, x) 

最终我们得到下面的代码:

 
( (func, x) => func(func, x) ) (  //函数体
  (func, n) => ( n==0 ? 1 :  n * func(func, n-1) ), //第一个调用参数
  5 //第二调用参数
); 

好像有点绕,anyway, 你看懂了吗?没事,我们继续。

动用高阶函数的递归

但是上面这个递归的匿名函数在自己调用自己,所以,代码中有hard code的实参。我们想实参去掉,如何去掉呢?我们可以参考前面说过的那个 MakePowerFn 的例子,不过这回是递归版的高阶函数了。

HighOrderFact = function(func){
  return function(n){
    return n==0 ? 1 : n * func(func)(n-1);
  };
};

我们可以看,上面的代码简单说来就是,需要一个函数做参数,然后返回这个函数的递归版本。那么,我们怎么调用呢?

fact = HighOrderFact(HighOrderFact);
fact(5); 

连起来写就是:

HighOrderFact ( HighOrderFact ) ( 5 )

但是,这样让用户来调用很不爽,所以,以我们一个函数把 HighOrderFact ( HighOrderFact ) 给代理一下:

fact = function ( hifunc ) {
  return hifunc ( hifunc );
} (
  //调用参数是一个函数
  function (func) { 
    return function(n){
      return n==0 ? 1 : n * func(func)(n-1);
    };
  }
);

fact(5); //于是我们就可以直接使用了

用箭头函数重构一下,是不是简洁了一些?

fact = (highfunc => highfunc ( highfunc ) ) (
  func => n =>  n==0 ? 1 : n * func(func)(n-1)
);

上面就是我们最终版的阶乘的函数式代码。

回顾之前的程序

我们再来看那个查找数组的正常程序:

//正常的版本
function find (x, y) {
  for ( let i = 0; i < x.length; i++ ) {
    if ( x[i] == y ) return i;
  }
  return null;
}

先把for干掉,搞成递归版本:

function find (x, y, i=0) {
  if ( i >= x.length ) return null;
  if ( x[i] == y ) return i;
  return find(x, y, i+1);
}

然后,写出带实参的匿名函数的版本(注:其中的if代码被重构成了 ?号表达式):

( (func, x, y, i) => func(func, x, y, i) ) (  //函数体
  (func, x, y, i=0) => (
      i >= x.length ?  null :
         x[i] == y  ?  i : func (func, x, y, i+1)
  ), //第一个调用参数
  arr, //第二调用参数
  2 //第三调用参数
)

最后,引入高阶函数,去除实参:

const find = ( highfunc => highfunc( highfunc ) ) (
   func => (x, y, i = 0) => (
     i >= x.length ?  null :
           x[i] == y  ?  i : func (func) (x, y, i+1)
   )
);

注:函数式编程装逼时一定要用const字符,这表示我写的函数里的状态是 immutable 的,天生骄傲!

再注:我写的这个比原来版的那个简单了很多,原来版本的那个又在函数中套了一套 next, 而且还动用了不定参数,当然,如果你想装逼装到天上的,理论上来说,你可以套N层,呵呵。

现在,你可以体会到,如此逼装的是怎么来的了吧?

其它

你还别说这就是装逼,简单来说,我们可以使用数学的方式来完成对复杂问题的描述,那怕是递归。其实,这并不是新鲜的东西,这是Alonzo Church 和 Haskell Curry 上世纪30年代提出来的东西,这个就是 Y Combinator 的玩法,关于这个东西,你可以看看下面两篇文章:

The Y Combinator (Slight Return)》,

Wikipedia: Fixed-point combinator

(全文完)


关注CoolShell微信公众账号可以在手机端搜索文章

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

——=== 访问 酷壳404页面 寻找遗失儿童。 ===——
好烂啊有点差凑合看看还不错很精彩 (26 人打了分,平均分: 4.62 )
Loading...

如何读懂并写出装逼的函数式代码》的相关评论

  1. 关于js里的不动点组合子,有个更加实用的例子,可以参考http://matt.might.net/articles/implementation-of-recursive-fixed-point-y-combinator-in-javascript-for-memoization/

  2. 在没有 pattern matching 的语言里搞 FP,总觉得怪怪的。开头那个 JavaScript 函数,感觉就像这里曾经介绍过的 Java 里的 OOP 的代码一样,很做作。FP 明明应该很易读:

    find x y = find' x y 0
    find' [] y _               = Nothing
    find' (x: xs) y n | x == y = Just n
    find' (_: xs) y n          = find' xs y (n+1)
    
    main =
      print $ find [1,2,3] 1
  3. 肉眼括号匹配是看清楚上述代码的一大障碍。Haskell的非括号语法应该有这点考量吧。

  4. :
    肉眼括号匹配是看清楚上述代码的一大障碍。Haskell的非括号语法应该有这点考量吧。

    用Lisp的人会告诉你,匹配括号是编辑器的事。

  5. 用 ?: 来“消除”if是不是有点太自欺欺人了…非要搞的话还是用模式匹配更清爽点,然而js并没有

    港真,代码可读性才是第一位,极端OOP和极端FP搞得代码更难读的话就都是邪教,该电

  6. JS 里没必要用 (f => f(f))(fn) 来确保有名函数 fn 里对自身的引用吧
    const f = x => x > 0 ? f(x – 1) : x

  7. find(List, Val) ->
    find(List, Val, 1).

    find([H|_], H, Len) ->
    Len;
    find([_|T], Val, Len) ->
    find(T, Val, Len+1);
    find([], _, _) ->
    null.

  8. 在我看来,就是一个关于匿名函数如何在其函数体内引用自身的问题。补充一个LISP的实现:

    (define find (lambda [x y] (((lambda [highfunc] (highfunc highfunc)) (lambda [func] (lambda [i end x y] (cond [(> i end) #none] [(eq y (car x)) i] [#true ((func func) (inc i) end (cdr x) y)])))) 1 (length x) x y)))

  9. 依云 :
    在没有 pattern matching 的语言里搞 FP,总觉得怪怪的。开头那个 JavaScript 函数,感觉就像这里曾经介绍过的 Java 里的 OOP 的代码一样,很做作。FP 明明应该很易读:
    find x y = find’ x y 0
    find’ [] y _ = Nothing
    find’ (x: xs) y n | x == y = Just n
    find’ (_: xs) y n = find’ xs y (n+1)

    main =
    print $ find [1,2,3] 1

    是哦,所以某些只从JavaScript(普及与多范式)入门函数式编程思想的人们把函数式编程给怒喷了……

  10. python version
    fact = (lambda fb: fb(fb) )(( lambda func: lambda n : ( n==0 and 1 or n * func(func)(n-1) ) ))
    …学习了新知识…并不太明白要用到哪里…

  11. 看完一阵发冷,硬是没看懂这样写到底意义何在?求陈皓大大具体说说这样的函数式编程能为我们带来什么,感谢!

  12. 大哥你连 Y Combinator 都没用上,装逼都不够彻底。你虽然有提到 Y Combinator,但你的文章中却没有出现,估计你是没弄懂。在我看来,这篇文章娱乐性居多。我还是认真一下,函数式编程是以抽象且可读性高为基本要求,并且多利用尾递归 (因为把尾递归优化成循环是函数式语言编译器的基本要求),如果真的有必要只使用语言提供的核心功能来写 find 函数,真正的函数式编程写这个程序应该要类似这样(我不懂 javascript,所以这边我用的是虚拟码):
    function find (arr : Array, n : T) : Optional {
    if (arr.empty()) {
    return None();
    } else {
    function loop(index : int) {
    if (index == arr.length) return None();
    if (arr[index] == n) return Some(index);
    loop(index+1);
    };
    return loop(0) ;
    }
    }

  13. 1. 如果仅仅是函数式编程,把for变成递归就够了。因为很多函数式编程语言并没有可变量。
    2. 文章中的函数变形步骤正是提取Y Combinator 的过程。个人感觉Y Combinator的作用只体现在不能够给函数/lambda表达式命名的语言中。一般情况下没必要刻意使用。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*