Concurrent Clean : 再帰データ構造の生成

プログラミング

たとえば、整数のリストを受け取って、奇数だけのリストを返す関数は、

oddList :: [Int] -> [Int]
oddList []     = []
oddList [i:ir] | isOdd i = [i:oddList ir]
                         = oddList ir

と定義しますが、これを、

oddList :: [Int] -> [Int]
oddList []     = []
oddList [i:ir] | isOdd i # ol = oddList ir
                         = [i:ol]
                         = oddList ir

としても効率に差はないです。（ここでの # は let と同じ効果です）
しかし、奇数のリストと偶数のリストの両方を返す次の関数は、

oddEvenList :: [Int] -> ([Int], [Int])
oddEvenList []     = ([],[])
oddEvenList [i:ir] # (ol,el) = oddEvenList ir
                   | isOdd i
                       = ([i:ol],el)
                       = (ol,[i:el])

とした場合、タプル生成と破棄のコストがかかってしまって、すこし面白くありません。
なので、これを、

::*OddEven = { ol :: [Int], el :: [Int] }
oddEvenList :: [Int] -> *OddEven
oddEvenList []     = { ol = [], el = [] }
oddEvenList [i:ir] # (oe=:{OddEven| ol, el}) = oddEvenList ir
                   | isOdd i
                       = {OddEven| oe & ol = [i:ol]}
                       = {OddEven| oe & el = [i:el]}

というように一意性を使ってやると、コンパイル時GCが行われて、実行時にレコード生成と破棄のコストがかからなくって、少し効率的になるんじゃないかと思っています。
というわけで、これから実験します。

      • -

実験結果です。
レコードを使った方は、一意性型属性を付けたものと付けないものの２通り試してみましたが、同じABCコードを吐くことが分かりました。
最も大きな違いは、タプルを使った方は遅延評価され、レコードを使った方は正格評価されるという点でした。なので、次のように無限リストを渡すと、タプルの方は結果が出力されますが、レコードの方はStack overflow.になります。

Start = oddEvenList [0..]

レコードの方の実行内容を詳細に見ていくと、実行中にレコードを生成する処理は一度も入っていません。全て計算が終わった後に、最後にレコードを生成しています。この関数が小さい関数だからそういう最適化が可能なのか、一般的にそういう最適化がかかるのかは分かりませんが。
あと、ABCコード上での命令数は、タプルを使った方が、レコードを使った方より少ないです。アセンブリに変換後を見ても同じ傾向です。これは、遅延オブジェクトを作る方が、スタック上のオブジェクトを書き換えるよりも、見た目の命令数が少なくなるということではないかと思います。
結論として、有限の計算で終わる場合は、レコード型を使った方が効率的に実行できそうです。しかし、無限リストを取り扱うには、タプルを使わないとダメなようです。あと、一意性型属性は、ここでは全く差が生まれませんでしたが、関数が大きい場合や関数をエクスポートする場合を考えると、付けておく方が効率的になる可能性はあるとおもいます。*1

      • -

以上、Cleanのレコード型のバッドノウハウでした。

      • -

（追記：2006/05/22）この件、よく考えてみると、レコード型の方は、レコードの更新を使っているから、正格評価されるのは当然ですね。

*1:あくまでも、全要素が利用される場合は、ということです。その一部しか利用されないなら、遅延評価されるタプルを使う方が効率的になりえます。