朝日ネット　技術者ブログ

朝日ネットのエンジニアによるリレーブログ。今、自分が一番気になるテーマで書きます。

Algorithm Design with Haskellでアルゴリズムを学ぶ

Haskell

はじめに

開発部のcbmkageです。 仕事でプログラムを書いていると、どうしたら期待通りに、かつ高速に動作するアルゴリズムが実装できるか、考えることがあります。 本記事では、アルゴリズムについて新たな視点を与えてくれる本「Algorithm Design with Haskell」を紹介します。

本記事はHaskell中級者向けです。Haskellの文法や、代表的なリスト操作関数を知っていることを前提としています。

Algorithm Design with Haskellとは

Algorithm Design with Haskell

Algorithm Design with Haskell

Amazon

Algorithm Design with Haskell (以下「同書」) とは、大学教授らによって書かれた、学生や研究者、教師などのためのアルゴリズムの教科書です。 出版社のサイトには、以下のような特徴が述べられています。

  • アルゴリズムデザインの5つの原理 (principle) を説明する
    • 分割統治法 (divide and conquer)
    • 貪欲アルゴリズム (greedy algorithm)
    • thinning*1
    • 動的計画法 (dynamic programming)
    • 全探索 (exhaustive search)
  • 良質な例題により、アルゴリズムの共通点と相違点を明らかにする
  • 多数の演習問題を含んでいる
  • 純粋関数型言語であるHaskellにより、簡潔な説明と短いプログラムを与えている
  • アルゴリズムの改善 (development) は可能な限り等式による理由づけを用いて、適用できる条件と正しさの議論を明快にする

5つの原理自体は、thinningを除けば一般的な用語で、アルゴリズムを学んだことがある方であれば聞いたことがある用語だと思います。同書でなくても概念を学ぶことはできるでしょう。 例題や演習問題の豊富さについては、列挙するだけでも大変です(全体で400ページ超の大ボリュームです)ので、本記事では語りません。

本記事では、最後の2点である、

  • 純粋関数型言語であるHaskellにより、簡潔な説明と短いプログラムを与えている
  • アルゴリズムの改善 (development) は可能な限り等式による理由づけを用いて、適用できる条件と正しさの議論を明快にする

ということについて、一部分の論理を追って雰囲気と面白さをお伝えしていきたいと思います。

同書は、先述の「5つの原理」と、その前の基礎の全6つのPARTで構成されています。

  • PART ONE BASICS
  • PART TWO DIVIDE AND CONQUER
  • PART THREE GREEDY ALGORITHMS
  • PART FOUR THINNING ALGORITHMS
  • PART FIVE DYNAMIC PROGRAMMING
  • PART SIX EXHAUSTIVE SEARCH

本記事では、PART THREE GREEDY ALGORITHMS の一部分の論理を紹介していきます。

準備: 関数の同値関係

内容の紹介の前に、ひとつ必要な準備をしておきます。 本記事では、2つの関数fとgが任意の入力に対して*2同じ出力をするとき、f <==> gという記法で命題を表します*3。 つまり、プログラムとしてfを使ってもgを使っても同じ結果が得られるいうことになります。ただし、計算量は同じとは限りません。

同書ではこの同値関係には= が使われていますが、Haskellでは =は束縛に使われるので、本記事では別の記号を使います。例として

1 + 1 <==> 2
map f . map g <==> map (f . g)
concatMap f . map g <==> concatMap (f . g)
foldr f e . map g <==> foldr (f . g) e

などの表記をします。

貪欲アルゴリズムのPART紹介

貪欲アルゴリズムとは

では貪欲アルゴリズムに関するPART THREEの論理を追っていきましょう。 まず、貪欲アルゴリズムとはどんなアルゴリズムかが述べられています。

(筆者翻訳) 多くの計算問題は、可能な候補の集合から最善の候補を選び出すことと関連している。 (中略) こうした問題の入力は通常、候補の集合ではなく、そこから候補を生成することができるような要素のリストとして与えられる。 (中略) 貪欲アルゴリズムは、こうした問題をstep-by-stepに、各ステップで1つの部分候補を作ることで解決する。

