他人のHaskell日記

■ 完全数

http://d.hatena.ne.jp/rubyco/20060620/perfect

コード

定義通りのナイーブな実装。

perfect  = [ n | n <-[1..] , n == (sum [ k | k<-[1..n-1],n`mod`k == 0])]

実行結果

*Main> take 3 $ perfect
[6,28,496]

4つ目を求めようとすると凄く遅い。やっぱり素因数分解が必要か。

■ やばい、今日の日記凄く長い。

しかも、気が付けばもうこんな時間。しなきゃならないことたくさんあるのに。

毎日のように質の高いブログ書いている人は時間の確保どうしているんだろう。

■ Prelude車輪再開発事業従事者へのQuickCheckの勧め。

quickCheckでsameness check

私を含めHaskellの初学者はHaskellへの理解を深めるためにPreludeの関数を自作している人が多いように思います。

しかし、その自作した関数・・本当にPreludeの関数と同じなのでしょうか？

それを確かめるためにQuickCheckが使えるのではないか、というのがこの記事の趣旨です。

やってみる

とりあえずtake関数を自作してみます

take' 0 _ = []
take' n (x:xs) = x:take' (n-1) xs

これでいいかな・・実行してみよう。

*Main> take 3 [1..6]
[1,2,3]
*Main> take' 3 [1..6]
[1,2,3]
*Main> take 0 [3..8]
[]
*Main> take' 0 [3..8]
[]

よしよし動いたぞ！Prelude関数と一緒だ！

ほんとに？？

ではでは、テスト用関数（特性）を書いてみます。

QuickCheckのインポートも忘れずに。

import Test.QuickCheck

take' 0 _ = []
take' n (x:xs) = x:take' (n-1) xs

