yunomuのブログ

趣味のこと

アルゴリズム問題

最近、CodeIQというサイトの「今週のアルゴリズム」を解くのが楽しい。元々私はこういうアルゴリズム問題を解くのが非常に苦手なんですが、まあこの「今週のアルゴリズム」の問題は簡単だし。20分とはいえないかもしれないけど1時間もかかんない感じだし。

で、この問題
第2回「今週のアルゴリズム:日付の2進数変換」解説 #ruby|CodeIQ MAGAZINE
日付を例えば2013年12月7日なら20131207という整数値にして、それを2進数に変換して、そのビット列が左右対称になるような日付を、1964年10月10日から2020年7月24日までの間で全て列挙しろ、と。

解き方はおおまかに2種類あって、
(案1) 1964/10/10から日付を加算しながら、数値や2進数に変換して対称の判定をする。
(案2) 左右対称なビット列を列挙して、それぞれが日付として解釈できるかを判定する。

案1の方はまあ簡単です。ああでもHaskellで書いたんで、10進2進変換を自前で書かなきゃいけないのが面倒だった。「日付+1日」というのも無くて、これは+1すればいいだけなので簡単だったんだけど、Rubyにすりゃよかったとちょっと思った。
探索空間は60年分くらいあるのでちょっとアレだが、1年400日としても2万4千個くらいになると見積もった。

案2の方は、左右対称なビット列を作るのが若干面倒だし、Haskellだと文字列を日付として正しいかどうかを判断するのが結構面倒(Data.Time.parseTimeが19656617を平然と1965年12月31日と読んだり。Rubyにすりゃよかった)なので採用しなかったんですが、解説によるとこっちの方が圧倒的に速いらしい。
私の感覚的には10進8桁は30ビット弱くらいだから、左右対称なので半分の15ビット弱くらいになって、まあ3万もいかないだろうけどもどっこいどっこいかなぁと思ったんですが。

本当に簡単だったので案1で5分くらいで書いたと思う。

フィードバックのメールを見ると、アルゴリズム問題なのでできるだけ速い案2で解いて欲しかったと書いてあって、そこまではまあそりゃそうだなんですが、模範解答で「19641010から20200724までは2進数にすると25桁で、12桁と真ん中1桁、12桁も全て1001から始まるので8桁+真ん中1桁の合計9桁、512個の数字を調べればいい」というようなことが書いてあった。
いや、そういうの考えるのが面倒だからコンピュータを使っているんじゃないのか。それにそんなこと言ってたらどこをとっても再利用できないプログラムができてしまうんじゃないか。一般化されてないコードを書くのは苦痛じゃないのか。
と思ったけどもよく考えたら問題文にプログラミングで解決しろとは書いてなかったのでどっちでもよかった。実際過去問見たら手計算で解いてる人もいるみたいだし。

ということでこれはただの自己主張なんですが、私は頭を使うのが面倒なのでコンピュータを使っています。あと、性能より一般化だ。遊びならなおさら。
私はアルゴリズムの高速化問題には向いてないかもしれない。

それはそうと、試しに案2の方も実装してみました。パーサを改造してちゃんとした日付しか読まないようにするのは簡単だったというかパース後の文字列比較で簡単にやった。左右対称なビット列を作るのは意外に面倒でした。小さい順に並べようとすると偶数桁の時と奇数桁の時で分けないといけないし、桁上りのタイミングを見ないといけないし。どうなんだろう。
でもそれらができれば簡単だし、速かった。いやちゃんと測ってないですけど、4倍くらい? 0から20200724までの対称なビット列の数は9027個しかなかった。これだけでも案1の日付数え上げの半分弱くらいで、19641010以上だと137個だから8890個は日付の判定までもいかないから、そりゃ速いわ。

誰か私の代わりにこういうの考える役をやってください。

これコードのネタバレいつまでダメなんでしょうね。

UTCTimeをEqで検査する

