cabal hellから抜け出したくてあがいた話

「cabalでパッケージをインストールする際、依存の解消がイマイチでハマりがち」という噂が流れているのは知っていた。

自分が遭遇するまでは「ふーん」と右から左であった。

仔細は省略するが、このたび見事にハマり、cabal hellを目の当たりにした。

熟練Haskellerであれば「こんなのは地獄のうちに入らぬわ！」などと高笑いするかもしれないが、初心者にとっては「面白そうなパッケージ試してみようと思ったらエラーが...解消しようと思ったらまたエラーが...エラー...エラー...」という終わりの見えない状況は十分に地獄と呼んでよいのではないか。

環境: Mac OSX 10.9.2

Haskell Platformのアンインストール

ここらへんを参考に、ghcもcabalもない、古き良き時代に戻る。

もう入れなおしだー！ % which ghc ghc not found % which cabal cabal not found

— 定食屋 おろポン (@oroponya) 2014, 4月 7

身も心もすっきりする。

GHCのインストール

参考: 2013年8月現在のHaskell開発環境 - maoeのブログ

Haskell Platformを使わない利点は、バージョンが固定されるパッケージが少ないので依存関係でこけることが減ること。

とのことなので、Haskell Platformを使わずインストールすることにする。

GHC: Download version 7.6.3 からGHC7.6.3のバイナリを落とし、インストール。

ちなみにニュービーな僕は「GHCのバージョンを一発で切り替えたい」などと欲をかかず、大人しく/usr/local/ghc/ghc-7.6.3/binにパスを通した。 それ以外は、概ね上記サイトの通りである。

Cabalのインストール

参考: An Introduction to Cabal sandboxes

「とりあえずcabal sandbox使っとけ」ということなので、githubのCabalをインストールする。

If you have used Haskell for some time, you’ve probably heard the expression “Cabal hell”. It refers to the fact that installing a new package with cabal install can break existing packages on your system.

すなわち。

もしもHaskellを何度か使ったことさえあれば、"Cabal hell"なる言葉を聞き及んだことがあろう。これは、新しいパッケージをインストールするために黒い画面に打ち込んだcabal installが既存パッケージをぶっ壊す恐ろしい現象を指す言葉である。

さて。

「GHCしか入ってないならこうやれよ」と仰せなので以下のコードを逐一実行してみる。

$ git clone git://github.com/haskell/cabal.git /path/to/cabal
$ cd /path/to/cabal/Cabal
$ runhaskell Setup.hs configure
$ runhaskell Setup.hs build
$ runhaskell Setup.hs install
$ cd ../cabal-install
$ sh bootstrap.sh

と、sh bootstrap.shでこんなエラーが出て失敗する。

Data/Text.hs:1213:42:
     warning: missing terminating ' character [-Winvalid-pp-token]
-- In (unlikely) bad cases, this function's time complexity degrades

ここらへん を覗くと、gcc4.7を使うと解決するようだ。gcc48もgcc49もあるけど、gcc47なら出来るっていうんだからそうしてやろうじゃないか。 仕方ないので、4.7を入れてやる。

時間がかかるので、しばらく正座して待つ。

gccコマンドがgcc47を参照するよう変更した後、再びsh bootstrap.shを行う。

The 'cabal' program has been installed in /Users/shogo/.cabal/bin/

めでたい。

使ってみる

「WAFが使えればもう大丈夫でしょう」という安易な発想から、 Making A Website With Haskell - adit.io を参考に Scottyを入れてみる。

さっそくcabal installで失敗する。世知辛い。

Resolving dependencies...
cabal: Could not resolve dependencies:
trying: todo-0.0.1 (user goal)
next goal: wai-extra (dependency of todo-0.0.1)
Dependency tree exhaustively searched.
Motoko% cabal update
Downloading the latest package list from hackage.haskell.org
Motoko% cabal install
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: todo-0.0.1 (user goal)
trying: wai-extra-2.1.1.1 (dependency of todo-0.0.1)
trying: conduit-1.1.0 (dependency of wai-extra-2.1.1.1)
next goal: monad-logger (dependency of todo-0.0.1)
rejecting: monad-logger-0.3.4.1, 0.3.4.0, 0.3.3.2, 0.3.3.1, 0.3.3.0, 0.3.2.0,
0.3.1.1, 0.3.1, 0.3.0.1 (conflict: todo => monad-logger==0.3.0)
rejecting: monad-logger-0.3.0 (conflict: conduit==1.1.0, monad-logger =>
conduit>=1.0 && <1.1)
rejecting: monad-logger-0.2.4, 0.2.3.2, 0.2.3.1, 0.2.3, 0.2.2, 0.2.1, 0.2.0.1,
0.2.0 (conflict: todo => monad-logger==0.3.0)
Backjump limit reached (change with --max-backjumps).

Backjumpがlimitに達して失敗したようだ。依存関係の解消ができなくて失敗してたら心を折って、ついでにHHKBも２つにぶち折っているところだった。

--max-backjumpsだが、cabal install --helpによると、「とりあえず-1にしとけ」と読み取れる。

    --max-backjumps=NUM             Maximum number of backjumps allowed while
                                    solving (default: 200). Use a negative
                                    number to enable unlimited backtracking.
                                    Use 0 to disable backtracking completely.

cabal install --max-backjumps=-1でリトライする。。も失敗。

.
.
.
Installed persistent-sqlite-1.3.0.5
cabal: Error: some packages failed to install:
persistent-postgresql-1.3.0.5 depends on postgresql-libpq-0.9.0.0 which failed
to install.
postgresql-libpq-0.9.0.0 failed during the configure step. The exception was:
ExitFailure 1
postgresql-simple-0.4.2.1 depends on postgresql-libpq-0.9.0.0 which failed to
install.
todo-0.0.1 depends on postgresql-libpq-0.9.0.0 which failed to install.

めげずに個別にインストールをしてみる。 cabal install postgresql-libpq-0.9.0.0を行うと、setup: The program 'pg_config' is required but it could not be found.とのことなので、pg_configを入れる。

Homebrewからインストール。すぐ終わる。

% brew install postgresql
% which pg_config
/usr/local/bin/pg_config

これによって、cabal install postgresql-libpq-0.9.0.0が成功するため、もう一度cabal install --max-backjumps=-1を行ってみる。

...成功！

.
.
.
Configuring todo-0.0.1...
Building todo-0.0.1...
Installed todo-0.0.1

世界にこんにちはできたので、寝る。

Ninety-Nine Haskell Problems 解いてみた

H-99: Ninety-Nine Haskell Problems - HaskellWiki
99 questions/1 to 10 - HaskellWiki

とりあえず1-10問目まで。 Preludeなどのライブラリ関数になるべく依存しない縛りで解いてみた。 そのため、myLastを書くのにhead', reverse', fold', flip'を書くことになった。

20問目までは飛ばしてもよかったかも。

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

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

バーコードのチェックサムと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の平方根まででよい」という恩恵を受けられなくなってしまうため、やめました。

Haskell勉強日誌 -RPN電卓-

Haskellで逆ポーランド記法電卓。関数型言語らしい題材で練習してみる。

まずは普通に書いてみる。

最初は、Stackを定義してpopやpushを実装するべきかと考えたけど、強力なパターンマッチのおかげでシンプルに書けた。

単なるリストをスタックとして使用している。

---

流れとしては、初期値の空リストを渡して、要素を順に処理していくかたちになる。 これは典型的な畳込み演算と言えそうだ。

foldで書き直せそうなので、書きなおしてみる。

大変シンプルでよろしい。