Clever Geek Handbook

Haskellの無限のストリームと同様に、分割して征服する

すべての読者へのご挨拶！

以下は、大学のHaskellコースのスライドの第14章をどのように理解したかについての私の視点です。

そこで、今日は次の2つのトピックについてお話します。

この分野の専門家は、不正確な点がある場合はコメントして修正してください。 コメントで質問に答えてうれしいです。



分割して征服する



おそらく、プログラミングで何度も「分割して征服」の原則を満たしているでしょう。 問題が初歩的なものであれば、すぐに解決します。 そうでない場合は、それをより小さな「副問題」に分割し、すべての問題が基本になるまでこれを行います。 すべての基本的な問題を解決した後、元の問題の解決策を得るために、それらを「接続」する必要があります。

問題（およびすべてのサブ問題）のタイプをp



とし、すべてのソリューションのタイプをs



ます。 タイプp



問題を受け入れ、結果としてタイプs



解を生成する高次関数divideAndConquer



を見つける必要があります。 これを行うには、divideAndConquerアルゴリズムの動作を実装する補助関数（= DivideAndConquer要素）が必要です。 



 indiv :: p -> Bool
この関数は、「問題をいくつかのサブ問題に分割することは可能ですか？」という質問に答えます。 はいの場合、Trueを返します。 そうでない場合、この問題は基本的なものであり、関数solve



を使用してsolve



ます。 



 solve :: p -> s
名前が示すように、この関数は基本的な問題を解決し、タイプs



解を生成します。 



 divide :: p -> [p]
問題が初歩的でない場合、それをいくつかの副問題に分割します。 1つの問題p



から多くの問題[p]



を作成し[p]



、これらははるかに簡単に解決できます。 



 combine :: p -> [s] -> s
すべての基本的な問題を解決した後、それらを単一のソリューションにまとめる必要があります。 ここでなぜp



を要求するのですか？ 問題の一部には、最終的な回答に使用する必要があるソリューションの一部が既に含まれている場合があります（以下の例で確認します）。



それでは、この普遍的なDivideAndConquer divideAndConquer



どのdivideAndConquer



見えるのでしょうか？ 関数の定義は次のとおりです。 

 divideAndConquer :: (p -> Bool) -> (p -> s) -> (p -> [p]) -> (p -> [s] -> s) -> p -> s


つまり この関数は、上記の4つの基本要素と、分割が開始される問題で構成されています。 出力には、タイプs



ソリューションがあります。 そして、ここに関数自体があります： 

 divideAndConquer :: (p -> Bool) -> (p -> s) -> (p -> [p]) -> (p -> [s] -> s) -> p -> s divideAndConquer indiv solve divide combine initPb = dAC initPb where dAC pb | indiv pb = solve pb | otherwise = combine pb (map dAC (divide pb))


問題（pb）が小さな副問題に分割されていない場合、 indiv pb = solve pb



ます。 そうであれば、この問題を共有し、解決して結果を結合します。



quickSort



例を使用して、このような関数を適用する方法を見てみましょう。 クイックソート関数は、比較可能な要素の配列を受け入れ、同じ要素を持つ配列を生成しますが、ソートされた順序になります。 

 quickSort :: Ord a => [a] -> [a]




次に、クイックソート専用のdivideAndConquer



アルゴリズムの4つの要素を決定する必要があります。 配列の長さが1以下の場合、問題は分割不可能（= indiv）と見なされます。クイックソートでは、問題のそのような解決策（=解決）はありません。 配列の長さが1の場合、この配列はソートされます。 次のように配列を分割（=分割）できます。最初の要素を取り、2つの配列を形成します-1つは最初の要素のすべての要素<=、2つ目は最初の要素のすべての要素>です。 ソートされた配列を結合（=結合）する：最初の要素は中央に配置され、その左はすべてこの要素よりも小さい数字で、右はすべての数字がこの要素よりも大きい。