UTCTimeが関わるテストをQuickCheckで書こうとしてハマった。

まずUTCTimeをランダム生成するために、UTCTimeをArbitraryのインスタンスにしようとした。
UTCTimeはDayとDiffTimeの組になっていて、DayとDiffTimeはIntegerから作れるし、IntegerはArbitraryのインスタンスなので、UTCTimeのインスタンス化はこんな風に書ける。

instance Arbitrary Day where
    arbitrary = ModifiedJulianDay <$> arbitrary

instance Arbitrary DiffTime where
    arbitrary = secondsToDiffTime <$> arbitrary

instance Arbitrary UTCTime where
    arbitrary = UTCTime <$> arbitrary <*> arbitrary

まあ別にDayとDiffTimeまでインスタンス化する必要は必ずしも無いんですけど。

で、UTCTimeに対してTextとの間で相互に変換する関数があるとする。こういうの。

fromText :: Text -> Maybe UTCTime
toText :: UTCTime -> Text

fromTextは一応Maybeにしておきます。

これをQuickCheckでテストする。

main :: IO ()
main = hspec $ describe "test"
    prop "from/to text" prop_text

prop_text :: Text -> Bool
prop_text a = fromText (toText a) == Just a

このテストが通らないわけだ。
なぜか、prop_textの比較に使われているUTCTimeをshowで表示してみても全く同じなのに、(==)がFalseを返す。なんでや。

よく見るとDayとDiffTimeはIntegerから生成しているので、負の数の場合があり得る。
Dayの場合は0が1858-11-17になってるだけなのでいいんだけど、DiffTimeはUTCTimeの中では0-86400の間で、1日の中の経過秒数を表している。(最後の1秒はうるう秒らしい)
ただし、特にUTCTimeやDiffTimeを作る時にそういう値の制約がかかっているわけでもないので、0-86400の範囲外の整数値からも普通にDiffTimeやUTCTimeを作ることができてしまう。いやDiffTimeの時はいいんだけどUTCTimeを作る時は制約かけてくれよ。

その結果どうなるかというと、こういう感じになる。

Prelude Data.Time> UTCTime (ModifiedJulianDay 0) (secondsToDiffTime 0)
1858-11-17 00:00:00 UTC
Prelude Data.Time> UTCTime (ModifiedJulianDay 1) (secondsToDiffTime $ -86400)
1858-11-17 00:00:00 UTC

で、UTCTimeのEqのインスタンス化がこうなので

instance Eq UTCTime where
	(UTCTime da ta) == (UTCTime db tb) = (da == db) && (ta == tb)

まあ、showの結果が一致しててもこれじゃequalにならないよね。うん。
どうでもいいけどこれだったらderiving Eqでもよかったんじゃないかな。

ということなので、DiffTimeのArbitrary化はこうするとテストが通るようになる。

instance Arbitrary DiffTime where
    arbitrary = secondsToDiffTime <$> choose (0, 60*60*24 - 1)

"-1"は念のため。なくても一応動くんですけどね。

あと、実はDiffTimeは負の値にするとさっきの例のように日付が変わるんですが、増やすと日付が変わらずに時刻だけループする。けども1周しかループしない。

Prelude Data.Time> UTCTime (ModifiedJulianDay 0) (secondsToDiffTime 86400)
1858-11-17 23:59:60 UTC
Prelude Data.Time> UTCTime (ModifiedJulianDay 0) (secondsToDiffTime 86402)
1858-11-17 23:59:62 UTC
Prelude Data.Time> UTCTime (ModifiedJulianDay 0) (secondsToDiffTime 86500)
1858-11-17 23:59:160 UTC
Prelude Data.Time> UTCTime (ModifiedJulianDay 0) (secondsToDiffTime 172800)
1858-11-17 23:59:86460 UTC

なんというか、UTCTimeのデータにDiffTimeを使いまわさない方が良かったんじゃないかなぁ。