引用元: Algorithm Design with Haskell [ISBN:1108491618] PART THREE

候補の生成と選択

同書7章1節にならって、貪欲アルゴリズムの対象となるような問題をHaskellの関数で記述していきます。(ただし、この記述のしかたはあくまで一例であり、すべての問題をこのように記述するのがよいとは限りません。) *4

type Component = ...
type Candidate = ...

extend :: Component -> Candidate -> [Candidate]
extend = ...

c0 :: Candidate
c0 = ...

step :: Component -> [Candidate] -> [Candidate]
step = concatMap . extend

candidates :: [Component] -> [Candidate]
candidates = foldr step [c0]

候補の生成方法はextendとc0により決定されます。 candidatesは入力としてComponentのリストをとり、これをstep = concatMap . extendによって畳み込むことによって候補 (Candidate) を生成します。

type Cost = ...
--instance Ord Cost

cost :: Candidate -> Cost
cost = ...

minWith :: Ord b => (a -> b) -> [a] -> a
minWith f = foldr1 (smaller f)
  where smaller f x y = if f x <= f y then x else y

mcc :: [Component] -> Candidate
mcc = minWith cost . candidates

mccは、候補の良さをはかる所与の関数costを使って (Costは小さいほど良いとします) 比較することで、candidatesで生成された候補の中から最善のものを選び出します*5。 これで、「要素のリストから生成された候補の中から、最善の候補を選び出す」という問題を記述することができました。

例として、同書7章2節で紹介されている「リストを昇順にソートする」という問題を考えます。 リストを昇順にソートすることは、「入力リストのすべての順列を生成して、順番と大きさが逆になっているペアの数が最小のもの*6を選ぶ」と考えることができるので、以下のようにできます。

pairs :: [a] -> [(a,a)]
pairs xs = [(x,y) | x:ys <- tails xs, y:zs <- tails ys]

ic :: Ord a => [a] -> Int
ic xs = length [(x,y) | (x,y) <- pairs xs, x > y]

perms :: [a] -> [[a]]
perms = foldr (concatMap . inserts) [[]]

inserts :: a -> [a] -> [[a]]
inserts x [] = [[x]]
inserts x (y:xs) = (x:y:xs): map (y:) (inserts x xs)

sort :: Ord a => [a] -> [a]
sort = minWith ic . perms

ic は順番と大きさが逆になっているペアを数える関数で、小さいほどよいという指標になります。 inserts は、第2引数のリストのどこかに第1引数を挿入したものすべて*7を返します。 perms はinsertsを繰り返していくので、引数リストのすべての順列を返します。 順列の中にはソートされているものが含まれているので、mcc の定義において、

  • cost = ic
  • extend = inserts
  • c0 = []

とすると「リストを昇順にソートする」という問題を記述できていることになります。

貪欲アルゴリズムへの改善

mccはそれ自体がHaskellの関数なので、プログラムとして実行することができます。 しかし、extendが1つの候補から複数の候補を生成するので、extendを繰り返すと候補が入力の長さに関して指数的に増加してしまいます。 このmccをよりよい関数で置き換えたいというのがアルゴリズムの考えどころです。

候補の生成は以下のように行われました。

step = concatMap . extend
candidates = foldr step [c0]

step = concatMap . extend を繰り返していますが、このstepごとに最善の候補だけを残して、他は捨てることはできるでしょうか。 たとえば先の「ソートする」という問題では、inserts の第2引数のリストがソートされていなければ、insertsの結果にソートされているものは含まれません。 ですからinsertsの結果のうち、ソートされているもの1つだけを残して、他は捨ててよいことがわかります。 これができるとすると、以下のmccGreedyで解が得られるでしょう。

gstep :: Component -> Candidate -> Candidate
gstep x = minWith cost . extend x

mccGreedy :: [Component] -> Candidate
mccGreedy = foldr gstep c0

