HaskellのHspecでテストケースぶん回したいの巻

Hspecって（使いづらいけど）楽しいよね！

特に使いづらいと思ったのがこれ。

Hspecで関数fの振る舞いを記述するとき、テストケースとして[(a1,b1),(a2,b2),...]っていうリストを渡して「f a1 `shouldBe` b1」みたいに書きたいとか思ってもモナドに阻まれて諦めてる

— 定食屋 おろポン (@oroponya) February 15, 2014

Hspecはなにも悪くないんだけどさ。describeとかitとかって、なんかIOモナドとかモナドとか、そういう「よくわからない何か」の香りがするんだよね。 だってdoで振る舞い（it関数）を連続して書けるんだよ？

main = hspec $ do
  describe "test" $ do
    it "will pass" $
      0 `shouldBe` 0
    it "will not pass" $
      0 `shouldBe` 1

test
  - will pass
  - will not pass FAILED [1]

1) test will not pass
expected: 1
 but got: 0

これはもう、間違いなくモナドとかモナドとかモナドとかそういう系ですよ。

ちなみに、やりたいことはこんな感じね。やっぱり、楽したいじゃん。

main = hspec $ do
  describe "test" $ do
    map (\(input,expected)-> it "try!" input `shouldBe` expected) testCases

testCases = [(0,0),(0,1)]

でも、もちろんこれはコンパイル通りません。型が全然違うからね。

これくらいはLLなら、forやらeachやら回せばパツイチですよ。 だけど、Haskellにはforもeachもないんですよ。どうすればいいんだよ。

悲嘆にくれつつ、すごいHな本を読みあさっていると、こう書いてありました。（意訳）

mapMも、forMも、あるんだよ

すごいH本と、Control.Monadは偉大でした。

Prelude Control.Monad> :t mapM_
mapM_ :: Monad m => (a -> m b) -> [a] -> m ()
Prelude Control.Monad> :t forM_
forM_ :: Monad m => [a] -> (a -> m b) -> m ()

[a]を受け取り、aをゴニョゴニョするとモナモナする関数を全てのaに適用し、返り値は捨てる。

まさにこれだ！！！ っていうかこれ、ある意味ではfor文じゃねえの？？

import Control.Monad
main = forM_ [1..5] print

出力
1
2
3
4
5

import Control.Monad
main = forM_ [0..3] (\i -> forM_ [0..3] (\j -> print [i,j]))

出力
[0,0]
[0,1]
[0,2]
[0,3]
[1,0]
[1,1]
[1,2]
[1,3]
[2,0]
[2,1]
[2,2]
[2,3]
[3,0]
[3,1]
[3,2]
[3,3]

FORだった！！

そしてこれを使うと、

main = hspec $ do
  describe "test" $ do
    it "will pass" $
      0 `shouldBe` 0
    it "will not pass" $
      0 `shouldBe` 1

test
  - will pass
  - will not pass FAILED [1]

1) test will not pass
expected: 1
 but got: 0

は、こう書けますね。

main = hspec $ do
  describe "test" $ do
    forM_ tests $ \(input,expected) ->
      it (show input ++ " -> " ++ show expected) $
        input `shouldBe` expected

tests = [(0,0),(0,1)]

test
  - 0 -> 0
  - 0 -> 1 FAILED [1]

1) test 0 -> 1
expected: 1
 but got: 0

参考) http://qiita.com/kei_q/items/f4bce3f94793b99f0871

Cool!!

あとはテンプレ化してGistにおいておけば楽ちん。わふー。

gist9542555

RubyのModule#===について

==と===のおさらいは飛ばして記事の下の方を読む

==とか===とかequalとか

==での同値性判定は暗黙の型変換を行ってゆるーくふわっと判定するけど、===は型変換を行わずに同値性判定を行う言語ってありますよね。
PHPとかJavaScriptとか。