DiffTimeに大きな値を突っ込んでも一応UTCTimeは作れるんですが、テストで使うと当たり前ですけどparseでコケますね。

文具トーク

たまにキングジムとかコクヨのサイトを眺める趣味がある。
文具屋では当たり前に便利なものがそろっているんですが、こういうサイトだと新製品とかなんかよくわからないアイテムがあったりして、また違う面白さがあったりします。面白いだけで買ったりとかはしないんですが。

ちょっと面白いもの、「packetta」というやつ。
その場でデータ共有 ワイヤレス共有メモリ「パケッタ」| KINGJIM
PC等からiPhoneとかWiFi対応機器にデータを共有するやつ。アドホックなのかアクセスポイントなのかわかりませんけど、仕組みはわかりやすい。外でデータ授受が頻繁に発生する人には結構便利そうです。プライバシーやセキュリティの色々があるので企業間でそういうことはあまり無いかもしれませんけど。

あと「フィンガープレゼンター黒曜石」
フィンガープレゼンター│コクヨS&T
単に形と名前が面白いだけです。下の方に「コクヨ石(意志)=黒曜石」となんかレベルの高い事も書いてあります。レーザーポインタとの組み合わせとかBLACK OUTボタンとか、色々考えてるなぁと。あんまし広い会場で喋ったこと無いのでよくわかんない。使うの難しそうだ。

というような事をグダグダと想像しながら眺めているんですが、これはこれで記録しておくと面白いかもしれないですね。

ここから先はまたノートの話なんですが、ノートコーナーに測量野帳があった。
測量野帳ブライトカラー - コクヨS&T
測量野帳って、何故か最近ちょっと人気ある気がするんですが、気のせいですかね。普通に手帳として使ったり、日記として使ったりする人が結構いるとか。
そもそも測量する人が使うものなので、丈夫で持ち歩きやすくて外でも書き込みやすいというあたりが人気のようです。私はあまり外でノート使わないし保存もしないのでよくわかりませんけど、丈夫なのはいいですね。
PCで日記書くの面倒になったら使ってみよう。いや、既に結構面倒になってて、iPadで手書きしてますけど。

「エッジタイトル」
エッジタイトル - コクヨS&T
ページの両端にタイトルを書き込むスペースがあるというやつ。こういう風な事を前に試したことがありましたけど、面倒でやめちゃいました。いやこれ結構面倒くさいと思いますよ。話題や日付が変わったらページを変えるくらいやった方が参照もしやすいし、書きやすいんじゃないかなぁ。みたいな話はまた別に記事書きますけども。
仕事がこれだけ細かい単位なら、日記帳とかスケジュール帳を使ったほうがいいんじゃないかなぁ。余白も余白で情報だと思うし。

「文庫本ノート」
文庫本ノート - コクヨS&T
文庫本サイズのノート、やっぱ持ち歩くならこのサイズだろうという感じですね。間違いないです。
持ち歩くということはそれなりに痛むのでブックカバーをつけたくなる。文庫本サイズだと市販品がたくさんあるし、お気に入りのものも使えるかもしれない。そういう用途を想定してペンホルダーがついたのも結構ありますしね。このページでも紹介されてます。
あとインデックス用の罫がついてるのもいい。インデックスつけるのよくやるので、これがやりづらいノートはそもそも使わないし。しおりがついてるのはよくわかんないけど、日記帳にするなら便利かな。
丈夫そうだし。
とはいえ今のところノートを使うのは会社でだけで、社内でもずっと自席に座っているので、今の私には無用の長物かなぁ。もっと忙しくなったら使おう。と思った。まあそうならないようにしよう。いやこれが必要な仕事もそれはそれで楽しいかもしれませんけど。

