無名再帰
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/04/07 17:11 UTC 版)
無名再帰（むめいさいき、英: anonymous recursion, nameless recursion）とは、無名関数において再帰を行うことである。無名関数は名前を持たないため自己を呼び出すために特別の工夫が必要である。無名再帰は、関数定義では関数自身には名前を付けないが、関数の引数には名前を付けて良い、という制約条件で行う再帰。ラムダ計算において関数はそのような制約条件がある。
不動点コンビネータによる方法
Haskell では以下のように書く。fix が不動点コンビネータ。ラムダ式で引数 f を余分に持っておき、f を自分自身として参照するように記述する。すると、無名再帰となる。
fix (\f n -> if n == 0 then 1 else n * f(n - 1)) 5 == 120
不動点コンビネータを名前付き関数の再帰を使わずに実装する方法
値呼びYコンビネータのZコンビネータ（下記関数Z）を使用して以下のようにも書ける[1]。名前付き関数 Z の実装において内部から Z を再帰呼び出していない。
Python
Z = lambda f: (lambda x: f(lambda *y: x(x)(*y)))(lambda x: f(lambda *y: x(x)(*y)))
# 利用方法（5の階乗の計算）
Z(lambda f: lambda n: 1 if n == 0 else n * f(n - 1))(5)
不動点コンビネータは Python の代入式を使った (f := lambda n: 1 if n == 0 else n * f(n - 1))(5) と同様である。
JavaScript (ECMAScript 2015)
Z = f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y)))
// 利用方法（5の階乗の計算）
Z(f => n => n == 0 ? 1 : n * f(n - 1))(5)
Ruby
Z = ->(f) { ->(x) { f[->(y) { x[x][y] }] }[->(x) { f[->(y) { x[x][y] }] }] }
# 利用方法（5の階乗の計算）
Z[->(f) { ->(n) { n == 0 ? 1 : n * f[n - 1] } }][5]
TypeScript
Zコンビネータに型をふるには再帰型が必要である。下記の type X が再帰型である。
function Z<A, B>(f: (_: (_: A) => B) => (_: A) => B) {
type X = (_: X) => (_: A) => B;
return ((x: X) => f((y: A) => x(x)(y)))((x: X) => f((y: A) => x(x)(y)));
}
// 利用方法（5の階乗の計算）
Z<number, number>(f => n => n === 0 ? 1 : n * f(n - 1))(5);
Java
Java で再帰型を利用するには名前付きクラスやインターフェースを使用する必要がある。型 X を表現するのに名前付きインターフェースを使用する。
import java.util.function.Function;
interface X<A, B> {
Function<A, B> apply(X<A, B> x);
}
static <A, B> Function<A, B> Z(Function<Function<A, B>, Function<A, B>> f) {
return ((X<A, B>) (x -> f.apply(y -> x.apply(x).apply(y)))).apply(x -> f.apply(y -> x.apply(x).apply(y)));
}
// 利用方法（5の階乗の計算）
Z((Function<Integer, Integer> f) -> (Integer n) -> n == 0 ? 1 : n * f.apply(n - 1)).apply(5);
不動点コンビネータを名前付き関数の再帰を使って実装する方法
不動点コンビネータの fix は無名関数だけで実装すると複雑だが、名前付き関数の再帰を使うならば簡単に実装できる。再帰回数が多いとスタックオーバーフローすることがあるが、その際はトランポリン化すれば良い。
Python
カリー化あり。
def fix(f):
return lambda *x: f(fix(f))(*x)
# 利用方法（5の階乗の計算）
fix(lambda f: lambda n: 1 if n == 0 else n * f(n - 1))(5)
カリー化なし。
def fix(f, *x):
return f(lambda *y: fix(f, *y), *x)
# 利用方法（5の階乗の計算）
fix(lambda f, n: 1 if n == 0 else n * f(n - 1), 5)
Scala
複数パラメータリスト（カリー化）を使用。
def fix[A, B](f: (A => B) => A => B)(a: A): B = f(fix(f))(a)
// 利用方法（5の階乗の計算）
fix((f: Int => Int) => (n: Int) => if (n == 0) 1 else n * f(n - 1))(5)
それをトランポリン化。
import scala.util.control.TailCalls._
def fix[A, B](f: (A => TailRec[B]) => A => TailRec[B])(a: A): TailRec[B] = f(a2 => tailcall(fix(f)(a2)))(a)
// 利用方法（0～100000の整数の和）
fix((f: Int => TailRec[Long]) => (n: Int) => if (n == 0) done(0L) else f(n - 1).map(s => s + n))(100000).result
名前付きラムダ式
多くのプログラミング言語ではラムダ式には名前が付けられないが、名前付きラムダ式を作れたり、変数に代入すれば再帰できるプログラミング言語もある。変数に代入する方法は、そのプログラミング言語が外の変数を参照で束縛することが必要であり、値で束縛すると初期化前なので再帰ができない。
Clojure
ラムダ式に名前が付けられる。
((fn f [n] (if (== n 0) 1 (* n (f (- n 1))))) 5)
なお、不動点コンビネータで実現できるという指摘はあったものの[2]、1960年の最初のバージョンの LISP I では (LABEL 名前 ラムダ式) という構文で再帰可能な名前付きラムダ式が作成できた[3]。
ECMAScript
アロー関数は名前を付けられないが、ECMAScript 3 以降[4]の function は再帰できるように名前を付けられる。
(function f(n) { return n == 0 ? 1 : n * f(n - 1); })(5);
アロー関数の場合は変数に代入すれば再帰が可能。
(f = n => n == 0 ? 1 : n * f(n - 1))(5)
Python
Python 3.8 で導入された代入式を使用すれば再帰が可能。
(f := lambda n: 1 if n == 0 else n * f(n - 1))(5)
Ruby
変数に代入する事でラムダ式も再帰が可能。
(f = -> (n) { n.zero? ? 1 : n * f.(n - 1) }).(5)
C++
外のローカル変数 f の参照を [&f] で束縛することができるので、これを使用して再帰ができる。[f] だと初期化前なので使用することができなく、参照で束縛することで f にラムダ式を代入後の値を使用できる。
#include <functional>
std::function<int(int)> f = [&f](int n) -> int { return (n == 0) ? 1 : n * f(n - 1); };
C#
C++ と似た手法であるが、C# の場合は、変数宣言を分離すると f の参照を束縛できる。これを1行で書くとコンパイルエラーになる。
Func<int, int> f = null!; // null免除演算子で警告を抑止
(f = n => n == 0 ? 1 : n * f(n - 1))(5);
Kotlin
C# と同じく変数宣言を分離し、lateinit を付けることで f の参照を束縛できる。
lateinit var f: (Int) -> Int
f = { n -> if (n == 0) 1 else n * f(n - 1) }
Java
C++ や C# とは異なり Java は外のローカル変数を参照で束縛することができないので、配列を導入すると参照可能になる。
import java.util.function.Function;
Function<Integer, Integer>[] ary = new Function[1];
Function<Integer, Integer> f = ary[0] = n -> n == 0 ? 1 : n * ary[0].apply(n - 1);
フィールドの場合は、this.f とするとコンパイルが可能。this. を付けないと「初期化子内の自己参照」のエラーが出る。static フィールドの場合も Foo.f とする必要がある。
import java.util.function.Function;
class Foo {
Function<Integer, Integer> f = n -> n == 0 ? 1 : n * this.f.apply(n - 1);
}
関数の自己参照をサポートしている言語による方法
APL
APL, 言語では実行中の dfn を ∇ で参照できる。
{0=⍵:1 ⋄ ⍵×∇ ⍵-1} 5
120
{0=⍵:1 ⋄ ⍵×∇ ⍵-1}¨ ⍳10 ⍝ applied to each element of 0 to 9
1 1 2 6 24 120 720 5040 40320 362880
Forth
Forth ではワードの定義中では、名前を用いて自分自身を参照できないため、RECURSE というワードで自分自身を参照する。
JavaScript
JavaScript では以下のように書ける[5]。arguments.callee で自分自身を参照する。なお、ECMAScript 5 以降の strict mode では arguments.callee は使用できない[4]。
(function(n) { return n == 0 ? 1 : n * arguments.callee(n - 1) })(5) == 120
Perl
Perl でも v5.16 から同様に、__SUB__ というリテラル（厳密には組込み関数）が、実行中のサブルーチン自身へのリファレンスを返し、無名再帰に利用できるようになった。
#!/usr/bin/perl
use feature qw/current_sub say/;
say sub {
my $x = shift;
$x > 0
? $x * __SUB__->( $x - 1 )
: 1;
}->(5);
R
R言語 では Recall で関数の自己参照ができる。
sapply(0:5, function(n) {
if (n == 0) return(1)
n * Recall(n - 1)
})
参照
- ^ Y コンビネータって何？ - IT戦記
- ^ “The implementation of LISP”. www-formal.stanford.edu. 2024年4月8日閲覧。
- ^ “McCarthy et al. LISP I Programmer's Manual. — Software Preservation Group”. softwarepreservation.org. 2024年4月8日閲覧。
- ^ a b “arguments.callee - JavaScript”. 2024年4月7日閲覧。
- ^ GNU RとJavaScriptの無名再帰をやってみた - NoiseFactory
- 無名再帰のページへのリンク