splitAndConquerの主要な4つのコンポーネントを定義したら、関数を安全に作成できます。 
 quickSort :: Ord a => [a] -> [a] quickSort lst = divideAndConquer indiv solve divide combine lst where indiv ls = length ls <= 1 solve = id divide (l:ls) = [[x | x <- ls, x <= l], [x | x <- ls, x > l]] combine (l:_) [l1,l2] = l1 ++ [l] ++ l2




このメソッドは、Quicksortだけでなく、Mergesortなどの他のソートアルゴリズムにも適用できます（ソートだけでなく）。 しかし、分割と征服を使用して問題を解決できる場合、これが最も効果的なソリューションになると誤解しないでください。 これはフィボナッチ数の例で見ることができます。 この関数は、フィボナッチ数列からn番目の数を返します。 
 fib :: Integer -> Integer fib n = divideAndConquer indiv solve divide combine n where indiv n = (n==0) || (n==1) solve n | n == 0 = 0 | n == 1 = 1 | otherwise = error "Input argument must be >= 0" divide n = [n-2, n-1] combine _ [l1,l2] = l1 + l2


残念ながら、この関数には指数関数的な複雑さがあり、この問題を解決するより効率的な方法があります。



おわりに


divideAndConquer



アルゴリズムは、 indiv, solve, divide, combine



の4つのindiv, solve, divide, combine



構成されindiv, solve, divide, combine



ます。 何らかの問題について、それらすべてを特定できる場合は、この方法を安全​​に使用できます。 ただし、「分割統治」が常に問題の最適な解決策とは限らないことを忘れないでください。



無限のストリーム



Haskellの機能の1つは、無限のスレッドで動作できることです。 この場合のストリームは、「無限配列」（eng。Lazy list）と同義です。 たとえば、 [1..]



はすべての自然数の配列です。 このようなストリームにより、「遅延評価」を実行できます。

すべての素数（=素数のストリーム）を生成するアルゴリズムを作成してみましょう。 エラトステネスのふるいを使用して素数を計算します。 その考えは、2から「無限大」までのすべての自然数の配列があるということです。 左端の数字は常に素数です。 素数を取るたびに、この数字で割り切れるすべての数字をリストから削除します。 で始まる：

2, 3, 4, 5, 6, 7, 8, 9, 10, 11...





数値2は素数で、2で割り切れるすべての数値を消します。

2, 3, 5, 7, 9, 11...





数字の3は素数で、3で割った数字をすべて消します。

2, 3, 5, 7, 11...





など



Sieve（= Sieve）は配列を受け取り、上記の操作を実行します。 
 sieve :: [Integer] -> [Integer] sieve (x:xs) = x : sieve [y | y <- xs, mod yx > 0]




これで、素数のストリーム（=素数）は次のように記述できます。 
 primes :: [Integer] primes = sieve [2..]


これでprimes



を呼び出すとprimes



がコンソールにprimes



れます。 これはどのように機能しますか？

primes





->> sieve [2..]





->> 2 : sieve [y | y <- [3..], mod y 2 > 0]





->> 2 : 3 : sieve [z | z <- [y | y <- [4..], mod y 2 >0], mod z 3 > 0]





->> ...





->> 2 : 3 : sieve [ z | z <- [5, 7, 9..], mod z 3 > 0]





->> ...





->> 2 : 3 : sieve [5, 7, 11, ...





->> ...







「さて、それでは何？」とあなたは尋ねます。 そのようなフローをどのように使用し、どのような操作を実行できますか？

いわゆる「サンプリング」原理があり、無限ストリームからいくつかの要素のみを選択できます。次に例を示します。



「フィルタリング」の原則。これにより、次のような素数セットのサブセットを選択できます。

このタイプへの小さな注意： filter (<10) primes ->> [2,3,5,7,



は決して実行を完了しません。 filterは、数値が10未満かどうかを認識せず、それらの検索を続けます。 関数を増やす場合、これは次のように実行できます： takeWhile (<10) primes ->> [2,3,5,7]



。



ストリームの各番号に対して特定のアクションを実行する「変換」の原理、例えば：



おわりに


ストリームは関数型言語では非常に便利ですが、注意して使用する必要があります。 フローの3つの基本原則：


More articles:


All Articles