他人のHaskell日記 RSSフィード

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

2006-06-19

完全数  完全数 - 他人の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つ目を求めようとすると凄く遅い。やっぱり素因数分解が必要か。

やばい、今日日記凄く長い。  やばい、今日の日記凄く長い。 - 他人のHaskell日記 を含むブックマーク

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

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

Prelude車輪再開発事業従事者へのQuickCheckの勧め。  Prelude車輪再開発事業従事者へのQuickCheckの勧め。 - 他人のHaskell日記 を含むブックマーク

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汚染にかかっているので終了しちゃいますが、

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

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

テストデータ生成機を自作すれば問題無し?)



QuickCheckオンラインマニュアル部分訳 QuickCheckオンラインマニュアル部分訳 - 他人のHaskell日記 を含むブックマーク

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

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

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

QuickCheckって何?

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

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

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

そうすると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

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

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

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

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

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

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

Arguments exhausted after 97 tests.

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

定量的特性

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

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

例えば

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

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

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

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

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

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

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

(とりあえず、ここまで)

構文強調ソースコードはてな記法の続き 構文強調ソースコードとはてな記法の続き - 他人のHaskell日記 を含むブックマーク

はてな記法無効化

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

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

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になっている。

実現への妄想 実現への妄想 - 他人のHaskell日記 を含むブックマーク

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

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

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

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

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

2006-06-19 - 他人のHaskell日記 を含むブックマーク

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

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

MeadowMeadow2012/01/06 03:09In the cmopliacetd world we live in, it's good to find simple solutions.

lwjtjrlwjtjr2012/01/06 19:07VCAmjP <a href="http://xzeizzjdpxdq.com/">xzeizzjdpxdq</a>

pxakzulxsiepxakzulxsie2012/01/07 23:43clkjNh , [url=http://yoqflftjklmz.com/]yoqflftjklmz[/url], [link=http://ibutncmxkxhr.com/]ibutncmxkxhr[/link], http://ckmtbknghhpf.com/

wecoawuyvwecoawuyv2012/01/08 21:30WKBmda <a href="http://cqaibwagxqav.com/">cqaibwagxqav</a>

majvaamajvaa2012/01/09 00:443mPG8V , [url=http://pefuwzkcazkn.com/]pefuwzkcazkn[/url], [link=http://zyovhdxfsoee.com/]zyovhdxfsoee[/link], http://wvnrgjpmaofa.com/