Yet Another Haskell Tutorial 19

8.4.2 Computations

関数の動作が(データの検索のように)失敗する場合のプログラミングを考えてみよう。Haskell ではこのような場合の戻り値には Maybe 型を使う事が多い。そのような関数の例として、グラフの経路を検索するプログラムが YAHT に紹介してある。

まず、グラフのデータ型を考えてみる。(注:グラフとはノードとエッジでできた図形の事だ。一筆書きの図を思い浮かべると分かりやすい。)

data Graph v e = Graph [(Int, v)] [(Int, Int, e)]

Graph タイプコンストラクタは二つの引数をとる。ひとつはノードのラベル(の型)とエッジのラベル(の型)だ。Graph データコンストラクタの第1引数は、ノードの Id (Int 型) とノードのラベルのペアのリストだ。(注:分かりやすく言うと一筆書きのノードを全ての集合だ)第2の引数は、始点のノードの Id と終点の Id とエッジのラベルのトリプルのリストだ。(注:一筆書きの矢印付きの辺の集合)この二つのパラメータで一つのグラフ(一筆書きの図形)は完全に記述できる。

グラフのあるノードから別のノードまでの経路を検索する関数を考えてみよう。このような経路はない場合もある。したがって、戻り値には Mabe 型のデータを使う事にする。経路が存在する場合にはその経路が通過するノードのリストを返すことにする。このような関数 search の例が YAHT に説明してある。この search が実験できるように次のプログラム Graph.hs を作成した。

module Graph where

data Graph v e = Graph [(Int, v)] [(Int, Int, e)]
  deriving Show

diagonal = Graph
  [(1,"A"),(2,"B"),(3,"C"),(4,"D")]
  [(1,2,"a"),(2,3,"b"),(4,3,"c"),(1,4,"d"),(1,3,"e"),(4,2,"f")]

search :: Graph v e -> Int -> Int -> Maybe [Int]
search g@(Graph vl el) src dst
  | src == dst = Just [src]
  | otherwise = search' el
  where
    search' [] = Nothing
    search' ((u,v,_):es)
      | src == u =
        case search g v dst of
          Just p -> Just (u:p)
          Nothing -> search' es
      | otherwise = search' es

diagonal は正方形とその対角線で作ったグラフのデータだ。上のプログラムは ghci の :l コマンドでコンパイルできたので search diagonal 1 3 を実行してみた。正方形の頂点 1 から頂点 3 までの経路の検索だ。

Prelude> :l Graph.hs
[1 of 1] Compiling Graph ( Graph.hs, interpreted )
Ok, modules loaded: Graph.
*Graph> search diagonal 1 3
Just [1,2,3]

Search 関数が何をやっているかを見てみよう。第1引数は Graph 型で、検索するグラフだ。第2引数は経路の始点で、第3引数は経路の終点だ。

まず、経路の始点と終点が同じときは経路のノードはその始点だけだ。関数は始点だけのリストを戻り値として返して終了する。そうでないときは、search' el を使って終点に至るまでの経路のノードを探す事になる。引数の el はエッジのリストだ。

Search' 関数の引数 el が空リストのときは、経路が見つからなかった事を示しているので Nothing が戻り値になる。El が空リストでないときはパターンマッチ ((u,v, _):es) でエッジのリストの先頭の要素をとりだし、エッジの始点を u にバインドし、終点を v にバインドする。エッジのラベルは使わないので _ で読み捨てる。Es はエッジの残りのリストだ。パターンの記述が g@((u,v,_):es) となっているが、g はパターン ((u,v_):es) の別名になる。

Search' の処理はエッジのリストの先頭のエッジについて行われることに注目しておくとソースが読みやすい。Src == u は経路の始点がエッジの始点と同じ場合だ、この場合は search g v dst が実行される。これは、g すなわち、search のパターンで取り出した先頭の要素を含めたエッジのリストから始点が先頭の要素の終点で、終点が目的の経路の終点であるような経路を探す。

