モナドで家系図探索 - ryamadaのコンピュータ・数学メモ

こちらで父子関係から祖父を探索するHaskell処理を書かれている
モナドを使うらしい
家系図探索に使えそう
Ancestral Recombination Graphにも使えそう
逆に、無限の伝達規則によってつくられる家系図を描いた上で、無限長の疑似乱数列と組み合わせれば、シミュレーションデータも作れる
- 無限長の疑似乱数列を用いているソースの参考サイトはこちら
父系探索してみよう
わざとループにしたりして、むちゃくちゃにする

db :: [(String,String)]
db = [ ("Bob","Dave")
     , ("Dave","Steve")
     , ("Steve","Tony")
     , ("Tony","John")
     , ("John","Bob")
     , ("Bob","Mike")
     , ("Mike","Steve")
     , ("Steve","Ted")
     , ("Ted","Mike")
     ]

lookup' :: [(String,String)] -> String -> Maybe String
lookup' = flip lookup

findGGFather' :: String -> Maybe String
findGGFather' x = (lookup' db x >>= lookup' db) >>= lookup' db

辺の評価はdbへの辺の登録順になっているようだ

*Main> :load "findGGFather.hs"
[1 of 1] Compiling Main             ( findGGFather.hs, interpreted )
Ok, modules loaded: Main.
*Main> findGGFather' "Tony"
Just "Dave"
*Main> findGGFather' "Bob"
Just "Tony"
*Main> findGGFather' "Ted"
Just "Tony"
*Main> findGGFather' "Steve"
Just "Bob"

家系図はグラフなので、家系の形を扱うためには、(この例のような)直線状の探索や、２分岐木の探索(こちらなど)には限界があって、グラフを扱う仕組みが必要になる
- グラフとなれば、(結局)幅有線探索・深さ有線探索などが登場するのだろう
- しかし、まったくよくわかっていないけれども、「グラフ簡約(メモ化)」という、なにやら、グラフになってもHaskell対応できそうな用語もある(こちらやこちら)なので、要、保留