foldrでタプルを渡す場合の注意

foldrはその定義から、無限リストに対しても使うことができますが、時には注意が必要です。たとえば、タプルを受け渡すような場合には注意しないと、無限リストに対して止まらなくなります。

Stackoverflowで見掛けたリストを2本に分けるコード http://stackoverflow.com/a/7412022 で、ちょうどそのパターンにはまりましたので、簡単なメモとして残します。

--問題あり。記事の最後を見ること。
foldr (\x (ys, zs) -> (x : zs, ys)) ([], [])

エレガントですが、実は問題をはらんでいて、無限のリストに対して使うと止まらなくなります。以下、順を追って説明します。

まず、有限のリストで簡単に動作をチェックしてみます。

ghci> foldr (\x (ys, zs) -> (x : zs, ys)) ([], []) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
--> ([1,3,5,7,9],[2,4,6,8,10])

リストが2本に分けられているのがわかります。これの先頭だけを取り出してみます。

ghci> head . fst $ foldr (\x (ys, zs) -> (x : zs, ys)) ([], []) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
--> 1

再帰の浅い部分しか評価されないはずですからfoldrの2番目の引数はundefinedでもかまわないはずです。が...

ghci> head . fst $ foldr (\x (ys, zs) -> (x : zs, ys)) undefined [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
*** Exception: Prelude.undefined

のようにundefinedの評価が起きてしまいます。

ここで (undefined, undefined) にすると、問題なく通ります。

ghci> head . fst $ foldr (\x (ys, zs) -> (x : zs, ys)) (undefined, undefined) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
--> 1

何が起きているのかというと、foldrに渡している関数のパターンマッチ (ys, zs) により、foldrの再帰が深くなるほうに向けて評価が進んでしまって（WHNFを求めようとしてしまって）います。ここでfoldrの返す値にはconsのように遅延する要素が無く、どこまでも直接タプルがありますので、最後まで進んでしまいます。結局最後に (undefined, undefined) があればタプルが確定して止まって先に進みますが、undefinedの場合は値全部がundefinedになってしまう、という差になっています。

無限リストに対して試してみます。無限リストでは基底パターンには入りませんから、2番目の引数はundefinedにします。

> head . fst $ foldr (\x (ys, zs) -> (x : zs, ys)) undefined [1, 2 ..]
^CInterrupted.

止まりませんので、メモリを大食いしてスラッシングを起こしたりなどする前にコントロールCなどで止めましょう。

問題を修正するには、関数のパターンマッチにチルダ ~ を付けて遅延パターンにしてやります。

--問題修正版。チルダに注意
foldr (\x ~(ys, zs) -> (x : zs, ys)) ([], [])

これで問題なく動くようになります。

ghci> head . fst $ foldr (\x ~(ys, zs) -> (x : zs, ys)) undefined [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
--> 1
ghci> head . fst $ foldr (\x ~(ys, zs) -> (x : zs, ys)) undefined [1, 2 ..]
--> 1

以上、foldrでタプルを受け渡す場合に必要な注意についてまとめました。