Case search g v dst of 1 になっているので、case 文によるパターンマッチは search g v dst の値にたいして行われる。Search 関数が再帰的に用いられているが、このような再帰関数がソースに現れたときは、search g v dst の値が既知のものであると仮定すると読みやすい。Search 関数の戻り値は、始点から終点までのノードのリストだから、search g v dst の戻り値は [v, ... , dst] のような v から dst までの経路を示すノードのリストになる。これが case 文に渡される値になる。

したがって、Just p で経路のリスト p が存在していたときは、始点の u を p の先頭に追加したリストを search' の値として Just (u:p) で返す。そうでないときは、先頭のエッジの始点からの経路に終点が含まれるものがなかった事を示しているので、エッジの残りのリスト es の先頭の要素のエッジについて、検索を続ける。

Search' の引数のエッジリストの先頭の要素(エッジ)の始点が経路の始点と一致していないときは、単に残りのリスト es について検索する。

このアルゴリズムは、検索が失敗したときの情報が Nothing だけだし、最初に発見した経路しか検索できない。また、経路が循環していたときはプログラムが止まらなくなる。しかし、最初のたたき台としてこのアルゴリズムを理解しておく事が重要だ。

YAHT 本文の search2 は Maybe 型の代わりに Failable a 型を用いる事によって、検索が失敗したときの情報を返すようにしている。Prelude では Either a b という標準のデータ型があるが、ここでは自前の Failure a 型を定義してある。Failure 型の定義は次のようになる。

data Failable a = Success a | Fail String

Search2 のアルゴリズムは search のものの直訳になるので、説明は省略する。

同じように search3 は複数の経路について検索して、経路のリスト [[Int]] を返すように改良してあるが、基本的なアルゴリズムは search と同じだ。

これらの search, search2, search3 の3つのプログラムには共通点があり、これをタイプクラスにまとめる事ができる。それは、関数の計算の成功と失敗を戻り値として表現できる事や、成功した二つの結果を結びつける事、成功した複数の値をまとめあげた結果を作る事だ。

このような操作(関数)をまとめたタイプクラス Computation は次のようになる。

class Computation c where
  success :: a -> c a
  failure :: String -> c a
  augment :: c a -> (a -> c b) -> c b
  combine :: c a -> c a -> c a

Computation タイプクラスのインスタンスは c 型(タイプコンストラクタ)で、インスタンスのデータ型のデータには、success, failure, augment, combine の4つの関数を関数適用させる事ができる。

関数 success は a 型のデータひとつを引数にとり、c a 型のデータを返す。failure 関数は、引数に文字列(String)をとり、c a 型の値を返す。combine は2つの c a 型の引数をとり、ca 型の値を返す。argument 関数はやや複雑で、c a 型の値と (a -> c b) 型の関数を引数にとり、c b 型の値を返す。YAHT 本文の例では c a -> (a -> c a) -> c a でも構わないのだが、一般性を持たせるために ca -> (a -> c b) -> c b になっている。

Computation タイプクラス の定義だけでは抽象的なままなので、インスタンスを宣言して4つの関数の実装をしなければならない。そこで、instance キーワードで Maybe 型を Computation タイプクラスのインスタンスに宣言してみる。(関数の部分適用を利用して、success などの関数の a 型の引数は定義から省略してある。)

instance Computation Maybe where
  success = Just
  failure = const Nothing
  augment (Just x) f = f x
  augment Nothing _ = Nothing
  combine Nothing y = y
  combine x _ = x

ところで、Failable a 型は Maybe の Nothing の代わりに、Fail String で失敗の情報を返すように工夫したデータ型だが、基本的には Maybe と同じ使い方をするので、やはり、Computation のインスタンスにする事ができる。

instance Computation Failable where
  success = Success
  failure = Fail
  augment (Success x) f = f x
  augment (Fail s) _ = Fail s
  combine (Fail _) y = y
  combine x _ = x

さらに、全ての経路を検索する場合の戻り値は [[Int]] という Int 型のリストのリストだったから、リスト型 [] も Computation のインスタンスにする事ができる。

instance Computation [] where
  success a = [a]
  failure = const []
  augment l f = concat (map f l)
  combine = (++)