一方で、==はオブジェクトの同一性判定を行うため、同値性判定を行うにはa equals(b)とか[a isEqualTo*:b]とか書く言語もありますよね。
JavaとかObjective-Cとか。

Rubyのお話

Rubyの==について

Rubyでは、==はメソッドなので、同値性判定なのか同一性判定なのかもよくわからない可愛いやつです。

==は同一性判定を行うように定義されていますが、同値性判定を行うように==をオーバーライドすることを期待されています。*1

逆に、equal?はオーバーライドしてはいけません。

Unlike ==, the equal? method should never be overridden by subclasses as it is used to determine object identity Class: BasicObject (Ruby 2.1.0)

例えばStringは==で同値性を判定できます。

a = "hoge"
b = "hoge"
puts a.object_id #=> 70312919003820
puts b.object_id #=> 70312919003800
puts a.equal? b #=> false
puts a == b #=> true

ただ、自前で実装したクラスに==を定義していないと同値性判定ではなく同一性判定を行うので、ちゃんとオーバーライドしてないのに同値性判定を期待すると痛い目にあいます。

class Cat
  attr_reader :name, :age
  def initialize name, age
    @name = name
    @age = age
  end
end

mike = Cat.new("mike",5)
kuro = Cat.new("kuro",3)

puts mike != kuro #=> true
puts [mike, kuro].include? Cat.new("mike",5) #=> false

Rubyの===について

PHPやJavaScriptとは違い、Rubyの===は「==より厳密な同値性判定を行う」といった性質のものではありません。

===はcase式のためにあるような演算子メソッドで、

case a
when b then hogehoge()
when c then fugafuga()
end

case式の中でaとbを比較するために===が使用されます。

ここで注意すべきなのは、a === bではなく、b === aが呼ばれるということです。 これらは全く違います。 ===は単なる演算子ではなくメソッドなので、どちらがレシーバで、どちらが引数なのかはとても重要です。

メソッド呼び出しであることがわかりやすいように書き直すと、a.===(b)ではなく、b.===(a)が呼ばれます。

===のオーバーライド時に一般に期待されるのは、「所属性」を返すことです。*2

b.===(a)に求められるのは、「引数aは、bに所属しているか」を返すことです。

よくRubyのcase式の例で挙げられる、Range#===は、Range#include?、Range#member?と全く同じです。*3

そのため、こんなクールなcase式を書けます。

case 1
when (1..3) then puts "Expected"
else puts "Oops.."
end

#=> Expected

しかし、Rangeオブジェクトそのものをcase式で比較すると、意に反した動作をします。 (1..3) === (1..3)、つまり(1..3).include? (1..3)はfalseだからです。

range = (1..3)
case range
when (1..3) then puts "Expected"
else puts "Oops.."
end

#=> Oops..

Module#===について

たとえば、引数に名前か年齢を受け取るメソッドを考えてみます。 名前を渡されたら挨拶を、年齢を渡されたら年齢を表示するメソッドです。

def a_method name_or_age
  # 名前なら、"hello, name!"と出力
  # 年齢なら、"You are age years old"と出力
end

そこで、引数の型チェックを行ってみようと思います。

ぱっと浮かぶのはこんなコードでしょうか。

def a_method name_or_age
  case name_or_age.class
  when String then puts "hello, #{name_or_age}"
  when Fixnum then puts "You are #{name_or_age} years old"
  else raise ArgumentError
  end
end

name_or_ageのクラスによって分岐して、Stringなら挨拶を、Integerなら年齢を表示します。

これを実行してみます。

a_method "oropon" #=> in `a_method': ArgumentError (ArgumentError)
a_method 27 #=> in `a_method': ArgumentError (ArgumentError)

動きません！StringでもFixnumでもないよ、と怒られてしまいます。

でも、==で比較してみるとちゃんとtrueが返ってきます。

puts "oropon".class == String #=> true
puts 27.class == Fixnum #=> true

==での比較はtrueなのに、===で比較するとfalseなの？ ==は===より厳格じゃないの？？

