他人のHaskell日記 RSSフィード

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

2006-06-20

誤差  誤差 - 他人のHaskell日記 を含むブックマーク

*Main> 1 == 1
True
*Main> 1 / 10 == 0.1
True
*Main> 1 / 100 == 0.01
True
*Main> 1 / 100 == (1/10)^2
False
*Main> -- ????
*Main> 1 / 100
1.0e-2
*Main> (1/10)^2
1.0000000000000002e-2
*Main> --- !!
*Main> 1
1
*Main> 1 /10
0.1
*Main> 1 /10 * 10
1.0
*Main> 1 == 1/10*10
True
*Main> 1
1
*Main> 1 / 9
0.1111111111111111
*Main> 1 / 9 * 9
1.0
*Main> 1 == 1 /9 * 9
True
*Main> -- !!
*Main> 1 +0.1
1.1
*Main> 1 +0.000000001
1.000000001
*Main> 1 +0.0000000000000000000000000000000000000000000000000000001
1.0
*Main> 1 == 1 +0.1
False
*Main> 1 == 1 +0.000000001
False
*Main> 1 == 1 +0.0000000000000000000000000000000000000000000000000000001
True

*Main> 0.9
0.9
*Main> 0.99999999999
0.99999999999
*Main> 0.999999999999999999999999999999999999999999999999999999999999999999999
1.0

四捨五入

 *Main>  take 25 $ scanl (\x y-> x + 9*((1/10)^y)) 0.9 [2..]
[0.9,0.99,0.999,0.9999,0.99999,0.9999990000000001,0.9999999,
 0.9999999900000001,0.999999999,0.9999999999,0.99999999999,
0.999999999999,0.9999999999999,0.99999999999999,0.999999999999999,
0.9999999999999999,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0]

等比数列の和

ちなみに0.9999999・・・・・・= 1は結果としては、正しい。

証明

f:id:taninsw:20060620171250j:image

はてなトピックツリー はてなトピックツリー - 他人のHaskell日記 を含むブックマーク

http://haskell.g.hatena.ne.jp/topictree

「要素を繰り返したリスト」のところが相互参照のためループになってる・・・。

QuickCheck応用(妄想 QuickCheck応用(妄想) - 他人のHaskell日記 を含むブックマーク

QuickCheckオンラインマニュアル勝手訳続き) QuickCheckオンラインマニュアル(勝手訳続き) - 他人のHaskell日記 を含むブックマーク

訳が終わりました

http://haskell.g.hatena.ne.jp/taninsw/20060619/p4 の続きです 

後半の方は理解できていません。

(Arbitaryクラスのcoarbitraryメソッドとか、反例となる「関数」をShowで表示する当たりとか)

テストケースの分布を監視する

テストケースの分布を認識しておくことは重要です。

もしテストデータが正しく分布していなければ、そのテストから導き出される結果もまた、不確かなものになってしまいます、

特に「 ==>」演算子テストデータの分布を大きく歪めることがあります。条件式を満たすようなテストデータばかりが使われるからです。

QuickCheckにはテストデータの分布を観察するいくつかの手段があります。

観察を行うためのコードは特性のステートメントに取り込まれています。

特性が実際にテストされるたびに、観察が行われます。

集められた観察結果はテスト終了時に要約されます。

ささいな(trivial)ケースを数える

特性は次のように書けます

	<条件式> `trivial` <特性>

例えば

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

条件式が真となるようなテストケースはささいな(trivial)ケースとして分類され、

全体におけるささいな(trivial)ケースの比率が報告されます。

この例ではテストは次のような出力をします。

Main> quickCheck prop_Insert
OK, passed 100 tests (58% trivial).

テストケースを分類する。

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

	classify <条件式> <分類名::String>$ <特性>

例えば

prop_Insert x xs = 
	ordered xs ==> 
		classify (ordered (x:xs)) "at-head"$
 		classify (ordered (xs++[x])) "at-tail"$
		ordered (insert x xs)
  where types = x::Int

条件式を満たしたテストケースは、与えられた分類に結びつけられます

分類別の分布がテストの後に報告されます。

この場合、結果は

Main> quickCheck prop_Insert
OK, passed 100 tests.
58% at-head, at-tail.
22% at-tail.
4% at-head.

テストケースを複数の分類に分けることができることに注目してください。

データの値を集める。

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

	collect <式>$ <特性>

例えば,

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

collectの引数はそれぞれのテストケースに対して評価されます。

そして、値の分布が報告されます。

この引数の型はShowクラスに属していなければなりません。

上の例では結果は次のようになります。