mccGreedyにおいて、foldrの畳み込みは右から左へ逐次的に行われるので*8、一種の「step-by-step」といえるでしょう。 畳み込みの各ステップでminWithにより候補を1つに絞るので、候補が指数的に増えていくことはありません。 これは一種の貪欲アルゴリズムになっていることがわかります。

さて、一般にmcc を mccGreedy に変更してよいのはどんな場合でしょうか。 ここでは以下のfoldr fusionという定理*9を使って、これができるための十分条件を与えます*10。

「任意のx, yについて h (f x y) <==> g x (h y)」
ならば
h . foldr f e <==> foldr g (h e)

これにmccとmccGreedyにあらわれる関数を代入して具体化します。

  • h <- minWith cost
  • f <- step
  • e <- [c0]
  • g <- gstep

すると以下の命題が得られます。

「任意のx, csについて minWith cost (step x cs) <==> gstep x (minWith cost cs)」
ならば
mcc <==> minWith cost . foldr step [c0]
    <==> foldr gstep (minWith cost [c0])
    <==> foldr gstep c0
    <==> mccGreedy

次に、「ならば」の前の条件の十分条件を見つけます。 ここでの中括弧 { } は、等式の根拠を表し、等式を補足するものです。

  minWith cost (step x cs)
<==> { definition of step }
  minWith cost (concatMap (extend x) cs)
<==> { distributive law (本記事では証明は割愛) }
  minWith cost (map (minWith cost . extend x) cs)
<==> { definition of gstep }
  minWith cost (map (gstep x) cs)
<==> { greedy condition (後述) }
  gstep x (minWith cost cs)

ただし、greedy condition (貪欲条件) は以下の命題とします。

任意のx, csについて
minWith cost (map (gstep x) cs) <==> gstep x (minWith cost cs)

以上より、以下の命題が示されました。

貪欲条件が満たされるならば、
mcc <==> mccGreedy

まとめ

貪欲アルゴリズムの一部分を読むことで、以下のような知見が得られました。

  • 貪欲アルゴリズムとは、生成される候補のうち最善のものを求める問題において、step-by-stepに、ステップごとに候補を1つだけ残すアルゴリズムである
  • 候補の生成がfoldrで記述されるときには、foldr fusionを使って貪欲アルゴリズムにできることがわかる
    • foldr fusionが使える条件を検討すると、貪欲条件が十分条件であることがわかる

まさに紹介文にあったような特徴がありました。

  • 純粋関数型言語であるHaskellにより、簡潔な説明と短いプログラムを与えている
  • アルゴリズムの改善 (development) は可能な限り等式による理由づけを用いて、適用できる条件と正しさの議論を明快にする

本記事では同書のほんの一部を紹介しましたが、魅力が伝わりましたら幸いです。

採用情報

朝日ネットでは新卒採用・キャリア採用を行っております。

新卒採用 キャリア採用｜株式会社朝日ネット

*1:同書でいうthinningとは、貪欲アルゴリズムの一般化であり、各ステップで最善になりえない候補の枝刈りを行うアルゴリズムです。定訳が見つからなかったため、英単語のままにしています

*2:同書では「有限リストについて」のような但し書きがついていますが、本記事では細かい議論は省きます

*3:この同値関係は関数の外延的等値性 (extensional equality) と呼ばれます。同書ではあまり詳しい説明はありません

*4:問題を関数で記述すると制約が強すぎる場合があるので、同書では問題を非決定的関数で記述する手法が紹介されています。これは強力で、同書の魅力のひとつですが、本記事では割愛します

*5:最善のものは一般に複数ありますが、この関数は最善のもののうち最も左のものを返します。これは問題を記述するうえで強すぎる制約になってしまう場合があります

*6:ペア数0のものが必ず存在します

*7:長さnのリストには、(n+1)箇所の挿入できる箇所があります

*8:遅延評価により実行順序と一致するとは限りません

*9:同書では定理の証明が与えられています

*10:同書では、foldr fusionを使ってgstepを見つけるという順番になっていますが、本記事では直観的なmccGreedyを先に与えています