これが必要な仕事が楽しそうといえば、モレスキンのメモポケットってのがありますね。
MOLESKINE モレスキン メモポケット
メモを挟むやつ。楽しそうというか、これが必要な仕事って何なんだろうと。
これ何を入れるんだろう。メモとか名刺とかかな。名刺はわかるけども、メモってなんだ。
おそらくこれはシステム手帳の変形なんじゃないかと思うんですが、どんなもんなんでしょうね。テーマで分けるんだったら別にシステム手帳でいいので、頻繁に人とやりとりするとか。名刺を表紙にしてメモを入れるとして、同時に6団体と仕事ができる。たぶんシステム手帳と組み合わせて、こまめに母艦に情報を移しながら戦う感じになると思うんですが、フリーランスの人とかかな主に使うのは。どういう艦隊を組むのかちょっと興味ある。

「PARACURUNO(パラクルノ)」
PARACURUNO[パラクルノ] - コクヨS&T
側面が斜めにカットされていてめくりやすいらしい。アイデア商品ですね。いかにもコクヨらしい。
これも時系列の、日記に良さそうかも。これもA6文庫本サイズですね。いいんですが、私はあんまし過去のメモを見返したり探したりしないので、形は普通のがいいかなぁ。でも日記だったら使いたいかな。A5があったらちょっと使ってみたい。

こんなの考えてるだけで余裕で1日つぶせたりするのでモンハンは進みません。

Haskellで可変長引数

可変長引数を作りたかったわけではないんだけど、というか何がしたかったんだかよく覚えていないんだけど、こういうのを作った。

class Test a where
    test :: a -> Int 
    test = const 0

instance Test a => Test (b -> a) where
    test f = 1 + test (f undefined)

instance Test Int 

Test型クラス。

> let c = undefined :: Int
> test c
0
> let f = undefined :: Int -> Int
> test f
1
> let g = undefined :: Int -> Int -> Int
> test g
2

test関数に与えた関数の引数の数を数えられます。
ただし、与える関数の戻り値の型がTestのインスタンスになっていないと使えません。

これ、なんとなく面白くはあるんだけど、何の意味があるんだ。使い所もよくわかんなくなっちゃったなぁなんて思っていたんですが、printfがこの仕組で作られていました。
http://hackage.haskell.org/package/base-4.6.0.1/docs/Text-Printf.html
うわあああこれprintfじゃないか!
あとQuickCheckのpropというかTestableクラスも思いっきりこの仕組で実装されていました。
http://hackage.haskell.org/package/hspec-1.7.2.1/docs/Test-Hspec-QuickCheck.html
http://hackage.haskell.org/package/QuickCheck-2.6/docs/Test-QuickCheck-Property.html#t:Testable
誰だ使い所無いとか言ったやつ。

特にQuickCheckなんて最近も使ってるし、なんで疑問に思わなかったのか。これ作った人頭いいな。

まあそれはいいとして、

class Arg a where
    f :: c -> a

みたいな型クラスを定義して、

instance Arg a => Arg (b -> a) where
    f = ...

みたいなインスタンスを作ると可変長引数関数が作れるみたいです。
(b -> a)がArgのインスタンスなら(d -> b -> a)というか(d -> (b -> a))もArgのインスタンスになるので。

io-streams

そろそろio-streamsで遊んでみよう。いや遊んでたのは実のところ随分前なんですけど。
http://hackage.haskell.org/package/io-streams

io-streamsというのはHaskellのストリーム処理ライブラリの一つで、シンプルなのが売りなのかな。
ストリーム処理には私はよくconduitを使っていますけど、conduitと比べるとなんというか、本当にシンプルで使い勝手がいいです。
まずはHelloWorld的に、猫のようなもの。

import System.IO.Streams

main :: IO ()
main = stdin `connect` stdout

ここで出てくるstdinとstdoutはSystem.IO.Streams.Handleに定義されてるもので、それぞれこんな感じになってる。

stdin :: InputStream ByteString
stdout :: OutputStream ByteString

で、connectはSystem.IO.Streamsに定義されてて、こんな感じ。