リスト型がインスタンスの場合、success の戻り値は要素が a だけの singleton list だ。Failure は空のリストを返す。combine は二つの success の値になるリストを結合する。augment は第1引数のリストの要素全てに関数 f を関数適用させたリストを返す。

このリスト型を利用したバージョンの search 関数の実行可能なソースを次に示す。search 関数の3つのバージョンに共通した処理は、Computation タイプクラスの関数として記述されており、3つのバージョンに共通する論理構造が分かりやすくなっている。

module Graph2 where

data Graph v e = Graph [(Int, v)] [(Int, Int, e)]
  deriving Show

diagonal = Graph
  [(1,"A"),(2,"B"),(3,"C"),(4,"D")]
  [(1,2,"a"),(2,3,"b"),(4,3,"c"),(1,4,"d"),(1,3,"e"),(4,2,"f")]

class Computation c where
  success :: a -> c a
  failure :: String -> c a
  augment :: c a -> (a -> c b) -> c b
  combine :: c a -> c a -> c a

instance Computation [] where
  success a = [a]
  failure = const []
  augment l f = concat (map f l)
  combine = (++)

searchAll :: Graph v e -> Int -> Int -> [[Int]]
searchAll g@(Graph vl el) src dst
  | src == dst = success [src]
  | otherwise = search' el
  where
    search' [] = failure "no path"
    search' ((u,v,_):es)
      | src == u =
        (searchAll g v dst `augment`
        (success . (u:)))
        `combine` search' es
      | otherwise = search' es

実行例

Prelude> :l Graph2.hs
[1 of 1] Compiling Graph ( Graph2.hs, interpreted )
Ok, modules loaded: Graph.
*Graph> searchAll diagonal 1 3
[[1,2,3],[1,4,3],[1,4,2,3],[1,3]]

このプログラムを理解すれば、Haskell の最も理解が困難で、有用性の高い概念である「モナド」が理解できた事になる。

実際、Computation タイプクラスは Monad タイプクラスとほとんど同じものだ。ただ、Monad タイプクラスでは success は return で、failure は fail で、augment は >>= (bind) だ。combine が モナドにはないが、MonadPlus タイプクラスに現れる。

追記

Computaion タイプクラスを導入する事で驚くべき事がおきる。上のプログラムのリストを Computation のインスタンスにする instance 宣言文を、Maybe を Computation のインスタンスにする instance 宣言文と置き換えると、次のように、ほとんど変更なしで、searchAll :: Graph v e -> Int -> Int -> [[]] 関数を search :: Graph v e -> Int -> Int -> Maybe [Int] 関数に置き換える事ができる。Monad タイプクラスのパワーを感じさせる事例だ。

module Graph3 where

data Graph v e = Graph [(Int, v)] [(Int, Int, e)]
  deriving Show

diagonal = Graph
  [(1,"A"),(2,"B"),(3,"C"),(4,"D")]
  [(1,2,"a"),(2,3,"b"),(4,3,"c"),(1,4,"d"),(1,3,"e"),(4,2,"f")]

class Computation c where
  success :: a -> c a
  failure :: String -> c a
  augment :: c a -> (a -> c b) -> c b
  combine :: c a -> c a -> c a

instance Computation Maybe where
  success = Just
  failure = const Nothing
  augment (Just x) f = f x
  augment Nothing _ = Nothing
  combine Nothing y = y
  combine x _ = x

search :: Graph v e -> Int -> Int -> Maybe [Int]
search g@(Graph vl el) src dst
  | src == dst = success [src]
  | otherwise = search' el
  where
    search' [] = failure "no path"
    search' ((u,v,_):es)
      | src == u =
        (search g v dst `augment`
        (success . (u:)))
        `combine` search' es
      | otherwise = search' es

Prelude> :l Graph3.hs
[1 of 1] Compiling Graph3 ( Graph3.hs, interpreted )
Ok, modules loaded: Graph3.
*Graph3> search diagonal 1 3
Just [1,2,3]

Yet Another Haskell Tutorial 20 へ続く ...
[PR]
by tnomura9 | 2013-02-25 07:56 | Haskell | Comments(0)
<< Yet Another Has... Yet Another Ha... >>