- 著者
-
中野 圭介
- 雑誌
- 第54回プログラミング・シンポジウム予稿集
- 巻号頁・発行日
- vol.2013, pp.181-188, 2013-01-11
関数型プログラミングにおいて,リストを消費する関数 foldr および生成する関数 unfoldr は重要な役割を果たす.特に,入力を foldr によって消費し,出力を unfoldr によって生成するような関数はメタモルフィズムとよばれ,基数変換などに代表される或るデータ表現から別のデータ表現への変換を自然に定義することが可能である.Bird と Gibbons は,このメタモルフィズムに対し,入力を消費しながら出力を生成するようなストリーム処理として実装できるための条件を提示したが,自然数に対する基数変換には応用することができなかった.これは入力の桁を全て読み込まない限り,出力の桁を決定できないためで,彼らの提示した条件を満たしていない.これを解決するために著者が提案した手法が,ジグソーパズルを利用したメタモルフィズムの計算機構である.本稿では,グレイコードのような特別な記数法に対してこの機構を適用し,対応するジグソーモデルの導出方法を示す.