読者です 読者をやめる 読者になる 読者になる

Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Zanmemo

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

高階関数と関数オブジェクトとラムダについての自分なりのメモ書き

近況

f:id:nisemono_san:20150714100817j:plain

正しく、そして簡単に書くことが、一番の壁だということを実感する。

概要

『関数プログラミング』という本の中においては、「関数そのものと関数を引数に適用したものを混合してはならない(p.9)」としている。というのは、「関数プログラミングにおいては、関数は値であり、ほかの値と対等のものである.とくに引数として関数に渡したり, 結果として返したりする. したがって, 関数と, 引数に関数を適用して得られる結果との区別に無頓着というわけにはゆかないのである.(p.10)」としている。

一般的に、「関数型言語」の特徴として、「関数オブジェクトが第一級(first-class-object)である」と言われる。ところが、「関数オブジェクトが第一級である」言語は、特に関数型言語と普通は言われないような言語でもある。だが、これらの区別が「関数型」という言葉を使わなくても、重要であることは間違いないので、今回は自分なりにその辺りについて考えたことをメモ書きしたいと思う。例によって、不正確な記述が多いと思われるので、それらは識者のツッコミ待ちをお願いしたいところである。

プログラムにおける関数オブジェクト

まず最初に、いきなり「関数適用」と「関数それ自体」という話に入る前に、具体的なコードを書いたほうが早いだろう。そこで具体的に「変数」に「関数オブジェクト 」を代入できるようなプログラミング言語を使いたいと思う。具体的には、それらの言語はPython、JavaScript、Scheme(Racket)の三種類に登場してもらいたい。

これら「関数それ自体」を利用する場合には、mapであったり、JavaScriptならcallbackの場合が多いように思われる。例えば、Pythonの場合は、次のようなコードを書くことが出来る:

plus_10 = lambda x: x + 10
list(map(plus_10, [1, 3, 5])) # => [11, 13, 15]

Python的には、lambda記法は、次のように使うことが出来る(ちなみに、このようにlambdaidentifierに代入することは、PEP-8では推奨されていない)。

def plus_one:
    return x + 10

list(map(plus_10, [1, 3, 5]))

また、JavaScriptでも、事情は同じである。JavaScriptは、プラグイン作成などに、関数オブジェクトが頻繁に代入される言語の一つであると思われる。

var plus_one = function(x) { return x + 10 };
[1, 3, 5].map(plus_one); // => [11, 13, 15]

Schemeでも同様に、次のように書ける:

(define plus_10 (lambda (x) (+ x 10))
(map plus_one '(1 3 5)) ;; => '(11 13 15)

関数それ自体と、関数適用を切り分ける

適切な表現はわからないけれど、このように考えると、「関数」というのは、ある変数に対して、「関数それ自体」が代入されているという風に、上記の言語では考えることができる。

実際に、これ自体も数学的に考えることは可能である。これが例の、いわゆる「ラムダ記法」というものである。ラムダ記法を暴力的かつ、いささか不正確に説明すると、{g(x) = t}という式(そして、この{t}を任意の式とする)で表現できるような関数があったとき、これを{g = \lambda_x.t}として表現することが出来るようにした記法である。

このような記法の何が嬉しいかというと、関数それ自体と、関数適用を分離し、関数を「名前」を使わず、その式だけを値として考えるようになり、また同時に「関数を返す関数」ということを考えることが出来る。

「関数を返す関数」のメリットというのは、具体的には、このブログの過去にも説明した通り、カリー化を作成し、部分適用で使いまわすことが出来る関数を作成することができるようになる。

もう少し、抽象的な話題を続けよう。関数が「値」として渡せるとするならば、「関数を利用するような関数」ということが考えられる。例えば、先ほどのソースコードの例のように、「関数が代入されている変数」を渡して、ある機能を実現させていた。これらのことを、「関数を扱う関数」として、「高階関数」と呼ばれる。

例として、関数適用を二度繰り返す関数というものを考えてみよう。これは、第一引数に関数を、第二引数に最初の初期値を与えるものだ。

{twice(f, x) = f(f(x))}

これに対して、ラムダを渡してみよう:

{twice( \lambda_x.x+10, 5) = ( \lambda_x.x + 10 )( ( \lambda_x.x + 10 )(5) )  = 25 }

というような展開として考えることが可能である。このように、関数自体に名前は必要がなく、関数それ自体を使うことが可能になる。同様のことをJavaScriptで行いたければ、次のようなコードが書けるだろう:

function twice(f, x) { return f(f(x)); };
twice(function(x) { return x + 10 }, 5);

関数を返す関数

さて、ここでちょっとだけ考えたいことがある。ラムダ記法によって、関数を返すような関数というのを記述することが可能になるということである。例えば、先ほどのtwice関数に対して、初期値だけを与えるための関数twice_fを考えてみよう:

{twicef(f) = \lambda_x.f(f(x))}

このとき、例えば{twicef(\lambda_x.x+10)}とした場合のコードで書くとするならば:

function twicef(f){ return function(x) { return f(f(x)); }; };
twicef(function(x) { return x + 10 })(5);

ということになる。

まとめ

ということで、高階関数とラムダについての話を、自分なりに理解したところで、説明をしてみた。例によって不正確な説明がある部分も多いと思うので、是非ツッコミをお願いしたいです。

参考文献

計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)

計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)

詳しい話を読みたければ、こっちを読んだほうがいいだろう。

論理と計算のしくみ

論理と計算のしくみ

こちらは平坦でわかりやすかい

関数プログラミング

関数プログラミング

最初に引用したもの。Mirandaというのが時代を感じさせる。

あわせて読みたい