Main> quickCheck prop_Insert
OK, passed 100 tests.
58% 0.
26% 1.
13% 2.
3% 3.

観察を結合する

ここで上げた観察はどれでも自由に結合することができる。

テストケース毎の全ての観察が結合され

これらの結合の分布が報告される。

例えば、こんな特性をテストしよう。

prop_Insert x xs = 
	ordered xs ==> 
		collect (length xs)$
		classify (ordered (x:xs)) "at-head"$
 		classify (ordered (xs++[x])) "at-tail"$
		ordered (insert x xs)
  where types = x::Int

実行結果

Main> quickCheck prop_Insert
OK, passed 100 tests.
58% 0, at-head, at-tail.
22% 1, at-tail.
13% 2.
4% 1, at-head.
3% 3.

この結果から「要素の数が1つより大きいリストに対して、リストの最初や最後へのinsertは、テストが行われていない」ことが分かる。

テストデータ生成機: 型Gen

テストデータテストデータ生成機によって産み出されます。

QuickCheck は多くの型に対してデフォルトの生成機が用意されていますが、

"forAll"によって自作の生成機を利用することもできます。

自分で宣言したような新しい型に対しては自らテストデータ生成機を定義する必要が出てくるでしょう。

型aの値を生成する生成機は"Gen a"という形の型になっています。

型Genはモナドなので、Haskellのdo記法や標準モナド関数を生成機を定義するために使うことが出来ます。

生成機は次のような関数から組み立てる事が出来ます。

choose :: Random a => (a, a) -> Gen a

この関数は与えられた範囲の中から乱数を選んで返します。

分布は一様分布になります。

例えばリストの中からランダムに要素を選びたいなら、次のように書けます

do i<-choose (0,length xs-1)
   return (xs!!i)

選択肢の中から選ぶ

生成機は次のような形を取ることが出来ます。

	oneof <生成機のリスト>

生成機のリストのなかから一つ選び出します。

それぞれが選ばれる確率は全て等しくなっています。

例えば

oneof [return True, return False]

この場合、TrueとFalseのどちらかが選ばれます。それぞれの確率は1/2です。

次の関数を代わりに用いることで結果の分布をコントロールすることが出来ます

	frequency :: [(Int, Gen a)] -> Gen a

Frequency関数リストの中からランダムに生成機を選び出しますが、

選択肢に与えられた重みに基づいて、確率が変動します。

例えば

frequency [(2,return True), (1,return False)]

は、2/3の確率でTrueを返し、1/3の確率でFalseを返します。

テストデータの大きさ

テストデータ生成機は暗黙のサイズパラメータを持っています。

quickCheck は始めは少ない数のテストケースを生成していますが、

テストが進むに従ってサイズはだんだん増えていきます。

テストデータ生成機によってサイズパラメータの扱いは代わります。これを無視するものもあります。

例えば、リスト生成機では。これを生成するリストの長さの最大値だと解釈します。

自分のテストデータ生成機をコントロールしたいなら、自由にこれを使って構いません。

サイズパラメータの値は次の関数を使うことによって得られます

	sized :: (Int -> Gen a) -> Gen a

sized g は gを呼び, 現在の大きさをパラメータとして渡します。

例えば、 0 から size までの範囲の中から自然数を生成するには、次のようにします

sized $ \n -> choose (0, n)

サイズをコントロールするのは、テストを素早く行える程度には小さく、

それでいて、エラーを見つけ出せる程度にはテストデータが大きいことを保証するためです。

デフォルトのサイズコントロールではこの目的を達成できないことが時々あります。

例えば、テストが終わりに近づくに従ってテストデータリストは50要素

ぐらいまで増えているでしょう。そうすると選択肢リストリストは2500要素になるでしょう。

これでは大きすぎてテストを効率的に行えません。

そんな場合は、サイズパラメータを明示的に変更することが出来ると便利でしょう

そのために次の関数を使います

	resize :: Int -> Gen a -> Gen a

resize n g は生成機 g をサイズパラメータ nで実行します。.

サイズパラメータは決して負の数にすべきではありません。

例えば、ランダム行列を生成するには元のサイズの平方根が適切なサイズパラーメータとなるでしょう。

matrix = sized $ \n -> resize (round (sqrt n)) arbitrary

再帰データ型の生成

再帰的なデータ型の生成機は、 コンストラクタリストの中から選ぶoneofやfrequencyを使って簡単に表現できます。

Haskellの標準モナドコンビネータを生成機を構成するために使うことも出来ます。

例えば、 ツリーの型が次のように定義されていたとすると

data Tree = Leaf Int | Branch Tree Tree

