recursion - 再帰的関数リテラル/無名関数をサポートする言語は?

Question

最近では、かなりの数の主流言語が関数リテラルをサポートしているようです。無名関数とも呼ばれますが、名前があっても構いません。重要なことは、関数リテラルは、他の場所でまだ定義されていない関数を生成する式であるため、たとえば C では&printfカウントされないということです。

追加する編集：本物の関数リテラル式がある場合は、それを関数に渡すか、すぐに引数に適用<exp>できるはずです。.f(<exp>)<exp>(5)

recursiveである関数リテラルを記述できる言語はどれか知りたいです。ウィキペディアの「匿名再帰」の記事には、プログラミングの例はありません。

再帰的階乗関数を例として使用しましょう。

ここに私が知っているものがあります：

JavaScript / ECMAScript でそれを行うことができますcallee:

function(n){if (n<2) {return 1;} else {return n * arguments.callee(n-1);}}

を使用する言語では簡単ですletrec。たとえば、Haskell (これはそれを呼び出しますlet):

let fac x = if x<2 then 1 else fac (x-1) * x in fac

LispとSchemeにも同等のものがあります。のバインディングはfac式に対してローカルであるため、式全体が実際には無名関数であることに注意してください。

他にもありますか？

score 16 · Accepted Answer

Most languages support it through use of the Y combinator. Here's an example in Python (from the cookbook):

# Define Y combinator...come on Gudio, put it in functools!
Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg)))

# Define anonymous recursive factorial function
fac = Y(lambda f: lambda n: (1 if n<2 else n*f(n-1)))
assert fac(7) == 5040

score 7 · Accepted Answer

C#

Wes Dyer のブログを読むと、@Jon Skeet の回答が完全に正しくないことがわかります。私は言語の天才ではありませんが、再帰的な匿名関数と「fib 関数は実際には、ローカル変数 fib が参照するデリゲートを呼び出すだけです」とブログから引用することには違いがあります。

実際の C# の回答は次のようになります。

delegate Func<A, R> Recursive<A, R>(Recursive<A, R> r);

static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f)
{
    Recursive<A, R> rec = r => a => f(r(r))(a);
    return rec(rec);
}

static void Main(string[] args)
{
    Func<int,int> fib = Y<int,int>(f => n => n > 1 ? f(n - 1) + f(n - 2) : n);
    Func<int, int> fact = Y<int, int>(f => n => n > 1 ? n * f(n - 1) : 1);
    Console.WriteLine(fib(6));                          // displays 8
    Console.WriteLine(fact(6));
    Console.ReadLine();
}

score 5 · Accepted Answer

You can do it in Perl:

my $factorial = do {
  my $fac;
  $fac = sub {
    my $n = shift;
    if ($n < 2) { 1 } else { $n * $fac->($n-1) }
  };
};

print $factorial->(4);

The do block isn't strictly necessary; I included it to emphasize that the result is a true anonymous function.

score 4 · Accepted Answer

Well, apart from Common Lisp (labels) and Scheme (letrec) which you've already mentioned, JavaScript also allows you to name an anonymous function:

var foo = {"bar": function baz() {return baz() + 1;}};

which can be handier than using callee. (This is different from function in top-level; the latter would cause the name to appear in global scope too, whereas in the former case, the name appears only in the scope of the function itself.)

score 4 · Accepted Answer

Perl 6 では:

my $f = -> $n { if ($n <= 1) {1} else {$n * &?BLOCK($n - 1)} }
$f(42);  # ==> 1405006117752879898543142606244511569936384000000000

score 2 · Accepted Answer

ここでいくつかの用語を混同しました。関数リテラルは匿名である必要はありません。

javascriptでは、関数がステートメントとして記述されているか式として記述されているかによって違いが異なります。この質問への回答の違いについていくつかの議論があります。

例を関数に渡しているとしましょう。

foo(function(n){if (n<2) {return 1;} else {return n * arguments.callee(n-1);}});

これは次のように書くこともできます。

foo(function fac(n){if (n<2) {return 1;} else {return n * fac(n-1);}});

どちらの場合も、それは関数リテラルです。ただし、2番目の例では、名前が周囲のスコープに追加されていないことに注意してください。これは混乱を招く可能性があります。ただし、一部のjavascript実装はこれをサポートしていないか、バグのある実装があるため、これは広く使用されていません。私はそれが遅いことも読んだ。

