他人のHaskell日記

■ 今思いついた造語「length汚染」

関数の定義内に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は大丈夫。

■ 型データコンストラクタは関数の様に扱える.

http://haskell.g.hatena.ne.jp/hyuki/20060615/type

最初に見たときは「isPrefixOf xs ys = and $ zipWith (==) xs ys」

でいけるんじゃないかと思ったけど、こうするとisPrefixOfは可換になるので

"abc" "abcdefg"の場合だけじゃなくて "abcdefg" "abc"でもTrueになっちゃう。

だから、この方法じゃダメだと思って諦めた。

で、さっき結城さんのサイトをみたら、いい方法が。

isPrefixOf xs ys = and $ zipWith (==) (map Just xs) (map Just ys ++ repeat Nothing)

以下、自分の頭の中での整理。

この問題を解決するアイデア

「ysのうしろにゴニョゴニョとリストを付け加えれば良い」

そうすればlength xs >= length ysのケースでも問題は発生しない。

そのリストのサイズはどうすればいいのか

リストのサイズは「ysとxsの大きさの差」以上であればどれだけ大きくても良い。

「ysがxsと比べてどれだけ短いか」は未知なので

• length xs - length ysを計算して、そのサイズのリストを生成する.
• 無限リストを生成する.

のいずれかかが考えられる。

「どれだけ大きくても良い」場合のHaskellでの素直な実装は無限リストだと思う。

そもそもlength汚染恐怖症の人間はlengthがあると不安になる。

そのリストの要素は何が相応しいのか。

xs="abcdefg",ys="abc"の場合について考える.

このとき(xs `isPrefixOf` ys)はFalseになって欲しい

しかし仮にysに追加された配列が"defg....."だとすると,これはTrueになってしまう。

このような事が起こらないように、追加するリストの要素を決めなければならない。

追加される要素は、xsに出てくる要素とカブってはいけない。

• xsでは出てこない「文字」を使う

xsで使われない文字集合は未知である

なので、xsで使われていない文字を求めるような関数が必要となる。

その関数が何をしているのか,分かりにくい。

• 別の型にはめこんで「文字」と「無」を分ける

「無」は「文字」にマッチすることは無いので、確実に問題を回避できる。

具体的にはMaybeの型データコンストラクタを使い[Just 文字]と[Nothing]を分ける。

型による意味の分離は,Haskellのようなstrongy-typedな言語と親和性が高く

コードの意味も理解しやすくなる。

追記

データコンストラクタと書かずに型コンストラクタと書いていましたので訂正しました。

■ ひらめき動物

「ひらめき」とは、それ自体が快楽である。

(しかもどれだけ「ひらめいて」も体の害にはならない^^)

しかし、あなたの「ひらめき」は

他の人にとっては凡俗な物かもしれないし、

あるいは全く役に立たないかもしれない。

ただ、その「ひらめき」が、誰かの元に届いて

その人を「ひらめ」かせるかもしれない。

やっぱり、その人も「ひらめき」も、

他の人の役に立たないかもしれない。

ただ、その人が「ひらめ」いたとき、

その瞬間その人は気持ち良かったはずなのだ

「ひらめき」は快楽の郵便である。

「役に立つ」ということは副作用(side-effect)である。

■ Haskell(λ星人)の本能？

Haskellに欲望があるとすれば、それはきっとパターンマッチだ

パターンマッチを成功した瞬間にのみHaskellは快感を得るのだ。

証拠

遅延評価

パターンマッチを成功させるために、怠惰(lazy)なHaskellは

必要にかられて嫌々引数の簡約を行う。必要がなければ絶対にしない。

迷路をゴールから辿る子供のように、外側の関数から簡約し、

パターンマッチが成功した時点で引数の評価をしなくなる

λ「引数を評価しろって？やだよ・・え、パターンマッチさせてくれるの？やるやる！」

型推論と型安全

パターンマッチが成功する可能性が無いなら最初から受け付けない。

面倒な事はしない。絶対にしない。

λ「パターンマッチさせてくれないなら何もしてやんないもんね！」