関数型プログラムで定義される関数f,gの合成関数を計算するとき、fの計算は gの計算のための中間結果となり、この中間結果がリストや木構造のような場合 には効率が悪くなるという問題がある。 中間結果が生成される場合に、中間結果が生成されず効率の良いプロ グラムに変換する手法としてDeforestationが提案されている。この手法は最悪 でも効率が悪くはならない。Deforestationで は、合成関数と同じ計算を行う効率のよい新しい関数を生成することで変換を行っ ている。 しかし、Deforestationは関数定義の第1引数のみでパターン照合を行うプログラムに しか適用できないという問題点がある。 本研究では、Deforestationの入力プログラムを、第1引数でのパターン照合プロ グラムからn箇所でパターン照合を行うプログラムに拡張した変換法である n-Deforestationを提案し、その正当性を証明する。本変換は入力プログラム に対して段階的な変換を行い最終的に効率化されたプログラムを出力する。まず、 入力プログラムに対してパターン照合が第1引数のみで行われるプログラムへの 等価変換を行い、得られたプログラムでの合成関数に対してDeforestationを適 用し、さらに効率をよくするためにパターン照合を複数箇所で行うプログラムへ の変換を行う。上記の2つの部分的な変換のそれぞれについて変換の前後で関数 が等価であることを証明し、n-Deforestationの正当性を証明する。また n-Deforestationが生成するプログラムの効率に関する性質を示す。