関数型プログラミング言語Haskell
■ このスレッドは過去ログ倉庫に格納されています
0788石敢當
NGNG簡単に言うと、Haskellが採用している評価順序ではデメリットしか
ないような場合には評価順序を変更して効率を良くしよう、ということ
です。例えば、foldlを使って1から3までの和を求めようとすると、
foldl (+) 0 [1,2,3]
= foldl (+) (0 + 1) [2,3]
= foldl (+) ((0 + 1) + 2) [3]
= foldl (+) (((0 + 1) + 2) + 3) []
= (((0 + 1) + 2) + 3) = ...
このように、途中の加算の式をそのまま引きずっています。
そんなことをせずに、
foldl (+) 0 [1,2,3]
= foldl (+) (0 + 1) [2,3] = foldl (+) 1 [2,3]
= foldl (+) (1 + 2) [3] = fold (+) 3 [3]
= foldl (+) (3 + 3) [] = fold (+) 6 [] = 6
としたほうが、明らかに効率が良さそうです。
Preludeのfoldl'の定義で使用されている($!) :: (a -> b) -> a -> b
は、まず第2引数の簡約化を行ってから関数適用を行うので、
まさに上に書いたような状況が得られるわけです。
Haskell Reportの 「6.2 Strict Evaluation」にこのあたりのことに
関する説明が少しあります。また、IFP本(>>277)では
「7.5 Controlling space」にやや詳しい説明があります。
■ このスレッドは過去ログ倉庫に格納されています