< 返回版块

jellybobbin 发表于 2020-03-04 15:08

Tags:Rust closure lambda

先看以下Javascript阶乘例子:

一般函数递归:

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

把fact中自己调用自己的名字去掉:

function fact(func, n) {
  return n==0 ? 1 :  n * func(func, n-1);
}
 
fact(fact, 5); //输出120

上面我们依然还要用一个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 //第二调用参数
);

动用高阶函数的递归:

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); //于是我们就可以直接使用了

Rust也是函数式编程语言,但是是强类型,今天小试了一下,如果就直接按照复制粘贴式 改成Rust语法的话,在匿名函数参数类型上不能显示标注类型,下面的impl Fn(func,u32)->u32 中的 func:

let fact = |f:impl Fn(func,u32)->u32,n:u32| -> u32{
    match n{
        0|1 => 1,
        _ => n * func(func,n-1)
    }
};

今天群里有位朋友说 可以通过匿名函数(lambda)构造不动点组合子来形成递归 不知道具体实现方式,这里请教一下用匿名函数递归调用的方式 怎么实现 fact(n) 就能直接求出n的阶乘.如果有playground 链接最好啦, 万分感谢.

评论区

写评论
lithbitren 2020-06-25 12:51

不小心翻进来了,记得刷题的时候想试试匿名函数递归,在StackOverflow搜到的也是这个例子,想应用到二叉树遍历上怎么都跑不通。

AlephAlpha 2020-03-05 13:48

对以下内容的回复:

// 必须用 struct;

这里的注释没写完……后面漏了半句:“如果用 type 会导致类型无限循环。”

作者 jellybobbin 2020-03-05 09:52

hahahaha... 对以下内容的回复:

作者 jellybobbin 2020-03-05 09:51

对于Js来说 调用方便, 对于Rust来说,试一试总是没坏处的 对以下内容的回复:

作者 jellybobbin 2020-03-05 09:50

昨天晚上看了张汉东老师的一篇关于Rust Y组合子的文章,他使用的Trait , 也是这个思想.非常感谢. 对以下内容的回复:

xie-jirong 2020-03-04 20:32

有实用意义吗? 看着太晦涩了,消化不了。

AlephAlpha 2020-03-04 17:44

对以下内容的回复:

在 JavaScript 里,不动点组合子可以这样写,非常简单易懂:

这个“非常简单易懂”忘了加狗头……

AlephAlpha 2020-03-04 17:42

这个问题可以用 Box dyn 来解决:

// 必须用 struct;
struct RecFn<T>(Box<dyn Fn(&RecFn<T>, T) -> T>);

impl<T> RecFn<T> {
    fn call(&self, f: &RecFn<T>, n: T) -> T {
        (self.0)(f, n)
    }
}

let fact = RecFn(Box::new(|func: &RecFn<u32>, n: u32| -> u32 {
    match n {
        0 | 1 => 1,
        _ => n * func.call(func, n - 1),
    }
}))

Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=8800daec71af93296432241d9b0e44e0

用不动点组合子的话会遇到同样的问题,而且解决起来更麻烦。

在 JavaScript 里,不动点组合子可以这样写,非常简单易懂:

var Y = f => (x => f(x(x)))(x => f(x(x)));
var fact = Y(func => n => n == 0 ? 1 : n * func(n - 1));

或者

function Y(f) { return x => f(Y(f))(x) }
var fact = Y(func => n => n == 0 ? 1 : n * func(n - 1));

但 Rust 的话……你可以试着分析一下这里的 Y 应该是什么类型。

1 共 8 条评论, 1 页