Haskell Quiz No.5

難易度: λλ

以下の Conduit を使ったコードの実行結果を予想してみてください!

#!/usr/bin/env stack
-- stack script --resolver lts-11.0
import Conduit

sink :: Monad m => ConduitM Int o m (String, Int)
sink = do
  x <- takeC 5 .| mapC show .| foldC
  y <- sumC
  return (x, y)

main :: IO ()
main = do
  let res = runConduitPure $ yieldMany [1..10] .| sink
  print res

答えは次回

はじめに

前回の問題と答えは以下の通りです。

問題

難易度: λ

今回は、与えられた値がリストのリストに含まれているかどうかを判定する問題です。

幅優先で探索する関数 bfs と深さ優先で探索する関数 dfs をそれぞれ定義してみましょう。

bfs :: Int -> [[Int]] -> Bool
bfs = undefined

dfs :: Int -> [[Int]] -> Bool
dfs = undefined

実行結果はだいたいこんな感じです。

$ stack repl -- Quiz4.hs
*Quiz4> xs = [[10..],[4,5,6],[7,8,9]]
*Quiz4> bfs 9 xs
True
*Quiz4> dfs 9 xs
.....

こたえ

素晴らしい回答が Haskeller から届きました。(一部修正)

dfs x = elem x . concat
bfs x = elem x . concat . transpose

まさに Haskell !!!って感じのコードですよね。

Haskell Quiz No.4 の解説

完全なコードはこちら

module Quiz4 where

import Data.List (transpose)

dfs :: Eq a => a -> [[a]] -> Bool
dfs x = elem x . concat

bfs :: Eq a => a -> [[a]] -> Bool
bfs x = elem x . concat . transpose
  • dfsdepth farst search なので、深さ優先探索を行うように実装しています。
  • bfsbreadth first search なので、幅優先探索を行うように実装しています。

Data.List モジュール

リスト操作系の関数は基本的に Data.List を探せば見つかります。

Prelude に含まれている関数と重複するものもありますが、それ以外にも有用な関数がいくつも定義されているため、 Data.List モジュールにどんな関数があるか把握しておくと良いと思います。

ここで定義されている関数の命名規則は別のパッケージでも慣習的に利用されていることが多いため、関数がどんな操作なのか理解 (暗記ではない) しておくと、全く知らないパッケージでも何となく読める時があります。

例えば今回の transpose 関数は Data.List 以外にも色々なモジュールで同様に定義されています。

つまり、データ構造はリストとは違うけども、操作としては同じと言うことです。

transpose

transposebase パッケージの Data.List で定義されています。Prelude には含まれていないため、明示的に import する必要があります。

haddock の説明通り、リストを転置させる関数です。

>>> transpose [[1,2,3],[4,5,6]]
[[1,4],[2,5],[3,6]]

>>> transpose [[10,11],[20],[],[30,31,32]]
[[10,20,30],[11,31],[32]]

その際、空リストは取り除かれるようですね。

transpose 関数の実装は Data.OldList で以下のように定義されています。

transpose :: [[a]] -> [[a]]
transpose []           = []
transpose ([]:xss)     = transpose xss
transpose ((x:xs):xss) = (x : [h | (h:_) <- xss]) : transpose (xs : [ t | (_:t) <- xss])

たしかに2つ目の等式で空白が除去されていることがわかりますね。

3つ目の等式は少し複雑ですが、面白いので見てみましょう。

それぞれのリストの head を取りたいので map head xss がすぐに思いつきそうですが [h | (h:_) <- xss] となっています。うまいやりかたですね。

普通に head をかけてしまうと空リストで実行時エラーとなってしまいます。

*Quiz4> xss = [[1,2],[],[3,4]]
*Quiz4> map head xss
[1,*** Exception: Prelude.head: empty list

しかし [h | (h:_) <- xss] ではどうでしょうか?

*Quiz4> xss = [[1,2],[],[3,4]]
*Quiz4> [h | (h:_) <- xss]
[1,3]

はい。空リストを含んでいたとしてもエラーにならずに、良い感じに先頭の要素から成るリストが生成できました。

では、なぜこのような動作になるのでしょうか?

それを理解するためには Haskell 2010 Language Report3.11 List Comprehensions を参照する必要があります。

ここにリスト内包表記がどのように変換されるか、変換規則が載っています。(ここでは一部のみ掲載)

-- ルール1
[ e | True ] = [e]

-- ルール2
[ e | q ] = [ e | q, True ]

-- ルール3
[ e | p <- l, Q ] = let ok p = [ e | Q ]
                        ok _ = []
                    in concatMap ok l

上記の規則により、先程の [h | (h:_) <- xss] は以下のように変換できます。

[ h | (h:_) <- xss ]
  = { ルール2 より }
[ h | (h:_) <- xss, True ]
  = { ルール3 より }
let ok (h:_) = [ h | True ]
    ok _ = []
in concatMap ok xss
  = { ルール1 より }
let ok (h:_) = [h]
    ok _ = []
in concatMap ok xss

最終的には f = [h | (h:_) <- xss] とすると

f = concatMap ok xss
  where
    ok (h:_) = [h]
    ok _     = []

になります。

パターンマッチに失敗した場合は ok _ = [] ということで自動的に空リストになるという部分が実行時エラーにならない秘密のようですね。

最終的に concatMap によって、空リストが自然に除去されていることがわかります。

*Quiz4> concatMap ok [[1,2], [], [3,4]]
[1,2,3,4]

ということで、もとの式に戻ると transpose 関数の主張はこういうことです。

transpose 関数の処理
transpose []           = []
transpose ([]:xss)     = transpose xss
transpose ((x:xs):xss) = (x : [h | (h:_) <- xss]) : transpose (xs : [ t | (_:t) <- xss])

幅優先探索と深さ優先探索

アルゴリズムの本などを読むと、必ずこの 幅優先探索深さ優先探索 というキーワードを目にすると思います。(また、同時に説明に利用されるのは木構造のデータでしょう)

幅優先探索と深さ優先探索の概念を理解するために木構造に触れる必要は無く、リストだけで十分です。

本質は以下のように凄く簡単なことです。

リストを使った幅優先探索と深さ優先探索

そのため [10..] のような無限リストが与えられた場合に 深さ優先探索 では結果を返すことができないのです。

$ stack repl -- Quiz4.hs
*Quiz4> xs = [[10..],[4,5,6],[7,8,9]]
*Quiz4> bfs 9 xs
True
*Quiz4> dfs 9 xs
.....

コードの解説

dfsconcat によってリストのリストを直列につないだ結果に対して elem x で要素を検索すれば良いということになります。

dfs :: Eq a => a -> [[a]] -> Bool
dfs x = elem x . concat

それに対して bfs は各リストの先頭要素だけを先に処理していく必要があります。自分でその辺りの処理を書いても良いのですが transpose で一発です。

bfs :: Eq a => a -> [[a]] -> Bool
bfs x = elem x . concat . transpose

bfs はこのように書くこともできます。

bfs :: Eq a => a -> [[a]] -> Bool
bfs x = dfs x . transpose

つまり、リストのリストのようなデータ構造に対して幅優先探索を行うということは、リストを転置した結果に対して深さ優先探索を行うことと等しいということです。

bfs と dfs の関係

まとめ

Haskell 2010 Language Report ってどういう時に利用するんだろう?って思っている人もいるとは思いますが、こういう場合に参照すると便利です。

今回は幅優先探索と深さ優先探索を リストのリスト で説明しましたが、一般的に説明される木構造では、これが少し複雑になっただけです。

以上です。