YES!! 上でRangeの例を挙げたように、Rubyでは==と===は厳格さが違うのではなく、用途が違うんです！

先ほどのコードを書き直すと、こんな感じになります。

def a_method name_or_age
  case name_or_age
  when String then puts "hello, #{name_or_age}"
  when Fixnum then puts "You are #{name_or_age} years old"
  else raise ArgumentError
  end
end

a_method "oropon" #=> hello, oropon
a_method 27 #=> You are 27 years old

caseの右にあるname_or_age.classから、.classが取れてname_or_ageだけになりました。

これだけで何故うまく動くのかの答えは、Module#===の実装にあります。 StringやFixnumはClassクラスのインスタンスで、ClassクラスはModuleクラスのサブクラスです。Class#===は、継承元のModule#===が呼び出されます。

ドキュメントを見てみます。

self === obj -> bool

指定された obj が自身かそのサブクラスのインスタンスであるとき真を返します。 また、obj が自身をインクルードしたクラスかそのサブクラスのイン スタンスである場合にも 真を返します。上記のいずれでもない場合に false を返します。

言い替えると obj.kind_of?(self) が true の場合、 true を返します。

このメソッドは主に case 文での比較に用いられます。 case ではクラス、モジュールの所属関係をチェックすることになります。

instance method Module#===

これで謎が解けました。

String === "oropon".classは、"oropon".class.kind_of?(String)ということで、これは「StringクラスはStringクラス*4のインスタンスですか？」と聞いているに等しいわけです。もちろん返り値はfalseです。

ついでに、kind_of?で比較するのでこう書き換えられます。

def a_method name_or_age
  case name_or_age
  when String then puts "hello, #{name_or_age}"
  when Integer then puts "You are #{name_or_age} years old" # Fixnum -> Integer
  else raise ArgumentError
  end
end

a_method "oropon" #=> hello, oropon
a_method 27 #=> You are 27 years old

FixnumをIntegerに書き換えたことで、引数がFixnumでもBignumでも年齢として扱います。

以上、「case式は、==が通っても===は通らないことがあるから気をつけろよ！」「case式や===の挙動は直感だけに頼らずちゃんと確認しろよ！」というお話でした。

*1:instance method Object#==

*2:instance method Object#===

*3:instance method Range#===

*4:あるいはそのサブクラス

HaskellのnubとRubyのuniq

HaskellのData.List#nubと、 RubyのArray#uniqは、どちらもリスト/配列内の重複要素を取り除いた新しい配列を返す関数です。

どうもHaskellのnubはRubyに比べてだいぶ遅いなあと感じます。 リストと配列のデータ構造の違いに起因するのだろうと想像はできますが、いまいち腑に落ちない*1のでまずは計測を行いました。

まずは、重複の全くない長いリスト/配列についてです。 具体的には、1から100,000までの数値を突っ込んだリスト/配列の重複を取り除きます。

nub.hs

module Main where

import Data.List

main = print $ length $ nub $ [1..100000]

uniq.rb

puts (1..100000).to_a.uniq.length

計測結果

$ time ./nub
100000

real    0m59.538s
user    0m59.229s
sys 0m0.121s

$ time ruby uniq.rb 
100000

real    0m0.097s
user    0m0.068s
sys 0m0.027s

Rubyのほうが600倍以上速いですね。

---

では、要素数は変えずに、重複の多いリスト/配列について確認します。 具体的には、1から1000までの数値を100回繰り返したリスト/配列の重複を取り除きます。

nub2.hs

module Main where

import Data.List

main = print $ length $ nub $ concat $ replicate 100 [1..1000]

uniq2.rb

puts (1..1000).to_a.*(100).uniq.length

計測結果

$ time ./nub2
1000

real    0m0.593s
user    0m0.589s
sys 0m0.003s

$ time ./uniq2.rb 
1000

real    0m0.062s
user    0m0.037s
sys 0m0.025s