匿名再帰はまた別の何かです。関数がそれ自体を参照せずに再帰する場合、YCombinatorについてはすでに説明しました。ほとんどの言語では、より良い方法が利用できるので、それは必要ありません。これがjavascript実装へのリンクです。

score 2 · Accepted Answer

2

F#には "let rec" があります

于 2008-10-01T05:48:40.957 に答える

score 1 · Accepted Answer

Mathematica では、次のよう#0に、関数自体を示すためにを使用して再帰関数を定義できるようです。

(expression[#0]) &

例えば階乗：

fac = Piecewise[{{1, #1 == 0}, {#1 * #0[#1 - 1], True}}] &;

これは#i、i 番目のパラメーターを参照する表記法と、スクリプトが独自の 0 番目のパラメーターであるというシェルスクリプトの規則に沿っています。

score 1 · Accepted Answer

C# では、デリゲートを保持する変数を宣言し、null を割り当てて確実に割り当てられるようにする必要があります。その後、割り当てたラムダ式内から呼び出すことができます。

Func<int, int> fac = null;
fac = n => n < 2 ? 1 : n * fac(n-1);
Console.WriteLine(fac(7));

C#チームが明確な割り当てのルールを変更して、個別の宣言/初期化を不要にすることを検討しているという噂を聞いたと思いますが、私はそれを誓いません。

これらの言語/ランタイム環境のそれぞれに関する重要な質問の 1 つは、それらがテールコールをサポートしているかどうかです。C# では、私が知る限り、MS コンパイラは IL オペコードを使用しませんが、特定の状況でtail.は JITがとにかく最適化する可能性があります。明らかに、これにより、動作中のプログラムとスタックオーバーフローの違いが非常に簡単にわかります。(これをもっと制御したり、いつ発生するかを保証したりできると便利です。そうしないと、あるマシンで動作するプログラムが別のマシンではわかりにくい方法で失敗する可能性があります。)

編集: FryHardが指摘したように、これは単なる疑似再帰です。仕事を終わらせるには十分に単純ですが、Y-combinator はより純粋なアプローチです。上に投稿したコードにはもう 1 つ注意点があります。の値を変更すると、ラムダ式が変数自体facをキャプチャしたため、古い値を使用しようとすると失敗し始めます。fac（もちろん、適切に動作するために必要です...）

score 1 · Accepted Answer

dbstack() イントロスペクションを使用してそれ自体の関数リテラルを取得し、それを評価する無名関数を使用して、Matlab でこれを行うことができます。(dbstack はおそらく言語外であると見なされるべきであるため、これは不正行為であることは認めますが、すべての Matlab で利用できます。)

f = @(x) ~x || feval(str2func(getfield(dbstack, 'name')), x-1)

これは、x からカウントダウンしてから 1 を返す無名関数です。Matlab には ?: 演算子がなく、無名関数内の if ブロックが許可されていないため、あまり役に立ちません。したがって、基本ケース/再帰ステップ形式を構築するのは困難です。

f(-1); を呼び出すことで、再帰的であることを示すことができます。無限にカウントダウンし、最終的に最大再帰エラーをスローします。

>> f(-1)
??? Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N)
to change the limit.  Be aware that exceeding your available stack space can
crash MATLAB and/or your computer.

また、feval に直接渡すことで、匿名関数を変数にバインドせずに直接呼び出すことができます。

>> feval(@(x) ~x || feval(str2func(getfield(dbstack, 'name')), x-1), -1)
??? Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N)
to change the limit.  Be aware that exceeding your available stack space can
crash MATLAB and/or your computer.

Error in ==> create@(x)~x||feval(str2func(getfield(dbstack,'name')),x-1)

それを有用なものにするために、「if」を使用して再帰ケースを評価から保護する、再帰ステップロジックを実装する別の関数を作成できます。

function out = basecase_or_feval(cond, baseval, fcn, args, accumfcn)
%BASECASE_OR_FEVAL Return base case value, or evaluate next step
if cond
    out = baseval;
else
    out = feval(accumfcn, feval(fcn, args{:}));
end

それを考えると、ここに階乗があります。

recursive_factorial = @(x) basecase_or_feval(x < 2,...
    1,...
    str2func(getfield(dbstack, 'name')),...
    {x-1},...
    @(z)x*z);

そして、バインドせずに呼び出すことができます。

>> feval( @(x) basecase_or_feval(x < 2, 1, str2func(getfield(dbstack, 'name')), {x-1}, @(z)x*z), 5)
ans =
   120

score 0 · Accepted Answer

匿名関数はラムダを含むC++0xに存在し、匿名についてはよくわかりませんが、再帰的になる可能性があります。

auto kek = [](){kek();}

score 0 · Accepted Answer

私は興味があったので、実際にMATLABでこれを行う方法を考え出そうとしました。実行できますが、少しルーブ・ゴールドバーグ風に見えます。

>> fact = @(val,branchFcns) val*branchFcns{(val <= 1)+1}(val-1,branchFcns);
>> returnOne = @(val,branchFcns) 1;
>> branchFcns = {fact returnOne};
>> fact(4,branchFcns)

ans =

    24

>> fact(5,branchFcns)

ans =

   120

score 0 · Accepted Answer

これはまさにあなたが探しているものではないかもしれませんが、Lisp では「ラベル」を使用して、再帰的に呼び出すことができる関数を動的に宣言できます。

(labels ((factorial (x) ;define name and params
    ; body of function addrec
    (if (= x 1)
      (return 1)
      (+ (factorial (- x 1))))) ;should not close out labels
  ;call factorial inside labels function
  (factorial 5)) ;this would return 15 from labels

score 0 · Accepted Answer

Delphi には、バージョン 2009 の無名関数が含まれています。

http://blogs.codegear.com/davidi/2008/07/23/38915/の例

type
  // method reference
  TProc = reference to procedure(x: Integer);               

procedure Call(const proc: TProc);
begin
  proc(42);
end;

使用する：

var
  proc: TProc;
begin
  // anonymous method
  proc := procedure(a: Integer)
  begin
    Writeln(a);
  end;               

  Call(proc);
  readln
end.

score 0 · Accepted Answer

「無名関数の考え方が間違っているようです。それはランタイムの作成だけでなく、スコープに関するものでもあります。次の Scheme マクロを検討してください。

(define-syntax lambdarec
  (syntax-rules ()
    ((lambdarec (tag . params) . body)
     ((lambda ()
       (define (tag . params) . body)
        tag)))))

そのような：

(lambdarec (f n) (if (<= n 0) 1 (* n (f (- n 1)))))

たとえば、次のように使用できる真の無名再帰階乗関数に評価します。

(let ;no letrec used
    ((factorial (lambdarec (f n) (if (<= n 0) 1 (* n (f (- n 1)))))))
  (factorial 4)) ; ===> 24

ただし、匿名にする本当の理由は、私がそうする場合：

((lambdarec (f n) (if (<= n 0) 1 (* n (f (- n 1))))) 4)

関数は後でメモリからクリアされ、スコープがないため、次のようになります。

(f 4)

エラーを通知するか、以前に f がバインドされていたものにバインドされます。

Haskell では、同じことを達成するアドホックな方法は次のようになります。

\n -> let fac x = if x<2 then 1 else fac (x-1) * x
    in fac n

違いは、この関数にはスコープがないことです。使用しない場合、Haskell が Lazy であるため、効果はコードの空の行と同じであり、C コードと同じ効果があるため、真にリテラルです。

3;

リテラル番号。そしてすぐに使っても消えてしまいます。これがリテラル関数の目的であり、実行時の作成自体ではありません。

score 0 · Accepted Answer

Clojure はfn、この目的のために特別にオプションの名前を取るので、それを行うことができます (名前は定義スコープをエスケープしません):

> (def fac (fn self [n] (if (< n 2) 1 (* n (self (dec n))))))
#'sandbox17083/fac
> (fac 5)
120
> self
java.lang.RuntimeException: Unable to resolve symbol: self in this context

たまたま末尾再帰である場合recurは、はるかに効率的な方法です。

> (def fac (fn [n] (loop [count n result 1]
                     (if (zero? count)
                       result
                       (recur (dec count) (* result count))))))

recursion - *再帰的*関数リテラル/無名関数をサポートする言語は?

16 に答える 16

Related

Reference

recursion - 再帰的関数リテラル/無名関数をサポートする言語は?