php

関数型 - Yコンビネータ

 
Yコンビネータのシナリオ:
  • Yコンビネータ(こんな感じのやつ → Y(F) = F(Y(F)) )を無心に写経する。
  • サンプルとして fact(10) を計算する。
  • 変数名としても関数名としても、fact の名を冠するものは登場しない。

関数型 - メモ化 Memoization

 

SICP Exercise 3.27.

メモ化のシナリオ:
  • 高階関数 memoize は、引数で渡された関数に対して、計算結果のキャッシング機能を追加する。
  • memoize の戻り値はキャッシング機能付きの関数で、これを変数 fib を通して使用する。
  • キャッシング機能によって、計算量の爆発が抑えられることを確認する。
  • 具体的には fib(1000) を計算する! これは、メモ化されていない fib(30) よりも遙かに速い。
  • 計算結果の桁数が200桁を越えるので、可能であれば多倍長整数を使用する。

関数の実行時間を計測するには?

 
  • 処理系で用意されている方法があるなら、それを使用する。
  • 無ければ、関数の実行時間を計測する関数 time を作成する。
  • 計測対象のサンプル関数として、フィボナッチ数を計算する fib を作成する。
  • 計測単位は、可能な限り秒(sec)とする。
  • 計測精度はミリ秒でもマイクロ秒でも構わない。

関数型 - イテレータ

 
イテレータのシナリオ:
  • 高階関数 myEach は、配列要素を1つ取り出すごとに、これを引数としてコールバックを行う。
  • 呼び出し側は、3の倍数を見つけたらプリントする。
  • myEach は、可能であれば組み込み型の拡張として実装する。 このとき継承は使わない。

処理系のインストール

 

記事で使用している処理系のインストール方法、 及びシェルの起動と終了について記載します。

関数型 - 無限リスト

 
無限リストのシナリオ:
  • 無限に続く奇数列 (1, 3, 5, 7, 9 ...)、odd を作成する。
  • 最初の10件を配列(リスト)に取り込む。

インストール - PHP 5.3

 

PHP 5.3.0beta2-dev も同様の方法でインストール出来ました(Fedora 10 を使用)。

2009-03-07

Fedora 9 に PHP 5.3.0α をインストールしました。 このバージョンでは、遂に「匿名関数」と「クロージャ」が実装されたということで、試したくなったのです。

PHPのインストール

インストール方法は UNIX/Linux の一般的な方法です。 インタラクティブシェルを使用するだけなので、configure のオプションには --with-readline だけを指定しました。 インストール先はデフォルトの /usr/local になります。

$ pwd
/usr/local/src
$ wget http://snaps.php.net/php5.3-200811111930.tar.bz2
$ tar xjf php5.3-200811111930.tar.bz2 
$ cd php5.3-200811111930
$ ./configure --with-readline           ← Interactive shell を有効に
$ make
$ sudo make install
$ make clean

PHPシェルの動作確認

動作確認については、次の記事を参照してください。

関数型プログラミング - 目次

 

これは、関数型プログラミングの記事をブック形式にまとめた集約エントリです。 難易度の低いものから高いものへと順にページをめくって行くことが出来ます。

関数型 - 有限リスト

 
有限リストのシナリオ:
  • 有限の奇数列 (1, 3, 5 .. 19) 、odd を作成する。
  • 可能であれば、 無限リストへの道筋となるような実装を行う。
  • 値を一気に配列(リスト)に取り込む。

関数型 - 再帰呼び出し

 
階乗の計算を、再帰呼び出しを使用して書く。
  • サンプル: 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800
  • いずれの処理系でも、非末尾再帰と末尾再帰の 2バージョンを作成する。 処理系によっては、末尾再帰で記述すると最適化される。
  • パターンマッチを使用できる処理系では、これを使用する。 そうでなければ if-else に準ずる構文を使用する。

関数型 - クロージャ

 
クロージャのシナリオ:
  • 高階関数 foo は、ラムダ関数を返す。
  • このラムダ関数は、環境(foo の引数 keyword、foo のローカル変数 page)を記憶している。
  • 呼び出し側は、変数 f1 と f2 を通して、キーワードに対する検索結果のページを次々に取り出すことができる。

関数型 - コールバック

 
コールバックのシナリオ:
  • 定形処理(x ** 2)を行う高階関数 foo を作成する。
  • 差分処理(x * 2)を行うラムダ関数を作成する。
  • 高階関数 foo は、ラムダ関数をコールバックしたあと、両者の和を求める。

関数型 - 写像 map

 
次の処理を、map関数を使用して書く。
  • 処理前: [1, 2, 3, 4, 5]
  • 処理後: [1, 4, 9, 16, 25] (各要素を2乗)

関数型 - ラムダ関数

 
次の計算を、ラムダ関数(匿名関数、無名関数)を使用して書く。
  • 2 * 3 = 6

関数型 - 畳み込み fold, reduce

 
次の2つの計算を、畳み込み関数を使用して書く。
  • 1 + 2 + 3 + 4 + 5 = 15
  • 1 * 2 * 3 * 4 * 5 = 120