このサイトは学部では早稲田で物理を, 修士では東大で数学を専攻し, 今も非アカデミックの立場で数学や物理と向き合っている一市民の奮闘の記録です. 運営者情報および運営理念についてはこちらをご覧ください.

理系のための総合語学・リベラルアーツの視点から数学・物理・プログラミング・語学 (特に英語) の情報を発信しています. コンテンツアーカイブに見やすくまとめているのでぜひご覧ください.

元書籍とここまでの内容

書籍

原著

翻訳

ここまでの内容

• 1. The smallest free number (最小自然数) 関数プログラミング 珠玉のアルゴリズムデザイン

冒頭部

Rem による解法では二分探索を使っていたそうだが,
この本では分割統治法を使うとのこと
配列の要素の上位者は右にある要素より大きい要素のことをいう.
例えば $i<j$ かつ $x[i] < x[j]$ なら $x[j]$ は $x[i]$ の上位者であるという.

文字列と文字に対してアルファベットが小さい方が上位者という順序をつければ,
次のように上位者数がカウントできる.

Specification

作る関数は msc (maximum surpassor count の略) と名付けられている.
次の実装は $O(n^2)$ なのでもっと軽くしたいという話.

msc :: Ord a => [a] -> Int
msc xs = maximum [scount z zs | z : zs <- tails xs]
scount x xs = length (filter (x <) xs)

tails [ ] = [ ]
tails (x : xs) = (x : xs) : tails xs

main = do
  print $ msc [1,2,3,4]

RESULT

3

標準ライブラリにも Data.List.tails があるがそれとは別に新たに定義する.
具体的には空リストを返さない.
tails の挙動を調べておこう.

tails [] = []
tails (x : xs) = (x : xs) : tails xs

main = do
  print $ tails [1,2,3,4]

RESULT

[[1,2,3,4],[2,3,4],[3,4],[4]]

標準ライブラリの Data.List.tails は次の通り.

import Data.List
main = do
  print $ Data.List.tails [1,2,3,4]

RESULT

[[1,2,3,4],[2,3,4],[3,4],[4],[]]

分割統治法

$O(n \log n)$ のオーダーにしたい.

全ての上位者数のテーブルを作る.

scount x xs = length (filter (x <) xs)

tails [ ] = [ ]
tails (x : xs) = (x : xs) : tails xs

table xs = [(z, scount z zs) | z : zs <- tails xs]

main = do
  print $ table [1,2,3,4,6,5]

RESULT

[(1,5),(2,4),(3,3),(4,2),(6,0),(5,0)]

このとき msc' = maximum . map snd . table とすれば第 2 の msc ができる.

scount x xs = length (filter (x <) xs)

tails [ ] = [ ]
tails (x : xs) = (x : xs) : tails xs

table xs = [(z, scount z zs) | z : zs <- tails xs]

msc' = maximum . map snd . table

main = do
  print $ table [1,2,3,4,6,5]
  print $ msc' [1,2,3,4,6,5]

RESULT

[(1,5),(2,4),(3,3),(4,2),(6,0),(5,0)]
5

ちなみに snd は名前の通り (タプルの) 2 番目を取ってくる関数.
1 番目を取りたければ fst.

main = do
  let l = [(1,5),(2,4),(3,3),(4,2),(6,0),(5,0)]
  print $ map fst l
  print $ map snd l

RESULT

[1,2,3,4,6,5]
[5,4,3,2,0,0]

もっと効率よく

これではまだ不満: 分割統治法のために
table (xs ++ ys) = join (table xs) (table ys) をみたす線型時間の join を作りたい.

本では間にごちゃごちゃ計算 (式または関数の変換) しているし,
途中にいろいろある.
よくわからないのでまずは結論から.

msc' :: Ord a => [a] -> Int
msc' = maximum . map snd . table

table [x] = [(x, 0)]
table xs = join (m-n) (table ys) (table zs)
  where m        = length xs
        n        = m `div` 2
        (ys, zs) = splitAt n xs

join _ tys [] = tys
join _ [] tzs = tzs
join n tys@((y, c):tys') tzs@((z, d):tzs')
    | y < z     = (y, c+n) : join n     tys' tzs
    | otherwise = (z, d)   : join (n-1) tys  tzs'

