Listで遊ぶ

おはようございます。mt_caretです。

この記事は慶應ロ技研 Advent Calendar 2017 23日目の記事です。遅刻しました。

(追記)空きがあったのでHaskell (その4) Advent Calendar 2017 20日目の記事としてもねじ込みます。

ロボット技術研究会のアドベントカレンダーということでHaskellについての記事です。元々「不変な世界への憧憬」と銘打ってあれこれImmutabilityとそれにまつわるデータ構造に言及しようと思っていましたが、間に合いませんでした。それならとアルゴリズムやらCSっぽいものやらをいくつかHaskellで実装し始めましたが、こちらも間に合いませんでした。他にいいネタも浮かばいのでListでも実装してみましょう。

※このファイルはLiterate Haskellで書かれているのでそのままコンパイル可能です。

型クラスのインスタンスは型シグネチャがあった方が個人的に書きやすいので InstanceSigsを有効にした上で必要なものをimportします。

{-# LANGUAGE InstanceSigs #-}
module List where

import Data.Monoid ((<>))

まずはListの定義です。リストの最後を表すNilと、リストの先頭要素・残りを持つ Consがリストであると定義します(単方向リスト)。例えば1, 2, 3を要素に持つリストを作るにはCons 1 (Cons 2 (Cons 3 Nil))という風にすればいいわけです。

data List a
    = Nil
    | Cons a (List a)
    deriving Show

次にListMonoid型クラスのインスタンスを書きましょう。

instance Monoid (List a) where

モノイドは単位元を持ち結合律を満たす代数的構造です。 Haskellではモノイドの結合操作をmappendあるいは(<>)で表し次の法則が成り立つことが想定されます。

  • 単位元の存在 mempty <> x = x <> mempty = x
  • 結合律 x <> (y <> z) = (x <> y) <> z
  • mconcat = foldr mappend mempty

ここで、結合操作をリスト同士の結合と考えると全ての法則に従いそうです。するとリストの単位元として自然なのは中身が空なリストであるNilですね。

 mempty :: List a
 mempty = Nil

結合操作はリスト同士の結合と書くと、自然と単位元がパターンマッチに出てきます。

 mappend :: List a -> List a -> List a
 mappend Nil bs = bs
 mappend as Nil = as
 mappend (Cons a as) bs = Cons a (as <> bs)

今度はListFunctor型クラスのインスタンスです。

instance Functor List where

HaskellのFunctorに対応するものは関手(functor)と呼ばれ圏から圏への対応付けです。 a -> bな任意の関数fFunctor f => f a -> f bに変換/対応fmapさせます。この時fmapは次の法則に従うように定義する必要があります。

  • fmap id = id
  • fmap (f . g) = fmap f . fmap g

fを各要素に適用するのがリストのFunctorとして自然そうです。ここで、空リストNilのときはfの適用のしようがないのでNilを返していますが法則を満たすためにはこれ以外の挙動はありえない、ということは直感的かと思います。

 fmap :: (a -> b) -> List a -> List b
 fmap _ Nil = Nil
 fmap f (Cons x xs) = Cons (f x) (f <$> xs)
instance Applicative List where

今回はApplicativeの説明を省きます。(c.f. Applicative Programming with Effects

 pure :: a -> List a
 pure x = Cons x Nil

 (<*>) :: List (a -> b) -> List a -> List b
 (Cons f fs) <*> (Cons a as) = Cons (f a) (fs <*> as)
instance Monad List where

いよいよモナドです。モナドの説明はインターネットに無数に転がっているので省くとして(c.f. monad tutorial fallacyHaskellではおおよそ次のように定義されています。

class Applicative m => Monad m where
  return :: a -> m a
  return = pure
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  m >> n = m >>= \_ -> n

returnApplicativepureと同じ操作なのでpureで定義されており、 (>>)(>>=)で定義できるのでApplicativeがあれば(>>=)さえ定義すればモナドが得られます。FunctorfmapMonad(>>=)を比べるとa -> ba -> m bになっていることが分かります。何も考えずに fmap (f :: a -> m b) (x :: m a)をしてしまうとm (m a)となりmが二重になってしまいます。(>>=)の本質は型の特性を上手く利用しm (m a)m aに変換できるような対応付けと解釈できます。(ちなみにm (m a) -> m ajoinと呼ばれておりこれで(>>=)を定義することもできます。)

Monadが満たすべき法則は次の3つです。

  • 左単位元 return a >>= f = f a
  • 右単位元 m >>= return = m
  • 結合律 (m >>= f) >>= g = m >>= (\x -> f x >>= g)

どれもそれはそう、といった感じですね。

 (>>=) :: List a -> (a -> List b) -> List b

前述の通りfmap (f :: a -> List b)をするとList (List b)が得られます。リストのリストをただのリストにするにはどうすればよいのでしょうか。リスト同士を結合するのが自然なのではないか、という考えが浮かびます。結合はMonoid型クラスのインスタンスで既に定義しているのでそれを使いましょう。

 Nil >>= _ = Nil
 (Cons x xs) >>= f = f x <> (xs >>= f)

これでListMonoidFunctorApplicativeMonadインスタンスを定義できました。

最後にリストモナドで少し遊んでから終わりましょう。Haskellのモナドは特別扱いされており、do構文という糖衣構文があります。

main =
    putStrLn "Tell me your name!" >>
    getLine >>= \name ->
    putStrLn ("Hi, " ++ name)

do構文を使うと、上記のようなコードを次のように記述することができます。

main' = do
    putStrLn "Tell me your name!"
    name <- getLine
    putStrLn ("Hi, " ++ name)

ここでputStrLnString -> IO ()getLineIO StringIOはモナドです。 name <- getLineに注目するとこのIO StringStringに変換している処理は getLine >>= \line ->に対応していることがわかります。(>>=)は任意のモナドで使えるので<-をリストで使うとどうなるか見てみましょう。

list1 :: List (Bool, Bool)
list1 = do
    b1 <- Cons True (Cons False Nil)
    b2 <- Cons True (Cons False Nil)
    return (b1, b2)
ghci> list1
Cons (True,True) (Cons (True,False) (Cons (False,True) (Cons (False,False) Nil)))

TrueFalseの組の全通りの組み合わせが得られました。なぜこれが得られるか分からなかったらdo構文の元となるコードに直してみた上でList(>>=)の定義と突き合わせて考えてみましょう。

さて、Listモナドを活用すると綺麗に非決定性計算のシミュレーションを行うことができます。今回は簡単のためNP完全であることで有名な充足可能性問題(SAT) を解くことにします。適当な命題論理式fを次のように立てます。

f :: Bool -> Bool -> Bool -> Bool
f b1 b2 b3 = (not b1 && b2 && b3) || (b1 && not b2 && b3)

fが真になるような(b1, b2, b3)は次のように得られます。

list2 :: List (Bool, Bool, Bool)
list2 = do
    b1 <- Cons True (Cons False Nil)
    b2 <- Cons True (Cons False Nil)
    b3 <- Cons True (Cons False Nil)
    if f b1 b2 b3 then return (b1, b2, b3) else Nil
ghci> list2
Cons (True,False,True) (Cons (False,True,True) Nil)
solve :: List a -> String
solve Nil = "No"
solve (Cons _ _) = "Yes"
ghci> solve list2
"Yes"

参考文献

広告

Listで遊ぶ」への1件のフィードバック

  1. ピンバック: 世界を記述する、エッシャーのタイリング【C++とQtでGUIプログラミング】 | 慶應義塾大学ロボット技術研究会

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中