connect :: InputStream a -> OputputStream a -> IO ()

標準入力からの入力ストリーム(InputStream)を標準出力への出力ストリーム(OutputStream)に接続(connect)しているというだけ。

System.IO.Streams.HandleにあるhandleToInputStream/handleToOutputStreamを使って書き直すとこんな感じ。

import System.IO (stdin, stdout)
import System.IO.Streams hiding (stdin, stdout)

main :: IO ()
main = do
    is <- handleToInputStream stdin
    os <- handleToOutputStream stdout
    is `connect` os

ついでにHandleで書くとこんな感じ。

import System.IO

main :: IO ()
main = do
    c <- hGetChar stdin
    hPutChar stdout c
    main

HandleToStreamと同じようにStreamToHandle系の関数もあるのでなんとなくストリームとIOハンドルは同じものなんだなぁというのがわかりますね。どうでもいいですけど。

ファイルから読むのはwithFileAsInput/withFileAsOutputというのがあって、withFileと同じような雰囲気で使えます。

% cat data.txt
abc
def
ghc

みたいなファイルがあったとして

import System.IO.Streams

main :: IO ()
main = withFileAsInput "data.txt" $ \is -> is `connect` stdout
    -- > "abc\ndef\nghc\n"

ファイルの中身を吐き出すだけのプログラムができる。中身はおそらくwithFileとhandleToInputStreamを組み合わせただけであろう。

System.IO.Streams.Listにはストリームをリストにしたりリストをストリームにしたりする処理が色々入っていて、おそらくよく使うのはtoListなんじゃないかなぁ。

import System.IO.Streams

main :: IO ()
main = withFileAsInput "data.txt" $ \is -> do
    as <- toList is
    print as
    -- > ["abc\ndef\nghc\n"]

なんかあんまし嬉しくなかった。ストリームの一番ベースとなるデータ構造ByteStringには区切りが無いのでまあこうなるよね。
System.IO.Streams.ByteStringにはlinesという改行ごとにByteStringを区切る関数があって、まあData.List.linesとだいたい同じように動きます。

import Prelude hiding (lines)
import System.IO.Streams

main :: IO ()
main = withFileAsInput "data.txt" $ \is -> do
    ls <- lines is
    as <- toList ls
    print as
    -- > ["abc", "def", "ghc", ""]

最後改行で終わってるからなんかゴミ入ってますけど、これで意図通り。isはただのバイト列のストリームですが、lsはバイト列のリストのストリームになっています。わかりづらいですが。
InputStream/OutputStreamはMonadじゃないけど、linesとかtoListとかがIOなのでdoで連結できるし、printとかとも簡単に連携できて良い感じです。それはそうと今MBAのキーボードに水をこぼしてAのキーがすごくききづらくなりました。
bindで書くとちょっといい感じに。

main = withFileAsInput "data.txt" $ lines >=> toList >=> print
    -- > ["abc", "def", "ghc", ""]

別にconnectしなくてもデータ取り出せるのがなんかお手軽な気がします。ここではtoListがconnect相当をやってるんですけどね。

toList :: InputStream a -> IO [a]

モナドトランスフォーマーとか使わないでいいのが良いと思います。

InputStreamにはread/unRead/peekがある。conduitでいうところのawait/leftoverみたいなものです。conduitにpeek相当ってあったっけ?

