他人のHaskell日記 RSSフィード

Haskell初心者が、リハビリがてらに「ふつける」と「入門Haskell」片手に、試行錯誤するサイト。

2006-06-16

今思いついた造語length汚染 今思いついた造語「length汚染」 - 他人のHaskell日記 を含むブックマーク

関数の定義内にlengthを使用したためストリーム無限リスト)が扱えなくなってしまうこと。

また、その関数を更に他の関数を使っていると汚染は拡大する。

Haskellのような"call-by-need"な言語では,

リスト関数は可能な限りストリームを扱えるように設計すべきだが

lengthのようなリストの終端をeagerするリストの末尾に関してstrictな関数を使うと、

無限リストが扱えなくなったり、末尾まで読み込むためにメモリを大量に浪費したり、

IOからの入力が終わるまで何も動作しなかったりする。

無限リスト理論的には扱える関数」がlength汚染に侵されると、

その汚染口から微少の目に見えないλ星人が大量に発生し、いつか悪さをやらかすかもしれない。

追記

eagerという言い回しはまずいようなので訂正しました。

追記2

コメント欄でlast汚染やfoldl汚染について教えて貰う。

lastがダメなのは直感的に分かるけどfoldlがダメなのは意識してなかった・・。

concat'をfoldlを使って自前で定義してPreludeと比較してダメっぷりを検証してみました。

concat' xs =  foldl (++) [] xs

*Main> take 13 $ concat  $ map (\x -> [x]) [1..]         --Prelude版
[1,2,3,4,5,6,7,8,9,10,11,12,13]

*Main> take 13 $ concat' $ map (\x -> [x]) [1..]         --foldl定義版
GHC's heap exhausted: current limit is 268435456 bytes;
Use the `-M<size>' option to increase the total heap size.

落ちた・・。これは気をつけなければ・・。

concat'' xs =  foldr (++) [] xs

*Main> take 10 $ concat'' $ map (\x -> [x]) [1..]
[1,2,3,4,5,6,7,8,9,10]

foldrは大丈夫。

takatohtakatoh2006/06/16 13:46last汚染というのもあるかも。foldlとかでリストを作るときに直前の要素がほしいことってあるんですよね。