ツリー型の生成機はこのように定義できるでしょう。

tree = oneof [liftM Leaf arbitrary,
	      liftM2 Branch tree tree]

しかしながら、再帰的な生成機はいつまでたっても終了しなかったり、とても巨大な値を出力したりする危険性を常に秘めています。

これを避けるために、再帰的な生成機は常にサイズコントロールの機構を利用すべきです。

例えば

tree = sized tree'
tree' 0 = liftM Leaf arbitrary
tree' n | n>0 = 
	oneof [liftM arbitrary,
	       liftM2 subtree subtree]
  where subtree = tree' (n `div` 2)

注:

* サイズがゼロになるときにLeafを返すことによって終了を保証している。

* 再帰の度に「サイズ」は半分になるので、サイズはツリーのノードの数の上限を与えている。 「サイズ」は自分が望むように解釈して良い。

* 当然だが、Branchの二つの枝がサブツリーの生成機を共有していても、それぞれのケースについて同じ木を生成していることにはならない。

便利な生成機コンビネータ

もしg が型 tの生成機ならば

    * two g はtsのタプル(二因子)を生成します,
    * three g は tsのトリプル(三因子)を生成します。 
    * four g は tsのクアドルプル(四因子)を生成します
    * vector n g は n ts.のリストを生成します。 

もし xs がリストなら elements xs は xsの要素の選択肢を生成します。

Arbitaryクラス

QuickCheckHaskellのオーバーローディング機構を用いてそれぞれの型に対するデフォルトテストデータ生成機を宣言しています。

これは次のクラスを用いることによって達成されています。

class Arbitrary a where
  arbitrary   :: Gen a
  coarbitrary :: a -> Gen b -> Gen b

QuickCheck は次のそれぞれの型についてインスタンスを宣言しています。

(), Bool, Int, Integer, Float, Double, タプル(二因子), トリプル(三因子), クアドルプル(四因子),リスト関数

クラスメソッド arbitrary は型 aのデフォルトの生成機です。.

デフォルトの生成機は、他の型に対しても定義出来ます

クラス Arbitrary のインスタンスであると宣言し、arbitraryメソッドを実装すれば良いのです。

クラスメソッドcoarbitraryランダム関数値を生成するために使われます

型 (a->b)に対するarbitrary の実装は型aに対するcoarbitraryを利用します

ある型のランダムな値を生成したいだけなら、その型についてarbitrary メソッドを定義するだけでかまいません。

その型に対するランダム関数も生成したいのならば、そのときは両方ののクラスメソッドを定義しましょう。

coarbitrary メソッドは型 aの値を生成機変換として.解釈します。

異なる値なら独立した生成機変換として解釈できるように定義されるべきです。

これらは次の関数を用いることによってプログラミングできます。

	variant :: Int -> Gen a -> Gen a

i と jの異なる自然数に対して, variant i g and variant j g は独立した生成機変換です。

variant の引数は負であってはいけませんし、効率のために小さくあるべきです。

coarbitraryのインスタンスは、variant.によって構成された生成機変換を一緒に合成することによって定義されます。

例えばツリー型が次のように定義されているのなら

data Tree = Leaf Int | Branch Tree Tree

Arbitraryの相応しいインスタンスは 次のように定義できるでしょう。

instance Arbitrary Tree where
  arbitrary = sized tree'
    where tree' 0 = liftM Leaf arbitrary
	  tree' n | n>0 = 
		oneof [liftM arbitrary,
	          liftM2 subtree subtree]
  	    where subtree = tree' (n `div` 2)
  coarbitrary (Leaf n) = 
	variant 0 . coarbitrary n
  coarbitrary (Branch t1 t2) = 
	variant 1 . coarbitrary t1 . coarbitrary t2|

関数の特性

QuickCheck関数値を生成することも出来ますし、それによって関数の特性をチェックできます。

例えば 関数合成結合性についてチェックしたいなら次のようにします。

prop_ComposeAssoc f g h x =
  ((f . g) . h) x == (f . (g . h)) x
  where types = [f, g, h] :: [Int->Int]

しかしながら、このような特性をテストするためには

反例が見つかったときのために関数値を表示できるようにしておかなければなりません

つまる関数の型がShowクラスインスタンスでなければならない、ということです。.

Tこの変更のために、このkindの高階特性を含む全てのモジュールにおいてShowFunctionsモジュールを 

反例が見つかったら関数値が常に "<function>"と表示されようにしているなら、何らかの問題が発生するでしょう。

Tip: newtypeを使おう

QuickCheckのおかげで、それぞれの型とテストデータの生成機を結びつけることは簡単に出来ます