{-# LANGUAGE OverloadedStrings #-}
import Prelude hiding (lines, read)
import Data.ByteString.Char8 ()
import System.IO.Streams

main :: IO ()
main = withFileAsInput "data.txt" $ \is -> do
    ls <- lines is
    a1 <- read ls
    print a1 -- > Just "abc"
    unRead "xyz" ls
    a2 <- peek ls
    print a2 -- > Just "xyz"
    as <- toList ls
    print as -- > ["xyz", "def", "ghc", ""]
    a3 <- read ls
    print a3 -- > Nothing

readはストリームを消費するけどpeekは消費しない。unReadは本来は一度読んだデータを読まなかった事にする関数だけど、型が合ってれば別になんでも詰め直せる。で、toListはストリームを全部消費するのでその後に何か読もうとしても読めない。
一方、writeはデータをOutputStreamに書き出すだけです。conduitのyieldとは全然違う。

あと/dev/nullみたいなnullInput/nullOutputみたいなのもあります。nullOutputはまあいいとして、nullInputはunReadと組み合わせてスタックみたいに使えそうですね。いやそんなのリスト使えって感じですね。

データ変換、conduitでいうところのConduit相当のものは、単に

f :: InputStream a -> InputStream b

みたいな関数を作ってやればいいだけみたいなんですが、えっとこれどうやって作るんだ。みたいになりますが、おそらくそういう時のためにGeneratorというのがあります。GeneratorはInputStreamを作るための機能のようですが、こいつはMonadでMonadIOなのでInputStreamの変換にも使いやすそうです。おい、結局モナドトランスフォーマー使ってるじゃないか。

ためしに

data Member = Member ByteString deriving (Show)
f :: InputStream ByteString -> IO (InputStream Member)

みたいな関数fを作ってみるとすると、

{-# LANGUAGE OverloadedStrings #-}
import Control.Monad.IO.Class (liftIO)
import Data.ByteString (ByteString)
import Data.ByteString.Char8 ()
import Prelude hiding (lines, read)
import System.IO.Streams

data Member = Member ByteString deriving (Show)
f :: InputStream ByteString -> IO (InputStream Member)
f = fromGenerator . g

g :: InputStream ByteString -> Generator Member ()
g is = do
    ma <- liftIO $ read is
    case ma of
        Nothing -> return ()
        Just a  -> do
            yield (Member a)
            g is

main :: IO ()
main = withFileAsInput "data.txt" $ \is -> do
    ls <- lines is
    ms <- f ls
    toList ms >>= print
    -- > [Member "abc", Member "def", Member "ghc", Member ""]

gなんて関数が増えちゃいましたけど、だいたいこんな感じ? Generator部分(g関数)はあんましConduitと変わりませんね。一旦Generatorを返す関数を作らないと、データの繰り返し処理ができなくなる。というのもだいたいConduitと同じ。

ということでio-stream結構いいんじゃないでしょうか。
周辺ライブラリの充実度でconduitに見劣りするのもの、インタフェースが簡素で他との連携もやりやすいので、頑張ればなんとかなるんじゃないでしょうか。Networkとかattoparsecなんかは最初から入ってるから、頑張って作ろう。

とここまで書いたところでチュートリアルの存在に気づきました。Tutorialってモジュールがある……。
System.IO.Streams.Tutorial

今回作ったソースはここです。
exercises/streams at master · yunomu/exercises · GitHub

スタイラスペンとブギーボードの話

iPad用に静電気タイプのスタイラスペンを買って使ってみてますけど、ここまで書いた段階でもういいやって感じです。参ったな高かったのに。
http://www.princeton.co.jp/product/digitalaudio/psatpa1.html

電源入れないと書けないので電池を気にしなきゃいけないのが一番のネックかなぁと思っていましたけど、その点はまあそんなに使うわけじゃないし、単6電池1本で140時間連続で使えるとのことなのであんまし問題は無いかもしれません。ただ文字の書き心地が著しく悪いので私には使えませんでした。
ペンの形状はいいのでもったいない感じはあるんですが、たぶんその形がいいのと感度が良すぎるのが災いして、文字が書けない。

前に買ったBambooのスタイラスペン(http://www.wacom.com/jp/ja/everyday/bamboo-stylus-solo)と比べると、長いしペン先が細いしでとても持ちやすいんですが、それゆえについ少しペンを寝かせてしまうので、接地の位置が思ったよりかなり手前にきてしまうという。普通のペンならペン先の頂点あたりからインクが出ますけど、ペン先の根本の部分からインクが出る感じになってしまって、それで字が書けるわけがない。いや、私がペンを寝せて書く癖があるからなので、もしかしたらシャーペンやボールペンを普段使う人は大丈夫なのかもしれませんけど。

Bambooのやつはペン先が太いので逆にそんなことはなく、快適に書けるんですが。
何事も吊り合いとかバランスとか適材適所とか、そういう感じですね。

ところで最近は家電量販店の文具コーナーに結構面白いものが色々ありますね。
というかキングジムが面白いですね。

ブギーボードというやつ。
http://www.kingjim.co.jp/sp/boogieboard/
電子メモのようなもので、適当な棒とか爪とかで引っ掻くと書ける。書いた線はeraceボタンで全消しできる。部分的には消せない。電池交換はできないけど、内部電池が切れるまで5万回程度書けるらしい。
「アイデアメモに!」って書いてあったけど、この仕様だとアイデアメモには使いづらいんじゃないかなぁと思います。
ああでも私が見たのは型番BB-1Nという一番小さくて単機能なやつだったんですが、上位モデルになると保存とかUSBでのデータ転送とか充電とかできるんですね。それならメモとして使えそうですね。

大きさはiPad miniと同じくらい。用途は人に見せるための連絡用ボードみたいな感じでしょうか。「冷凍庫にカレーが入ってます」みたいなの。
ペンが自由なのがいいですね。消しゴムが無いというのも、このサイズならあまり問題にならないんじゃないでしょうか。もう少し大きかったら複数の情報を書くようになるから全消しのコストが高くなる。そうすると部分的に消せる消しゴム機能がほしくなって、全体的になんか使いづらいアイテムになると思う。
少し大きくて消しゴム機能があったらプレゼンテーションの道具になりますね。ホワイトボードでいいじゃん。
バランス大事ですね。

なので私が使うとしたら、やっぱり伝言メモにする感じですかね。この場合は、電池交換できない書き換え5万回というのも特に問題にならないし、3千〜4千円くらいの値段もまあまあまずまずといったところなんじゃないでしょうか。
まあ私が実際に使う場面は無さそうなんですけどね。
こういうの想像するのが楽しいんじゃないですか。

JavaコードをHaskellで書きなおすのに手こずった話

「続・アルゴリズムを学ぼう」が発売されて、校正をほんのちょっと手伝ったお礼かなんかで発売された本を頂きまして、ぼちぼち読んだりしています。
前作に比べて使いやすいというか、親しみやすいネタが多くて面白いですね。
「続・アルゴリズムを学ぼう」http://www.amazon.co.jp/dp/4048913948/

で、ちょっと暇つぶしに「続・アルゴリズムを学ぼう」に載ってるリバーシHaskellで実装してみました。
https://github.com/yunomu/exercises/tree/master/reversi

この本に載っているプログラム例はJavaで書かれているので、要はJavaHaskellで書きなおすという作業をしたような感じになりました。

前になんか勘違いしていた話

JavaHaskellといえば、前に社内で"Types and Programming Languages"の読書会をやろうって話になった時にこんな事を言っている。

ここで言う型クラスというのはHaskellの型クラスのことで、見た目は割と似ていますよね。似てるんじゃないかな。
例えばEqとか、

class Eq a where
    (==) :: a -> a -> Bool
    (/=) :: a -> a -> Bool

ってなってて、いかにもインタフェースを定義している感じ。こういう振る舞いをするデータを作りたかったら、データ型を作ってこの型クラスのインスタンスにすればいいんじゃないかなと思う。
まあやってみると全然違うんですが。

Javaのinterfaceは型だけども、Haskellの型クラスは型ではないので、Javaのinterfaceみたいなノリで型クラスを使うと、徐々に無理が出てきて後悔することになる。

class ToInt a where
    toInt :: a -> Int

instance ToInt Int where
    toInt = id

instance ToInt Char where
    toInt = const (-1)

みたいな型クラスがあったとして

f :: ToInt a => [a] -> [Int]
f = map . toInt

a = f [2, 'a']

みたいなことはできない。リスト内の型が違うから。

b = [toInt 2, toInt 'a']

これはできる。まあ、そりゃできる。
こうしてみれば当たり前なんだけど、toInt関数の扱い方に気をつけなきゃいけないのでそれなりに面倒な場面が増えてくるというか、感覚的には「同じtoIntって関数が使えるんだから同じように扱えてもいいじゃん」って思うんだけど、シンボルというか名前が同じでもChar型のtoIntとInt型のtoIntは別物なので、別物として扱いましょう。
同じ型クラスならリストに入れられるようにしようみたいな話もどっかにあった気もしますが。

型クラスはやっぱりShowみたいに型によって処理を振り分けたい時に使うのが良さそうですね。
インタフェースが同じなら素直に同じ型にしましょう。

継承やコンストラクタやインタフェース定義

Haskellの型定義にはJavaの継承とかコンストラクタみたいなものはなくて、メソッドもなくて、どうするのこれってなります。
ならないなら幸せです。人やコードによってはならないんじゃないかな。
本ではプレイヤーをこんな風に定義してる。

public abstract class Player {
    protected final Turn turn;
    protected Player(Turn turn) {
        this.turn = turn;
    }
    public Turn getTurn() {
        return turn;
    }
    public abstract Position play(Board board);
}
public class HumanPlayer extends Player {
    ...
}

抽象クラスの`Player`を定義して、それを継承してHumanPlayerとかSimpleAIPlayerとかを作ってる。
これはそのままだとHaskellに変換できないんだけど、よく考えれば具象クラスが要らないだけだったりする。コンストラクタの代わりに初期化関数を作る。

data Player = Player
    { playerTurn :: Turn
    , playerPlay :: Board -> Player -> IO (Maybe Position, Player)
    }

initHumanPlayer :: Turn -> Player
initHumanPlayer t = Player t humanPlay

humanPlay :: Board -> Player -> IO (Maybe Position, Player)
humanPlay = ...

Java風に言うと、テンプレートメソッドパターンがストラテジーパターンになってる。というかJavaでもこう書けよという気がしてくる。抽象クラスがいいのかストラテジーがいいのかはここでは微妙なところかもしれないけど。

戻り値の型

Javaのplayメソッドのシグネチャはこうなってるけど

    public abstract Position play(Board board);

Haskellのplayの型はこうなってる。

playerPlay :: Board -> Player -> IO (Maybe Position, Player)

このインタフェースはちょっと悩んだんですけど、

  • Playerの内部状態を使うかもしれないから引数にPlayerが必要
  • Playerの内部状態を更新するかもしれないから戻り値にPlayerが必要
  • Positionが決まらない場合があるからMaybe Position(元プログラムではnullを返している)
  • ユーザの入力や乱数を利用して手を決めるかもしれないからIO

という感じで決めました。
SimpleAIPlayerだとIOが要らないし、HumanPlayerだとMaybeが要らないし、もっと後の方になるまで戻り値のPlayerが要らなかったりするので、ここは先見性が試されるというか、3回くらい書き直しました。

IOが必要かどうか、値が存在しない場合があるかどうか、このあたりを最初から慎重に設計してなきゃいけないけども、このあたりは結構難しいところだったと思います。機能追加の度に共通部分を書き直す羽目になりました。よく考えれば自明なんですけど、Javaのメソッドは基本的に副作用があるというのは忘れがちな気がします。

そんなこんなで、暇だからAI作って遊び相手になってもらおうと思って書き始めたものの、案外面倒くさくて、ここまで書き終わる頃には新幹線が目的地に着いてしまったという。それはそれで良い暇つぶしにはなりましたけど。