このサイトは学部では早稲田で物理を, 修士では東大で数学を専攻し, 今も非アカデミックの立場で数学や物理と向き合っている一市民の奮闘の記録です. 運営者情報および運営理念についてはこちらをご覧ください.
理系のための総合語学・リベラルアーツの視点から数学・物理・プログラミング・語学 (特に英語) の情報を発信しています. コンテンツアーカイブに見やすくまとめているのでぜひご覧ください.
目次
はじめに
数学や物理, 特に物理を学ぶのに関数プログラミング,
特に Haskell が非常にうまく使えるという話がある.
それを見て Haskell の勉強が急務だと思い色々な形で Haskell への知見を深めている.
例えば別企画で次のような記事 (群) もある.
- 素数夜曲とプログラミング B-B.1.2 Scheme, Python, Haskell, JavaScript 第 1 回
- 素数夜曲とプログラミング B.2-B.4 Scheme, Python, Haskell, JavaScript 第 2 回
そして何となくアルゴリズムをきちんと勉強しないといけないのかな,
とずっと思って放置したままになっている.
とりあえずいい加減何かやってみようと思い,
何となく買ってみたのが Richard Bird の pearls of functional algorithm design だ.
英語版を手に入れたのだが翻訳があったらしいと後で気付いた.
ウルトラ難しく 1 章を読んだ時点で既に心が折れている.
ただせっかく読んだ分は記録に残しておきたい.
他の数学、物理系プログラミングを進めていて,
うんざりしてきたら現実逃避でこちらを進めるというのもあっていいだろうとは思っている.
この本, Graham の本と同じスタイル,
つまり正確なコードを書かずに一部疑似コード (疑似記号?) を使っていて,
慣れていないとすぐに翻訳できないのが最高に鬱陶しい.
例えば第 1 章で言うと本の P.1 で出てくる $\notin$ は
not . flip elem
のように表現しないといけないよう (本当によくわかっていない) だし,
本の P.2 で出てくる $\lor$ は本来の Haskell コードでは ||
だ.
先に書いたように最近また精力的に数学や物理, プログラミングのコンテンツを作っているけれども,
こういうのはよくないな, と痛感させられるコンテンツだ.
そういう意味でも厳しいコンテンツを見てみることは役に立つと思って,
無理せずゆるくやっていこう.
追記
翻訳者の山下伸夫さんからコメントを頂いてしまった.
Functional Pearls of Algorithm Designのプログラム表記と、ASCII記号によるHaskellプログラム表記との対応については、 http://pfad.sampou.org/ に追記しましたので、御笑覧くださいませ。
引用しておこう.
演算子記号とASCII文字列との対応
- 本書の記号: HaskellのASCII文字
- ≤: <=
- ≥: >=
- ∨: ||
- ∧: &&
- ⋅: .
- ≠: /=
- ∈:
elem
- ∉:
notElem
- ⊑:
isPrefixOf
- div:
div
- mod:
mod
- min:
min
- max:
max
- knows:
knows
演算子以外の構文記号の一部については,GHCの言語拡張UnicodeSyntaxを有効にするとソースコード中に記述可能です. 詳細については,GHCユーザーガイド 9.3.1 Unicode syntaxをご覧ください.
演算子に関しては,Unicodeの記号が使えますので,たとえば,1章については,以下のような定義モジュールをインポートすれば,そのままコードで表現できます.
{-# LANGUAGE UnicodeSyntax #-}
module Operators whereimport qualified Data.List
infixr 5 \
(\) ∷ Eq a ⇒ [a] → [a] → [a]
(\) = (Data.List.\)infix 4 ∈, ∉
(∈) ∷ Eq a ⇒ a → [a] → Bool
(∈) = elem(∉) ∷ Eq a ⇒ a → [a] → Bool
(∉) = notEleminfixr 2 ∨
(∨) ∷ Bool → Bool → Bool
(∨) = (||)infixr 3 ∧
(∧) ∷ Bool → Bool → Bool
(∧) = (&&)infix 4 ≤, ≥
(≤) ∷ Ord a ⇒ a → a → Bool
(≤) = (<=)(≥) ∷ Ord a ⇒ a → a → Bool
(≥) = (>=)
数学関係だとほとんどコメント来ないのに (素人くさい) プログラミングの話だと
やたら本質的に私が助かるコメントが来るのでありがたさしかない.
1. The smallest free number (最小自然数) 関数プログラミング 珠玉のアルゴリズムデザイン
集合 $X \subset \mathbb{N}$ の最小値を求めようという問題を考えよう.
もちろん適当に派生的な問題もあるし現実的な応用もある.
解は $X$ がどのように表現されているかによる.
任意の数のリストを線型時間でソートするアルゴリズムを考えてみる.
次の minfree
のような挙動をする関数を作りたい.
-- Int を Nat にしたい: Nat じたいは例えば Data.Nat にはある. 適当にインポートしたりする必要あり?
minfree :: [Int] -> Int
--minfree xs = head $ [0..] Data.List.\\ xs
minfree xs = head $ [0..] Main.\\ xs
-- Data.List.\\ にある関数: 本の記述では notElem が TeX でいう $\notin$ の記号で書かれていた.
(\\) :: Eq a => [a] -> [a] -> [a]
us \\ vs = filter (not . flip elem vs) us
main = do
let a = [8, 23, 9, 0, 12, 11, 1, 10, 13, 7, 41, 4, 14, 21, 5, 17, 3, 19, 2, 6]
-- print $ Data.List.sort a
print $ minfree a
RESULT
15
この関数 minfree
は $O(n^2)$ のオーダーなので困る.
これをどうにかしたい.
Haskell の配列による解法
[0 .. length xs]
の全ての要素が xs
に入っているわけではないことに注意する.
xs
に入っていない最小の数は filter (<= (length xs)) xs
に入っていない最小の数だ.
結果から書くと次のようになる.
この実装は xs
の要素が全て違う必要はないものの自然数であることは要請する.
import Data.Array
minfree' = search . checklist
search :: Array Int Bool -> Int
search = length . takeWhile id . elems
checklist :: [Int] -> Array Int Bool
checklist xs = accumArray (||) False (0, n) $ zip (filter (<= n) xs) (repeat True)
where n = length xs
main = do
print $ minfree' [8, 23, 9, 0, 12, 11, 1, 10, 13, 7, 41, 4, 14, 21, 5, 17, 3, 19, 2, 6]
RESULT
15
こんなさっくり書かれて意味がわかるわけもない.
当然 search
と checklist
をそれぞれじっくり追うしかない.
まずは checklist
を見てみる.
checklist
たぶん慣れていないと accumArray
がめんどい.
というかいまだにきちんと理解しきれていない.
次の節で別立てで見ることにして,
まずは accumArray に食わせるリストを作るところからはじめよう.
つまり zip (filter ( <= n) xs) (repeat True)
だ.
repeat True
は全要素がブーリアン True
の無限リストを作る.
zip
ではめて有限リストを切り出している.
zip
にかけるもう一方のリストは filter (<= n) xs
で作る.
これは特に言うことない.
main = do
let xs = [8, 23, 9, 0, 12, 11, 1, 10, 13, 7, 41, 4, 14, 21, 5, 17, 3, 19, 2, 6]
let n = length xs
let a = zip (filter (<= n) xs) (repeat True)
-- print $ repeat True
print $ filter (<= n) xs
print a
RESULT
[8,9,0,12,11,1,10,13,7,4,14,5,17,3,19,2,6]
[(8,True),(9,True),(0,True),(12,True),(11,True),(1,True),(10,True),(13,True),(7,True),(4,True),(14,True),(5,True),(17,True),(3,True),(19,True),(2,True),(6,True)]
これでタプルのリストができる.
このタプルのリストを accumArray
にくわせる.
accumArray
多分これが一番めんどい.
泥臭くコード片を追いかけないとわからない.
ふだん (手続き型で?) 書くときはループで書くところを関数でスパっと書いている感じ.
逐次 print デバッグみたいなのがやりづらいので何をやっているかまだ追いづらい.
多分慣れればもっとサクサク書けるのだろうなとは思う.
とにかく泥臭く追いかけよう.
foldr
などと同じくコレクションに関数を順次適用させて新たなコレクションを作る系の処理だ.
実コード例
import Data.Array
main = do
-- 配列の添字は [1..3]
-- 配列の各要素は第 2 引数 0 で初期化される
let a = [(1, 2), (3, 4), (1, 5)]
print $ accumArray (+) 0 (1,3) a
RESULT
array (1,3) [(1,7),(2,0),(3,4)]
accumArray
の第 1 引数は当てる関数,
第 2 引数は初期値, 第 3 引数は新たな配列の添字の範囲,
第 4 引数はなめていく配列だ.
Python あたりの標準的な記法を使って配列、リストを表すことにしよう.
accumArray
の結果の配列を b
とする.
b[1]
からはじまるので b[1]
がどうなるかを調べよう.
結果から行くと a[0]
と a[2]
の第 1 要素の和,
つまり b[1] = a[0][1] + a[2][1]
になる.
これを見ていく.
基本は a
をなめていくのだ.
a[0][0]
を調べると1
: これとb[1]
の値を関連づける.
初期値は0
で+
を使うことになる.
+
のもう一方の引数としてa[0][1]
を使う.- 結果として
b[1] = 0 + a[0][1]
になる. - 次に
a[1][0]
を調べると3
: これとb[3]
の値を関連づける.
初期値は0
で+
を使うことになる.
+
のもう一方の引数としてa[1][1]
を使う. - 結果として
b[3] = 0 + a[1][1]
になる. - 次に
a[2][0]
を調べると1
: これとb[1]
の値を関連づける.
初期値は0
で+
を使うことになる.
+
のもう一方の引数としてa[2][1]
を使う. - 結果として
b[1] = 0 + a[0][1] + a[2][1]
になる. - 一度も出てこない
b[2]
は初期値そのままb[2] = 0
.
これが上の accumArray
の結果.
checklist
は 0 から $n$ 個までの $n+1$ スロットある.
最初は全て False
だ.
search
改めて書くと次のように定義される.
minfree' = search . checklist
search :: Array Int Bool -> Int
search = length . takeWhile id . elems
checklist :: [Int] -> Array Int Bool
checklist xs = accumArray (||) False (0, n) $ zip (filter (<= n) xs) (repeat True)
where n = length xs
Boolean の配列 (Data.Array) から整数を取る.
この整数はもとのリストの最小値にあたる.
この他に関数の合成 (.)
も使っている.
elems
から見ていこう.
これは配列の要素をリストに格納して返す.
import Data.Array
main = do
let a = listArray (0,3) [1,2,3,4]
print $ a
print $ elems a
RESULT
array (0,3) [(0,1),(1,2),(2,3),(3,4)]
[1,2,3,4]
これも特に問題ないだろう.
よくわからないのは id
.
なぜこれを挟む必要があるのだろうか?
外したらエラーになった.
takeWhile
に predicate を食わせないといけないからその役割なのだろうか.
そう思えば必要な理由は理解できる.
今の私のレベルでは自分で書こうとすると多分解決できずそのまま死にそう.
takeWhile
は predicate を食わせてそれが True
を返すうちはリストを返し続けてくれる関数.
False
が来たら打ち切ってそこまでの長さを測れば目的の値が取れる.
分割統治法 (divide & conquer)
xs
の要素は全て異なることを前提にしている.
基本的なアイデアはリストを分けてそのリストのそれぞれに対処すること.
最初のコードは次の通り.
徐々に改善していく.
import Data.List
minfreeDivideAndConquer b xs =
if null ([0..b-1] Data.List.\\ us)
then head ([b..] Data.List.\\ vs)
else head ([0..] Data.List.\\ us)
where (us, vs) = partition (< b) xs
main = do
let a = [8, 23, 9, 0, 12, 11, 1, 10, 13, 7, 41, 4, 14, 21, 5, 17, 3, 19, 2, 6]
print $ Data.List.sort a
print $ minfreeDivideAndConquer 4 a
RESULT
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,17,19,21,23,41]
15
いくつか関数の挙動を調べておこう.
まずは null
.
main = do
print $ null []
print $ null [1]
RESULT
True
False
次に partition
.
import Data.List
main = do
print $ Data.List.partition (< 2) [1,2,3,4]
RESULT
([1],[2,3,4])
最初の改良点は null ([0..b-1] Data.List.\\ us)
で,
$O(n^2)$ かかるこの処理を軽くしたい.
リストに重複がなければ null ([0..b-1] \\ us) == (length us == b)
であることを使う.
ここでリストに重複がないことを使っている.
これと次の minfrom
を使う.
minfrom :: Int -> [Int] -> Int
minfrom a xs = head ([a..] \\ xs)
RESULT
そこで次のコードが出てくる.
import Data.List
b = 5
minfreeDivideAndConquer' xs = minfrom 0 xs
minfrom a xs | null xs = a
| length us == b - a = minfrom b vs
| otherwise = minfrom a us
where (us, vs) = partition (< b) xs
main = do
print $ minfreeDivideAndConquer' [8, 23, 9, 0, 12, 11, 1, 10, 13, 7, 41, 4, 14, 21, 5, 17, 3, 19, 2, 6]
このコードを runhaskell で動かそうと思ったら動かない.
エラーになるわけではなく処理が回りっぱなしという感じ.
何なのだろう.
何はともあれ, 上のコードは b=5
のハードコードが気に入らない.
これを消した以外にも length us
を何度も計算しないように
where
に押し込めたりと工夫したのが次のコード.
import Data.List
minfreeDivideAndConquer'' xs = minfrom 0 (length xs, xs)
minfrom a (n, xs) | n == 0 = a
| m == b - a = minfrom b (n - m, vs)
| otherwise = minfrom a (m, us)
where (us, vs) = partition (< b) xs
b = a + 1 + n `div` 2
m = length us
main = do
print $ minfreeDivideAndConquer'' [8, 23, 9, 0, 12, 11, 1, 10, 13, 7, 41, 4, 14, 21, 5, 17, 3, 19, 2, 6]
RESULT
15
今回はこれでおしまい.
Functional Pearls of Algorithm Designのプログラム表記と、ASCII記号によるHaskellプログラム表記との対応については、 http://pfad.sampou.org/ に追記しましたので、御笑覧くださいませ。
ありがとうございます。
追記もしておきました。