prop_take :: Int -> [Int] -> Bool     --型宣言重要。型が多層型になってたら、テストデータを生成出来ない。
prop_take n xs = (take n xs == take' n xs)

さあquickCheckだ！

*Main> quickCheck prop_take
Falsifiable, after 0 tests:
-1
[-2,-1]

残念！不合格！

*Main> take (-1) [-2,-1]
[]
*Main> take' (-1) [-2,-1]
[-2,-1*** Exception: c:/cygwin/home/25.hs:(3,0)-(4,32): Non-exhaustive patterns in function take'

確かに挙動が違います。

第一引数の値が負になるケースを考えていなかったのがまずかったようです。

書き換えます！

import Test.QuickCheck

take' n _ | n <= 0 =  []                 --負の数に対応
take' n (x:xs) = x:take' (n-1) xs

prop_take :: Int -> [Int] -> Bool
prop_take n xs = (take n xs == take' n xs)

実行

*Main> take' (-1) [-2,-1]
[]

よし！じゃあ再テストだ！

*Main> quickCheck prop_take
*** Exception: c:/cygwin/home/25.hs:(3,0)-(4,32): Non-exhaustive patterns in function take'

な、何が・・

例外(Exception)が起きたときは「なにはともあれverboseCheck」が基本です。

*Main> verboseCheck prop_take
0:
-1
[]
1:
1
[2,0]
2:
1
[-1]
3:
3
[4,3,1]
4:
3
[1]
*** Exception: c:/cygwin/home/25.hs:(3,0)-(4,32): Non-exhaustive patterns in function take'

むむむ

*Main> take 3 [1]
[1]
*Main> take' 3 [1]
[1*** Exception: c:/cygwin/home/25.hs:(3,0)-(4,32): Non-exhaustive patterns in function take'

なるほど。第一引数の値が、リストのサイズより大きかったときに

空リストがパターンマッチが成功せず、エラーが発生しているのですね。

パターンマッチを追加しましょう！

import Test.QuickCheck

take' n _ | n <= 0 =  []
take' n [] = []                         --追加：空リストになったらそれ以上読まない！
take' n (x:xs) = x:take' (n-1) xs

prop_take :: Int -> [Int] -> Bool
prop_take n xs = (take n xs == take' n xs)

さてどうだ？

*Main> take' 3 [1]
[1]
*Main> quickCheck prop_take
OK, passed 100 tests.

テスト合格！でけた！

　汚染は検知出来ず。

こんな風に大変便利なquickCheckですが、上に挙げた手法では問題があります。

たとえば次のコードの場合

import Test.QuickCheck

take' n _ | n <= 0 =  []
--take' n [] = []
take' n xs | length xs < n = xs        --　変更。恐怖のアイツがいます
take' n (x:xs) = x:take' (n-1) xs

prop_take :: Int -> [Int] -> Bool
prop_take n xs = (take n xs == take' n xs)

実行してみると

*Main> quickCheck prop_take
OK, passed 100 tests.

テストに合格します。

でも実は無限リストを与えると・・

*Main> take 3 [1..]
[1,2,3]
*Main> take' 3 [1..]
GHC's heap exhausted: current limit is 268435456 bytes;
Use the `-M<size>' option to increase the total heap size.

自作関数版はlength汚染にかかっているので終了しちゃいますが、

Preludeのtakeの方は問題なく処理します。つまり挙動が違うわけです。

どうやらリスト型に対するデフォルトのテストデータ生成機には無限リストが含まれていないようです。

（テストデータ生成機を自作すれば問題無し？）

■ QuickCheckオンラインマニュアル部分訳

写経がてら訳してみました。

英語不得手なので間違っているかも・・。

http://www.cs.chalmers.se/~rjmh/QuickCheck/manual.html

QuickCheckって何？

QuickCheckはHaskellのプログラムを自動的にテストするツールです。

プログラマはプログラムの内部で満たされなくてはならない特性

（例えば、任意の値の絶対値は常に０より大きい、等）を与えることで仕様を定義します。

そうするとQuickCheckは、ランダムに生成された様々なテストケースについて、

その特性が本当に常に保たれているのかテストします。

仕様はHaskellで表現します。

そのためにQuickcheckライブラリで宣言されているコンビネータを使います。

QuickCheckはコンビネータを使って特性を宣言し、テストデータの分布を観察し、テストデータの生成機を定義します。

簡単な例

特性は次のように宣言します。

prop_RevRev xs = reverse (reverse xs) == xs
  where types = xs::[Int]

この特性が満たされているかチェックするために、QuickCheckを実行します。

Main> quickCheck prop_RevRev
OK, passed 100 tests.

特性が満たされなかったとき、QuickCheckは反例を表示します。

例えば、次のように定義してみます。

prop_RevId xs = reverse xs == xs
  where types = xs::[Int]

さて、どうなるか見てみましょう

Main> quickCheck prop_RevId
Falsifiable, after 1 tests:
[-3,15]

Quickcheckを使おう

Quickcheckを使うにはモジュール（ QuickCheck.hs）,をダウンロードしなければなりません。

なるべく スクリプト（ quickCheck）もダウンロードした方がよいでしょう。

（訳注：GHCには標準付属している事を確認.import Test.QuickCheck)

定義やテストデータ生成機を含んだ全てモジュールにたいしてquickCheckモジュールをインポートしましょう。

特性をテストするには定義されたモジュールをHugsに読み込んだのちに、次のようにquickCheckを呼びます。

quickCheck <特性名>

あるいはスクリプトを実行させてもいいでしょう。

 > quickCheck <オプション> <ファイル名>

これで与えられたモジュールの中で定義された全ての特性がチェックされます。

コマンドラインのオプションはHugsのオプションと同じ物を与えることが出来ます。

特性をチェックするためにHugsを仕様する必要はありません。

どんなHaskell98の実装であっても十分です。

しかしながら, quickCheck スクリプトはシステムにHugsがインストールされていることを前提に動きます

だからrunhugsの場所を指定するためにスクリプトを編集する必要はないと思います

何がテストされているかどうすれば分かるの？

バージョンによってはHugsは、式を評価する前に、その式を表示します。

これなら、どの特性がテストされていてどんな特性が満たされてないのかわかりますよね。

もし、Hugsがそのようなことをしないバージョンをお使いなら、quickCheckに+namesフラグを与えましょう

 > quickCheck +names <オプション> <ファイル名>

こうすれば全ての特性の名前をテスト前に表示します

テストがループしたりエラーに遭遇したらどうすればいいの

こんなケースでは、特性が満たされないことを私たちは知っていますが

Quickcheckは反例を表示することはありません。

こんな場合のための他のテストの関数が用意されています。

これを使ってテストをやりなおしましょう。

verboseCheck <property-name>

これで、テストを実行する前に毎回テストしようとしているケースが何なのか表示します。

エラーが発生したりループに陥る前に最後に表示されたケースこそが、反例になります。

特性

特性はHaskellの関数の定義として記述されます。関数の名前はprop_から始まっている必要があります。

特性は、そのパラメータがなんであっても定量的でなければありません。だから

prop_RevRev xs = reverse (reverse xs) == xs
  where types = xs::[Int]

この場合は、等式は全てのリストxsについて成り立たなければなりません。 . Technical note.

特性は単相型でなければいけません。

多層型の特性は上記の例のように、特定の型に制約されなければ、テストには使えません。

次のようにwhere節の中で引数の型を明言するのが気軽でしょう。

  where types = (x1 :: t1, x2 :: t2, ...)

注：typesは何か意味を持ったキーワードではありません。

x1やx2の型を制約するための便利な場所を提供するための単なるローカルな意味の無い関数宣言に過ぎません。

特性が返す値の型は普通Boolになるでしょう。あるいは以下に述べる他のコンビネータを使って定義すれば話は別です。

条件付き特性

特性は次のような形を取れます。

	<条件式> ==> <特性>

例えば

ordered xs = and (zipWith (<=) xs (drop 1 xs))
insert x xs = takeWhile (<x) xs++[x]++dropWhile (<x) xs

prop_Insert x xs = ordered xs ==> ordered (insert x xs)
  where types = x::Int

「条件式が満たされるときは必ず、==>の後の特性も満たされる」という特性を意味します。

条件式を満たさないテストケースは予め捨てられます。

テストケースの生成は、条件式を満たすケースが１００個見つかるか、

テストケースの生成の試行回数が全体の上限に達したときに終了します。

(これは、条件式が満たされないときにループに陥ることを避けるためです。).

この場合、次のようなメッセージが表示されます。

Arguments exhausted after 97 tests.

これは「97のテストケースが 見つかり、特性はその97個のケースにおいて保たれていた」ことを示しています。

定量的特性

特性は次のような形をとれます。

	forAll <生成機> $ \<パターン> -> <特性>

例えば

prop_Insert2 x = forAll orderedList $ \xs -> ordered (insert x xs)
  where types = x::Int 

forAllの最初の引数はテストデータ生成機です。それぞれの型に応じたデフォルトのテストデータ生成機を用いる代わりに、

自作のテストデータ生成機を与えることでテストデータの分布をコントロールすることが出来ます。

例えば、整列済リストを産み出す自作のテストデータ生成機を与えることで、

あらかじめ整列されていないテストケースを省略することが出来るだけでなく

テストケース生成試行回数の全体上限に達してしまうことなく、１００個のテストケースの生成が成功することを保証できます。

生成機を宣言するためのコンビネーターについては後述します。

（とりあえず、ここまで）

■ 構文強調ソースコードとはてな記法の続き

はてな記法無効化

ソースコード中において「はてな記法のみ」を無効化する方法について

はてなアイデアで提案が無いか見てみた。

http://i.hatena.ne.jp/idea/5731

　superpre(>|| ||<)を使えとの事。

http://i.hatena.ne.jp/idea/5774

　それではダメなんだと再提案

http://d.hatena.ne.jp/studiokingyo/comment?date=20050903#c

>以前自分もまったく同じ要望をはてなに出しましたが、却下されました。

どうやら「はてな記法だけ無効化」の線は望み薄いかな。

ソースコード以外における乱用を畏れていると妄想した。

ソースコード強調記法

それなら逆に「ソースコードのみ」に対して使える記法があればいいのでは。

というか、それでソースコードを囲めば自動的に構文強調されると有り難い

（ちなみにpukiwikiでは実際にpluginとしてそのようなものがある。

http://www.sys.tutkie.tut.ac.jp/~sasaki/pukiwiki/index.php?Man%2FLatest）

ということで、こちらもはてなアイデアを探してみた。

http://i.hatena.ne.jp/idea/3560

そのような要望は多いようで発行済株数は1000になっている。

■ 実現への妄想

ライセンス上問題が無ければvimのsyntaxファイルを使えるといいと思う。

• すでに200以上の言語に対応している。

スクラッチからそれぞれの言語の構文用のコードを書く場合、マイナーな言語は後回しにされる可能性が高い。

• 新しい言語や新しい文法にも対応できる。

vimには沢山のユーザーが存在するため、はてながやらなくてもどこかの誰かがきっと新規のsyntaxファイル作ってくれる。

• vimのsyntaxファイルはパワフルでは無いがシンプルである。

＝構文解析しないので早い＆実装も比較的簡単に出来る

Haskell文法定義ファイル（http://www.haskell.org/libraries/haskell.vim）を見てみる。

次の様な行が沢山ならんでいる。

syn region  hsString		start=+"+  skip=+\\\\\|\\"+  end=+"+  contains=hsSpecialChar
syn match hsStructure		"\<\(class\|data\|deriving\|instance\|default\|where\)\>"

これは正規表現でマッチしたものに対してhsStructureやhsStringのようなgroup-nameを付けているだけである。group-nameはそのままCSSのクラス名にすれば良い.

こんな風に。

<span class="hsString">"string"</span>

<span class="hsStructure">where</span>

haskell.vimの下の部分には次のような行が並んでいる箇所がある。

hi link hsInfix			  PreProc

hi link hsStatement	          Statement

これは「hsInfixはPreProcにリンクされてますよ。つまりPreProcで設定されたものと同じhighlightになりますよ」という意味。

このようにgroup-nameをリンクさせる事で、他の言語を使っていても「コメント」ならこの色、「文字列」ならこの色、という構文強調が共有できる。

だから、

<span class="hsInfix">infixr</span>

より

<span class="PreProc">infixr</span>

と書いた方が良い。

ユーザー定義のクラスと被らないようにPrefixを付けた方がいいかもしれない。

例えばvimのsyntax定義の構文に従って"syn"を頭に付ければどうだろう。

<span class="synPreProc">infixr</span>

これはつまりこう表示される。

infixr

さて、ここで「このHTML」のソースを見て欲しい。

実際に

<span class="synPreProc">infixr</span>

と書いてある。

なぜこんなことが出来るのか？

実ははてなは構文強調をデフォルトのスタイルシートに既に組み込んでいる！

http://d.hatena.ne.jp/css/base.css

この下の部分

/* SUPERPRE SYNTAX HIGHLIGHT */

.synSpecial { color: #c000c0; }
.synType { color: #008000; }
.synComment { color: #0000c0; }
.synPreProc { color: #c000c0; }
.synIdentifier { color: #008080; }
.synConstant { color: #c00000; }
.synStatement { color: #804000; }

上ではPRE記法(>| |<)で書いていたが、コメントからSUPERPRE記法(>|| ||<)で使えるようにするつもりなのが分かる。

http://naoya.g.hatena.ne.jp/naoya/20060616/1150466540

最初、このページをみたとき、何をしようとしているのか分からなかったが

それはつまりそういうことなのでは、と妄想してみた。

半分以上は願望です。

参考:VIMリファレンスマニュアル 構文強調 syntax.txt (訳 村岡太郎氏）

http://briefcase.yahoo.co.jp/bc/jod2357/lst?&.dir=/vimdoc&.src=bc&.view=l

■

おまけ：vimな人にとって「開発中に見ているコード」と「Blogで見られるコード」が一致すると嬉しいかも。

ちなみに自分はMeadowを使ってます。