だいぶ差が縮まりましたが、Rubyのほうが10倍近く速いです。

Rubyは対して変わっていませんが、Haskellについては、ちょうど100倍くらい速くなっています。

---

ここらへんで、実装を見てみることにします。

まずはHaskell

Haskell (Data.List.hs)

hackage

-- | /O(n^2)/. The 'nub' function removes duplicate elements from a list.
-- In particular, it keeps only the first occurrence of each element.
-- (The name 'nub' means \`essence\'.)
-- It is a special case of 'nubBy', which allows the programmer to supply
-- their own equality test.
nub                     :: (Eq a) => [a] -> [a]
#ifdef USE_REPORT_PRELUDE
nub                     =  nubBy (==)
#else
-- stolen from HBC
nub l                   = nub' l []             -- '
  where
    nub' [] _           = []                    -- '
    nub' (x:xs) ls                              -- '
        | x `elem` ls   = nub' xs ls            -- '
        | otherwise     = x : nub' xs (x:ls)    -- '
#endif

計算するまでもなく、O(n^2)って書いていますね。ひい。

これはHaskellが悪いわけではなく、Ordのインスタンスでない型に対しても使えることから来ています。 逆に言えば、(Ord a) => [a] -> [a]であればオーダーの少ないアルゴリズムを使用できます。 Ordのインスタンスの場合、O(n * log n)となるnubOrdをがこちらで提示されています。

unique elements in a haskell list - Stack Overflow

import qualified Data.Set as Set

nubOrd :: Ord e => [a] -> [a] 
nubOrd xs = go Set.empty xs where
  go s (x:xs)
   | x `Set.member` s = go s xs
   | otherwise        = x : go (Set.insert x s) xs
  go _ _              = []

ちなみにこれを使うと、Rubyとほぼ同じ速度になります。

-- main = print $ length $ nubOrd $ [1..100000]

$ time ./nub3 
100000

real    0m0.082s
user    0m0.076s
sys 0m0.005s

Ruby (array.c)

GitHub

static VALUE
rb_ary_uniq(VALUE ary)
{
    VALUE hash, uniq;

    if (RARRAY_LEN(ary) <= 1)
        return rb_ary_dup(ary);
    if (rb_block_given_p()) {
        hash = ary_make_hash_by(ary);
        uniq = rb_hash_values(hash);
    }
    else {
        hash = ary_make_hash(ary);
        uniq = rb_hash_values(hash);
    }
    RBASIC_SET_CLASS(uniq, rb_obj_class(ary));
    ary_recycle_hash(hash);

    return uniq;
}

Rubyは、というと、Hashをうまく使っています。

重要なのはここですね。

hash = ary_make_hash(ary);
uniq = rb_hash_values(hash);

ary_make_hash(ary)は、配列をハッシュにします。Rubyで書くとこんなかんじ。

p [1,2,3].inject({}){ |h,elt| h[elt] = elt;h; } #=> {1=>1, 2=>2, 3=>3}
p ['a','a','a','b','b','c'].inject({}){ |h,elt| h[elt] = elt;h; } #=> {"a"=>"a", "b"=>"b", "c"=>"c"}

ハッシュは同一のキーを持たないので、この時点で重複がなくなるんですね。うまいもんだ。 あとは、rb_hash_values(hash)でvalueのみを取り出してオシマイ。

ハッシュのキー探索は速い(ほぼO(1))ので、高速に動くわけですね。

そこで「Haskellでもハッシュ使って実装してみよう」と思ったんですが、Data.HashTableはIOモナドってたのでやめました。

*1:連結リストであれ、配列であれ、重複しているかのチェックは配列を走査する必要があり、シーケンシャルアクセスでもランダムアクセスでも大きな差が出るとは思えない。。という素人考えのせい

バーコードジェネレータをゆるーくRubyで

「IOモナド難しい..Rubyで書いたらゆるふわ楽勝なのに..」

とか前に書いてたので、ほぼ同様のコードをゆるーく書いてみました。

gist8574615

# =>
#MJDRYCAD
#CKLKCQSW
#CHJAQKSZ
#YWASAYMI
#UHVRVEWW
#以下略

重複する可能性を考慮して、必要な数の２倍のコードを生成し、シャッフルしてから必要な数だけ取り出す謎の処理をしています。

「チェックサムする前に重複を削除して、重複した文をまた生成する」を繰り返すほうが速いけど10万件くらいならまあこれでよいでしょう。

Common Lisp初め

「おろポンくん、プログラミングできるの？」
僕「うーんどうだろう、少しは書けますね」
「じゃあWindowsのプログラムとか作れちゃう？」
僕「いや、Windowsはちょっと」
「分かったJavaだ」
僕「Javaは全く。。」
「なんだ、Web系？PHPとか？」
僕「PHPは前にちょっと触ったことがあるくらいですね。」
「え、ほかは？」
僕「うーん、Ruby on Railsは少し触りましたけど全然。。」
「そしたらHTMLとかCSSとかJavaScriptとか？」
僕「HTMLとCSSはなんとなく。JavaScriptもなんとなくは。」
「なんとなく？へえ。。ああ、スマートフォンアプリとかバリバリ開発しちゃう系？」
僕「iPhoneアプリなら行けるんですが、Androidアプリ書いたことないんですよね」
「え、今どき両方対応してもらわないと。。」
僕「あ。。はい。。」
「えっとじゃあ何出来るの？」
僕「あ。。あ。。」
「おろポンくん、ほんとにプログラミングできるの？」
僕「ゆ。。ゆるして。。」

今日、ぼんやりしながら、こんな脳内会話を繰り広げていました。 ルビイストです！とかJSerです！とかスマホアプリ開発行けます！とか言いたい。言いたい。

...ゆるして！

というわけで、なんとなくCommon Lispに興味がわいたので文法を調べてみました。

carとcdrはHaskellの(x:xs)的な感じですね。なるほどなるほど。

そしたらmapとfilterはすぐ書けますね、と書いてみた。functionとfuncallでハマったけど。

感想：「カッコがキモいのは慣れのような気がする」「Lispに慣れてLisp脳になれたら楽しそう」

(defun myfilter (l f)
  (cond
    ((null l)
      nil)
    ((funcall f (car l))
      (cons (car l) (filter f (cdr l))))
    (t
      (filter f (cdr l)))))

(myfilter '(Apple Orange Banana) (function (lambda (x) (eq x 'Apple))))

(defun mymap (l f)
  (cond
    ((null l)
      nil)
    (t
      (cons (funcall f (car l)) (mymap (cdr l) f)))))

(mymap '(1 2 3 4 5) (function (lambda (x) (* x x))))

バーコードのチェックサムとHaskellの練習

コンビニの商品にも、スーパーの商品にも、たいていの売り物にはバーコードがついていますね。 すだれハゲみたいなアレです。

http://ja.wikipedia.org/wiki/バーコード

日本の商品に使用されるバーコードは JANコード というもので、8桁あるいは13桁の数字を表しています。

バーコードの最後の１桁は「チェックデジット」というものです。 ざっくりいうと、8桁のバーコードの場合、最後の1桁は残りの7桁を全て足しあわせた数の'一の位'です。 *1

92384781というバーコードであれば、1がチェックデジットです。9+2+3+8+4+7+8 = 41なので、41の'一の位'である1がバーコードの最後に来るわけです。

...というようなことを風のうわさで聞きました。

「バーコードにはチェックデジットなるものがついてるらしいよ」、と。

では、なぜバーコードにはチェックデジットなんて付いているのでしょうか。 13桁の数値なら、約10兆個の商品コードが生成できます。 そのうち1桁をチェックデジットに使ってしまうと、1兆個の商品コードしか作れないじゃないですか！梅雨明けてないじゃないスか！やだー！

---

ということでウンウン唸りながら考えて、しばらくしてポンと膝をたたきました。*2

「ヤツは、バーコードの誤認識を防ぐためにあるんだな！」

ということに気が付いたのです。

コンビニとか、スーパーって、ピッピがあるじゃないですか。分かりませんか？あの、赤い光が出ててピッピ言ってるアレです。

あいつが「ピッ」って言ったら、バーコードを読み込んだ証拠です。「なかなかピッて言わないなこいつ」ってことはあっても、「ピッって言ったくせに読み込んでないじゃないスかー！やだー！」ってことはありません。

でも、商品のバーコードってわりとヨレヨレだったりするじゃないですか。掠れてたり、汚れてたり、曲がってたり、濡れてたり。

92384781ってバーコードなのに、間違えて72384781って読み込んでしまったりしそうじゃないですか。

でも、コンビニの店員さんに「すみません、こいつがピッって言ったから『この商品はすでにインプットされた』と誤解されてしまったかと思います。しかし、今のはちょっとしたミスでして、もう一度読み込むのでちょっとお待ちいただけますか、このピッピはあとでよーく叱っておきますので、何卒ご理解とご協力をお願い致します」なんて謝られたことはありませんよね。僕はありません。

読み込み率100%です。すごいです。ピッピからピクシーに進化させてやりたいくらいです。ダッシュでおつきみやまでつきのいしを拾ってくる勢いです。

そこで、チェックデジットの出番です。 92384781ってバーコードを間違えて72384781って読んでしまっても、そこで「ピッ」とは言わないんです。 グッと我慢して、「こいつのチェックデジット合ってるかな」って確認するんです。

72384781の場合、7+2+3+8+4+7+8=39なのでチェックデジットは39の'一の位'である9ですが、72384781の最後のひとけた目は1になっている。

「であえー！であえー！クセモノだー！！」

となり、ピッピは「てへっ間違えちゃった」とつぶやきながら、正しいバーコードを読むために読み込みを継続するんですね。

なるほどーなるほどー。

最初に考えた人はすごいですねー。

---

ということで、チェックデジット付きのバーコードをランダムに吐き出すHaskellプログラムを書きました。

こわーいこわーいIOモナドの練習です。

「ある関数を同じ引数で呼び出せば、必ず同じ値が返ってくる」という参照透明性を持つHaskellでは、「ランダムな値」というのはクセモノです。 こういうクセモノに対処するには、嫌でもIOモナドと付き合う必要があります。 今回は、

• なるべく汚染されたIOモナドの使用を最小限にして、バーコード生成プログラムを書く
• 無限リストでバーコードを吐き出す

というのを目標にバーコードを生成してみました。

8桁のアルファベットで、チェックデジットにはXORを使用、Oは0と読み間違えやすいので省いています。

感想としては「nub遅ぇ〜！！」「IOモナド難しい..Rubyで書いたらゆるふわ楽勝なのに..」ってかんじですね。 haskellのnubはなんでこんなに遅いのか、オフトゥンの中で考えてみようと思います。

gist8540769

*1:正確なことはのチェックデジット計算方法を御覧ください。

*2:コトバのアヤです。「コーヒー吹いたｗｗｗ」と似たようなものです。

Haskell勉強日誌 -エラなんとかの篩-

練習のため、素数判定で有名なエラなんとかの篩を実装しました。

エラなんとかの篩

13行目のx ^ 2が毎回評価されると実行速度に悪影響を与えそうですが、参照透明性のお陰で１度しか評価されていないハズですね。 reverseはコストが高い処理ですが、１回しか評価されないのでまあ良いでしょう。

primesを無限リストにして、take 100 primesのように書くほうがHaskellっぽい気もしますが、無限リストを返すようにしてしまうと 「篩に書けるのはmaxの平方根まででよい」という恩恵を受けられなくなってしまうため、やめました。