しかし同じ型に対して異なるテストデータの分布が必要になることもあるでしょう。。

例えば構文木を操作するプログラムテストしていると仮定します。

変数コンストラクタは次のようになっています。

data Expr = Var String | ...

ここでは変数名は文字列型として扱っています。

しかし、文字列型に対するデフォルトテストデータ生成機が、変数名にふさわしい分布を生成することは滅多にないでしょう。

例えば、ランダムな「式(Expr型)」のテストデータが生成においては、

テストデータの中で名前の衝突が発生してくれることが望まれるでしょう。

しかし、ランダムな文字列(例:"p}v(\231\156A.")が二つ抜き出されたとして、

その二つが等しくなることは滅多にありません。

もちろん、テストデータ生成機を変数名のために自作することで、この問題はやりすごせます。

自作生成機を「限定された小さな集合の中からテストデータを選び出す」ように設計すれば、

名前が競合する確率を上げることが出来ます。

「文字列が変数名の役割をしているところでは、forAll関数を使って、その自作生成機を指定するんだ。」ということを、いつも覚えてさえいれば、たしかに上手くいくでしょう。

しかし、これは間違いを生みやすい困った傾向です。

もっとよい方法があります。

名前のための新しい型を文字列の同型として(newtype宣言で)定義することです。

そして、この型のために生成機を自作し、それにクラスメソッドを実装することで

その型のデフォルトの生成機にしてしまえばいいのです。

例えば次のようになります。

newtype Name = Name String

instance Arbitrary Name where
  arbitrary = oneof ["a", "b", "c", "d", "e"]

名前を意味するものが現れるあらゆる場所でName型を使うように気をつければ

特性をとても簡単にかけるし、また、つまらない過ちを起こさずに済むのです。

有理数(分数)の実装  有理数(分数)の実装 - 他人のHaskell日記 を含むブックマーク

このサイトを見て、型クラス概念の習得に良さそうな感じがしたのでやってみる。

http://d.hatena.ne.jp/haskon/20060619

data Ratio = Ratio Integer Integer --deriving (Show)

instance Show Ratio where
  show (Ratio a 1) = show(a)                              
  show (Ratio a b) = show(a)++"/"++show(b)

instance Eq Ratio where
  a == a' = case a - a' of 
             Ratio 0 1 -> True
             otherwise -> False 

instance Ord Ratio where
  x <= y  = case y - x of Ratio a b -> a > 0

instance Num Ratio where
  (Ratio a b) *  (Ratio c d) = yakubun(Ratio (a*c) (b*d))
  (Ratio a b) -  (Ratio c d) = (Ratio (a) b) + (Ratio (-c) d)
  (Ratio a b) +  (Ratio c d) = yakubun(Ratio (a*d+b*c) (b*d))
  abs (Ratio a b) = case yakubun(Ratio a b) of 
                      Ratio c d | c >= 0    -> Ratio c d
                                | otherwise -> Ratio (-c) d     
  signum (Ratio a b) = case yakubun(Ratio a b) of 
                         Ratio c _ | c  > 0 -> 1
                                   | c == 0 -> 0
                                   | c  < 0 -> -1
  fromInteger n      = Ratio n 1


ratio (a,b) = yakubun (Ratio a b)
yakubun(Ratio a b) = Ratio (div a c) (div b c) where c = gcd a b * (if b < 0 then -1 else  1)
gyakusu(Ratio a b) = yakubun(Ratio b a)

(Ratio a b) `waru`  (Ratio c d) = (Ratio a b) * gyakusu(Ratio c d)

jou :: Ratio -> Integer -> Ratio
jou a n | n  < 0 = jou (gyakusu a) (-n)
        | n == 0 = Ratio 1 1
        | n == 1 = a
        | otherwise =  a * (jou a (n-1))

実行結果。

*Main> gyakusu(fromInteger 3) * (fromInteger 2)
2/3
*Main> gyakusu(fromInteger 3) * (fromInteger 2)
2/3
*Main> jou (gyakusu(fromInteger 3) * (fromInteger 2)) (-3)
27/8
*Main> (jou (gyakusu(fromInteger 3) * (fromInteger 2)) (-3)) - racio(23,8)

<interactive>:1:56: Not in scope: `racio'
*Main> (jou (gyakusu(fromInteger 3) * (fromInteger 2)) (-3)) - ratio(23,8)
1/2
*Main> (jou (gyakusu(fromInteger 3) * (fromInteger 2)) (-3)) - ratio(23,8)

AmitAmit2012/05/05 10:00I was so confsued about what to buy, but this makes it understandable.