2013/04/30

Haskellで多項間比較演算子

Haskell入門しています.
すごいHaskellたのしく学ぼう! よいですね.最初のほうでHaskellの機能が紹介されていて面白い機能があるんだなあと思ったら,後半でファンクタ,アプリカティブファンクタ,モナドなどが尽くそれらの機能を統一的に説明し,面白い機能とはただの糖衣構文であったということを思い知らされます.まだ読みきっていませんが非常にわかりやすく,かつ引き込まれる内容だと思います.おすすめです.

さて,Schemeでは<が多引数関数となっていて
(< 1 2 3) ; 1<2かつ2<3
のような記述ができるそうです.Haskellに(<)は2引数関数だけど 1 < 2 < 3みたいに書きたいなあ.Haskellに出来ないはずはない(断言).

ひとつには,リストを引数としてそれらが昇順だったらokと言う関数myLTが考えられます.
myLT::[Int]->Bool
myLT = fst . foldl f (True, minBound)
  where f (accBool, accNum) num = if accBool then (accNum<num, num) else (False, num)

myLT [1,3,5] -- True
myLT [1,3,2,4] -- False
アキュムレータを (今のところ昇順かどうか, 直前の値) :: (Bool, Int) として畳み込んでいます.初期値のminBoundはどんな値よりも小さいCのINT_MINのようなものです(本当はJSの-Infinityのほうが真に小さい).
でも,「ファンクタ,アプリカティブファンクタ,モナド等は値を文脈で包むものだ,Maybeは失敗するかもしれないという文脈を表し,リストは結果がどれか1つに決まらない非決定性の文脈を表すものだ」と習いました.要素をリストで渡すのはモナド的にはおかしいのでは?

そこで2つめの実装をしてみました.仮想的には,
1 < 2 < 4 < 3
こんなことがしたいです.モナドでは,
return 値 >>= (値を取り文脈に包まれた値を返す関数) >>= (値を取り文脈に包まれた値を返す関数)...
のように左から右に食わせていくことが出来たので,Maybeのような感じで昇順でない2項を発見した段階でNothingに落とすような流れが考えられます.
data OrderingOrNot a = OutOfOrder | OrderingForNow a deriving (Show)
OutOfOrder .< _ = OutOfOrder
(OrderingForNow a) .< b = if a<b then OrderingForNow b else OutOfOrder

OrderingForNow 1 .< 2 .< 4 -- OrderingForNow 4
OrderingForNow 1 .< 0 .< 4 .< 3 -- OutOfOrder
まずはOrderingOrNotというデータ型を用意していますが,これはMaybeと瓜二つです.今までのところ昇順になっていればOrderingForNowに直前の値が入り,それ以前に照準でない箇所があれば以降はOutOfOrderのみを持ちます.これで仮想的なコードにそっくりな演算子が出来上がりました.
なおMaybeでやっていれば,パターンマッチに失敗した時のfailの実装が「Nothingを返す」なので,2行目がなくて済みます.モナドのインスタンスにしてfailを実装したいところですね.

ところで,この.<ができるOrderingForNowはファンクタ,アプリカティブファンクタ,モナドのどれなのでしょう.それぞれの演算子の型を見比べてみます.
fmap :: (a -> b) -> f a -> f b -- ファンクタ
(<*>) :: f (a -> b) -> f a -> f b -- アプリカティブファンクタ
(>>=) :: m a -> (a -> m b) -> m b -- モナド
(.<) :: Ord a => OrderingOrNot a -> a -> OrderingOrNot a -- OrderingOrNotを送っていく何か
ファンクタは,値から値への関数で,文脈から文脈へ値を送りました.
アプリカティブファンクタは,文脈に入った値から値への関数で,文脈から文脈に値を送りました.
モナドは,値から文脈に入った値への関数で,文脈から文脈に値を送りました.
でも.<は,文脈に入った値と値を使って別の文脈に入った値を作っています.ほかの3つと違って関数を受け取っていません.
多分.<が両側を受け取る関数を吸収してしまっているためで,うまく分離すれば関数と>>=等になって,関数のほうはモナド等になれるのではないかと思います.が,いまいちピンときていません.

また追記すると思います.

4/30 15:00
更に読み進めた所,モナド版畳み込みであるfoldMを知りました.
foldMにより,前者のfoldlを使った実装をタプルではなくモナドの文脈に包むことが出来,より直感的で単純な書き方ができます.
import Control.Monad
myLTM::[Int]->Bool
myLTM = toBool . foldM f minBound  
    where f acc num = if acc<num then Just num else Nothing
          toBool (Just _) = True
          toBool Nothing = False

myLT [1,3,5] -- True
myLT [1,3,2,4] -- False
fが値を文脈に包まれた値に写しています.実にモナドらしいですね.