main = do
  let l = [1,2,3,4,6,5]
  print $ table l
  print $ msc' l

RESULT

[(1,5),(2,4),(3,3),(4,2),(5,0),(6,0)]
5

join の定義で txs は tys に,
tys は tzs に変えて table での引数との対応を見やすくした.

本での join の定義は
join 単独で見た場合に全ケースを尽くしているのだろうか.
上のように書けば問題ないだろうとは思う.

@ はシノニム: 聞き慣れないのでめちゃくちゃわかりづらいが,
単に別名をつけているだけのようだ.

testFunc lst@(x:xs) = [(x, 0)] ++ [(a, 1) | a <- xs]
main = do
  print $ testFunc [1,2,3]

RESULT

[(1,0),(2,1),(3,1)]

これは引数の lst を x:xs に分解して,
この分解した値を関数本体で使っている.

: はリストへの要素追加.

main = do
  let list = 1 : [2, 3]
  print list

RESULT

[1,2,3]

あとは join に食わせる n の値が問題か.
本ではもちろん最初から追いかけて最後に上のようにまとめているので,
それを逆に追いかける必要がある.
join と table は相互に関係があるから両方見ないと決まらないのか.

一般的に考えるより具体例を追いかけた方が早そう.

main = do
  let xs = [1,3,2]
  let m = length xs
  let n = m `div` 2
  let ys = fst $ splitAt n xs
  let zs = snd $ splitAt n xs

  print m
  print n
  print (m - n)
  print ys
  print zs

RESULT

3
1
2
[1]
[3,2]

ここまで書いてみたはいいものの,
具体的に書き下していくのがあまりにも面倒で断念.
頭の中で簡単なシミュレーションをして何となく事情は察した.

このくらいならまだ結果を見てシミュレーションすれば何となく雰囲気は掴める.
単純に慣れていないだけなのだとは思っているが,
関数が相互に定義されていてしかも再帰的になっている状況,
どうしても追いかけるのがつらい.
デバッグもどうしたらいいのかよくわからない.
「(Haskell に) 慣れたら print デバッグなんてそもそもしなくなった」みたいなことも見かけるので,
もっとどっぷり浸かってみろということなのだろう.

数学や物理のコンテンツを作っていても他人に言うことだし,
しばらく地道にやっていくしかない.

あとやはり実行可能なコード片を実際に作り,
ちょこちょこ小さくコードを積んでいくのがよさそう.
今回もそれをやりたかったのだが table と join のように
2 つの関数が絡んでくる場合にどうしたものか.
もっとじっくり解きほぐすしかないか.
今回はソートされたリストのマージで挫折した.
$\land$ を重ねたような記号で書いてあるところ.

ああいう記号だか関数だか Haskell に本当にあるの.
単に気分だけを表現しているのか何なのか,
それすら全くわからない.
自分がコンテンツを作っているときにこうなっていないか,
反省する題材でもある.

追記

またコメントを頂いた.
本文にコメントを引用する.

(⩕)演算子はHaskellの標準ライブラリでは定義されていません。
この演算子の仕様が、「整列済みの2つのリストをマージして1つの整列済みのリストにする」です。
ここでは、この仕様どおりの(⩕)が与えられているとしたら、(2.2)の等式が満たされていることが判るということが重要です。つまりプログラムを実行しなくても、あるいはテストしなくても、その正しさが判るということが、肝になっています。

以下の様に定義すれば仕様を満していることは容易に判ると思います。

コードは別枠で引用.
#+BEGIN_SRC haskell :results silent
infixr 4 ⩕
(⩕) ∷ Ord a ⇒ [a] → [a] → [a]
[] ⩕ ys = ys
xs ⩕ [] = xs
xxs@(x:xs) ⩕ yys@(y:ys)
| x > y = y : (xxs ⩕ ys)
| otherwise = x : (xs ⩕ yys)
#+END_SRC

話がずれるが「⩕」がフォント (?) 的に存在していたことに衝撃を受けた.

ちなみに infixr はこの辺参照.