2015/04/01

関数型言語のリストと命令型言語のリスト

C++納品の案件で、プロトタイプ&アルゴリズム検証用にSchemeで実装してから C++に移植するってのをやってて、 std::listとSchemerが考える「リスト」の違いに改めて気づいた。 いやもちろんリストというデータ構造を利用してるという意味では同じなんだけど。

リストを不定長データの集合を扱うコンテナと考えるならstd::list的な もので十分だし、データの挿入位置についてこだわりがないなら可変長配列を持ってる 言語は既にたくさんあって、さらにそういったデータ構造に対するfindや map的な操作も標準で提供されることが多いから、 そっちの面から見たらSchemeでのリスト操作は比較的素直に命令型言語の 組み込みリスト型or可変長配列型に移植できそうに思えるんだけど。

Scheme(や他の関数型言語)のリストってのは、 「既にあるリストに変更を加えずに、新たな要素を低いコストで追加したリストを 得られる」ってのがかなり決定的に重要な性質で。

探索しながら結果を積み上げていって、失敗したら別の選択肢を試す、 なんてコードは、Schemeなら途中までの結果は既に掴んでるから 単に再試行すればいいだけなんだけど、std::listにpush しちゃってる場合は巻き戻さないとならない。 これはまあ、関数型風の書き方と命令型風の書き方のミスマッチと言っちゃえばそれで おしまいなんだけど、 案外、二つのスタイルの根本的な差を端的に示してるのかなとも感じた。

(なお、「SchemeとC++の両方で実装」というのは個人的には成功だった。 循環ありの有向グラフをいじりまくる案件だったので試行錯誤にSchemeの方が圧倒的に楽だったのと、 Scheme版でテストデータを生成してC++版を流して一致するかどうか見る、という形で C++版の実装バグを簡単に潰せたので。 もちろん同一アルゴリズムを使ってる以上、アルゴリズムのバグは別にテストしないとならないんだけど、 実装の問題とアルゴリズムの問題を確実に切り分けられるだけでものすごく助かった。)

Tags: Programming, Gauche, Scheme, C++