<   2012年 04月 ( 28 )   > この月の画像一覧

RWH の読み方(40) 第4章

Real World Haskell 第4章 Functional Programming

Anonymous (lambda) Functions

このセクションでは、Haskell の無名関数の書き方について述べてある。例えば次のように関数に名前をつけなくても、無名関数を定義して使うことができる。

Prelude> (\x -> x * x) 2
4

\ は英米のASCIIではバックスラッシュになるのでギリシャ語のλに似ている。このため \ を「ラムダ」と読んで、無名関数の(独立)変数を指示するのに使われている。

関数のラムダ記法(ラムダ算法)は1930年にチャーチとクリーネによって考案された形式的に関数を表記するための記法だ。もともとは記号論理学的に一階述語論理学の決定不可能性を証明するために使われた。

ラムダ算法は関数型言語と密接な関係があり、Lisp はラムダ算法をプログラミング言語として実装したものだ。

ここでは、そのような理論的な性質は関係なく、単に無名関数を記述する方法だと理解しておけばいい。

ラムダ記法の無名関数は、map 関数に利用することが多い。

Prelude> map (\x -> x * x) [1,2,3]
[1,4,9]

また IO モナドの cs <- getLine のような <- 記法を理解するときに必要になる。

しかし、実際のプログラミングでは可読性が下がるなどの理由で避けたほうがよいとされる。上の map のプログラムもラムダ記法の部分はセクション Section で代替可能だ。

Prelude> map (^2) [1,2,3]
[1,4,9]

Partial Function Application and Crrying

Haskell の type signature は a -> b -> c のようにタイプ変数を -> でつなげてあるが、これは2引き数以上の Haskell の関数が、1引き数の関数とも、複数引き数の関数ともみなすことができるということを示している。

次の2引き数の関数 twoArgs は次のように引き数 x に定数を代入して1引き数の関数 oneArg とみなすこともできる。

Prelude> let twoArgs x y = x + y
Prelude> twoArgs 1 2
3
Prelude> let oneArg y = twoArgs 2 y
Prelude> oneArg 2
4

多変数関数を1変数関数に使いまわしたりできるので便利だ。もっと複雑な使い方もできるがそれは RWH の本文を読むと書いてある。

多変数関数に部分的に値を適用して新しい関数を作ることを currying と呼ぶ。

Partial Function にしても、crrying にしても実際のプログラムを書くときは頻繁に出てくるのでその威力を感じることが多いが、文章で説明するのは難しい。RWH の例を読んでもあまり有難みは感じないかもしれないが、自分で Haskell の小さなプログラムを書き始めると自然に利用し始めるだろう。

Sections

Section は中置演算子の partially applied function だ。例えば + は、x + y のように2つの引き数をとりその和を計算するが、これを (1+) と記述すると左の引き数が1で右の引き数が y の関数になる。したがって引き数 y の値を与えるとその和が計算される。

Prelude> (1+) 2
3

Section は map 関数と組み合わせて使われることが多い。例えば上にも例示したが次のようなプログラムは、リストの引き数の各要素を二乗した新しいリストを返す。

Prelude> map (^2) [1,2,3,4,5]
[1,4,9,16,25]

詳しい説明は RWH の本文に書かれている。

As-patterns

再帰関数の the recursive part を記述するときに次のように (x:xs) というパターンを使うが、関数の body の部分で (x:xs) そのものを使いたい時がある。そのときは xs'@(x:xs) のように @ マークを使ったパターンを使うと関数の body の部分で xs' を (x:xs) として使うことができる。

RWH の例にある suffixes 関数を ghci 上で検証してみた。

Prelude> let suffixes xs@(x:xs') = xs : suffixes xs'; suffixes _ = []
Prelude> suffixes [1,2,3,4]
[[1,2,3,4],[2,3,4],[3,4],[4]]

As-pattern の詳しい説明は RWH の本文を参照してほしい。

Code Reuse Throught Composition

このサブセクションでは、関数の使い回しのパターンを説明してある。Haskell は関数を合成することで新しい関数を作り出すことができるので、関数の再利用が簡単にできる。そのため、車輪を二度発明しないという原則を実行しやすい環境がある。

RWH では As-pattens のセクションで記述した suffixes という関数を標準関数の再利用で記述して見せている。

suffixes を文字列 "foo" に関数適用すると次のような結果になる。

Prelude> suffixes "foo"
["foo","oo","o"]

ところで、Data.List モジュールの関数 tails を "foo" に関数適用すると次のようになる。

Prelude> :m +Data.List
Prelude Data.List> tails "foo"
["foo","oo","o",""]

値のリストの最後の空文字列 "" が余計なので、init 関数で取り除いてやる。

Prelude Data.List> init (tails "foo")
["foo","oo","o"]

これで suffixes 関数と同じ動作を既存の関数を組み合わせてできることが分かったので。関数再利用のプログラム suffixes2 を定義する。

Prelude Data.List> let suffixes2 xs = init (tails xs)
Prelude Data.List> suffixes2 "foo"
["foo","oo","o"]

このように既存の関数を合成して新しい関数を定義するのか簡単にできるところが Haskell の魅力のひとつだ。

ところで、init (tails xs) という式は init 関数 と tails 関数の合成を意味しているので合成関数を作る演算子 . を利用すると次のように定義できる。

Prelude Data.List> let suffixes3 xs = (init . tails) xs
Prelude Data.List> suffixes3 "foo"
["foo","oo","o"]

上の定義では関数の合成だけに注目して引き数を定義式から省略することもできる。

Prelude Data.List> let suffixes4 = init . tails
Prelude Data.List> suffixes4 "foo"
["foo","oo","o"]

RWH では関数の再利用を使って、C言語のマクロ名のみを取り出すプログラムを説明しているが、プログラムを再掲するだけに留める。

-- file: ch04/dlts.hs
import Data.List (isPrefixOf)

dlts :: String -> [String]

dlts = foldr step [] . lines
  where
    step l ds
      | "#define DLT_" `isPrefixOf` l = secondWord l : ds
      | otherwise = ds
    secondWord = head . tail . words

実行例

*Main Data.List> dlts "#define DLT_CHAOS 5"
["DLT_CHAOS"]

Use Your Head Wisely

このサブセクションではランタイムエラーを防ぐためにパターンの記述の際に起こりえるパターンの全ての可能性を考慮するように勧めている。

Tips for Writing Readable Code

このセクションでは可読性の高いコードを書くための要件について述べている。

その要件とは、

1. 無名関数や末尾再帰を使わないこと。
2. 極力ライブラリー関数を使って、ベタな再帰関数を書かないこと。
3. ライブラリー関数でできることを folds を使って書かないこと。
4. let や where を活用して局所関数もできるだけ名付きの関数を使うこと。

などのようだ。詳しくは RWH の本文に書いてある。

Space Leaks and Strict Evaluation

Haskell は遅延評価が標準だが、実用的なプログラムの場合は、正格評価を利用しなければならないことが多い。正格評価を強制する関数は seq だが、このセクションでは seq を利用した正格評価について述べてある。しかし、内容も難しいし、さしあたって必要ではないので省略する。

この記事でやっと第4章 Functional Programming が終了した。ここまでの知識で基本的な Haskell プログラムなら十分書けるようになっていると思う。

第5章以下はだんだんに実用的なプログラムを Haskell で書くにはどうするかという RWH 本来の目的が始まってくるが、ちょっと記事を書くのにつかれてきたので本当にしばらく RWH 関係の記事を終了したい。
[PR]
by tnomura9 | 2012-04-29 15:26 | Haskell | Comments(0)

RWH の読み方(39) 第4章

Real World Haskell 第4章 Functional Programming

Left Folds, Laziness, and Space Leaks

このサブセクションでは Data.List モジュールの foldl' が解説されている。

How to Think About Loops セクションを通じて畳込み関数については foldl を中心に述べられている。それは、foldl が末尾再帰関数と同等と考えてよいので手続き型の言語のループを Haskell の再帰関数に翻訳するときに便利だったからだ。

しかし、foldl は実用的なプログラムでは余り使われない。それは、遅延評価の実装の関係で、foldl は計算の手順を保存した thunk の形でメモリに保存されるからだ。thunk の形で保存にされていた式は、その評価が必要となった時に、GHC によってスタックに展開されて計算される。

したがって、foldl を遅延評価の状態で使用するときは、thunk として保存されるための多量のメモリと、評価の際のスタックの消費が必要となり、メモリ効率と速度の点でかなり効率の悪い実装になってしまう。

foldl' は foldl の計算を遅延評価ではなく正格で行うため、thunk が発生せず、メモリ効率と速度の点で有利だ。

それは、次の foldl と foldl' の計算にかかる時間を見ると良く分かる。

Prelude> foldl (+) 0 [1..100000]
5000050000
Prelude> :m +Data.List
Prelude Data.List> foldl' (+) 0 [1..100000]
5000050000

このため、理論的には foldl でプログラムを設計するが、実用的には foldl' を使うことになる。

Further Reading

このサブセクションでは、Graham Hutton の論文 "A tutorial on the universality and expressiveness of fold" が紹介されている。

長い道のりだったが、これで How to Think About Loops セクションは終わりだ。Haskell の第1の関門がループ(Haskell ではあくまで再帰関数であってループではないが)の記述法だ。このサブセクションで述べられたことを活用すれば、ループの記述であまり迷うことはないだろう。
[PR]
by tnomura9 | 2012-04-29 02:44 | Haskell | Comments(0)

どうして「なぜ?」が必要か。

フィンランドの教育法である「フィンランド・メソッド」では小学生が入学してくると、先生が生徒に「なぜ?」という質問攻めにするそうだ。

子供が小さいときに「何?」「なぜ?」攻撃を受けて苦しかったのを覚えているので、子供も大変だろうと同情するが、しかし、「なぜ?」という質問が教育の現場でどうしてそのように重要視されているのか不思議に思った。

そこで思いついたのが、アブダクションを誘発するのでないかということだ。アブダクションとは仮説的推論のことで、古くはアリストテレスの著作に端を発するらしい。また、アブダクションの例でもっとも有名なのはシャーロック・ホームズの推理だ。

現に目の前にある事柄は必ずいろいろな要件と関連がある。しかし、さしあたって目に見えないそれらの要件を探り出すきっかけになるのが「なぜ?」という質問なのだ。たとえば、杖をついて歩いている人がいるとする。それが、年寄りであっても、若い人であっても杖をつくに至った理由があるはずなのだ。

「杖をついて歩いてい人がいる」という通り一遍の観察に、「なぜその人は杖をついているのだろう?」という疑問が加わると、子細な観察がはじまる。「その杖は一本杖なのか、松葉杖なのか。どちらの足を引きずっているのだろうか。ギプスなどはしていないのだろうか。」等々さまざまな観察をひきだし、もっともふさわしそうな仮説へたどりつく。

いったん仮説ができても、それで満足してはいけない。その仮説がほんとうに適切なのか、別の仮説は考えられないのか。あるいは、仮説から推測される過去や未来の現象はどういうものなのか検証しないといけない。

目に見える現象は単純なものであっても、それに関連する背後の要件は広く複雑なものだ。それらの、関連性にまで思いが至らなければ、適切な仮説など思いつくことはできないだろう。氷山の一角を見て、本体に思いが及ばなければ本当の理解はえられない。

しかし、このアブダクションという思考はかなり脳のエネルギーを消費するらしく、普段はこのような思考活動は起きない。「なぜ?」という疑問を呼び水にすることで、ふさわしい仮説をもとめるこのような一連の思考活動を誘発することができる。

こう考えると、一見何の変哲もない「なぜ?」という疑問の重要さが分かってくる。また、試験問題をすばやく解くために、解答のパターンを覚えておくという訓練がいかに浅薄で有害なもの(大学受験にしか使えず、応用範囲が狭いという意味で)かもよくわかる。さらに、それは、受験産業の責任ではなくて、そのようなパターンを誘発する入試問題の作者の責任だということも。
[PR]
by tnomura9 | 2012-04-26 07:56 | 考えるということ | Comments(0)

RWH の読み方(38) 第4章

Real World Haskell 第4章 Functional Programming

Folding From the Right

このサブセクションでは右畳込み right fold の説明がされている。ポイントは、foldr の定義が次のプログラムであること、

foldr f z (x:xs) = f x (foldr f z xs)
foldr _ z [] = z

foldr の展開は次の式であること。

foldr (+) 0 [1,2,3] = 1 + (2 + (3 + 0))

この展開式と、元のリストの構造を比較すると

1 : (2 : (3 : []))
1 + (2 + (3 + 0))

リストのの要素の間の : を + で置き換えるようにしたものが foldr の値であることなどである。また、それだけでなく、foldr は filter のようなものも記述できる。

myfilter p xs = foldr step [] xs
  where
    step x ys
      | p x = x : ys
      | otherewise = ys

このように foldr で置き換えることのできるような再帰関数は primitive recursive と呼ばれる。

驚いたことに foldr を使って map や foldl を記述することさえできる。

myMap f xs = foldr step [] xs
  where step x ys = f x : ys

myFoldl f z xs = foldr step id xs z
  where step x g a = g (f a x)


おまけ

foldr の定義と foldl の定義を並べてみても違いがよく分からない。

foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)


foldl f z [] = z
foldl f z (x:xs) = foldl f (foldr f z x) xs

こういう時は foldr と foldl の式の展開の様子を機械に聞いてみる。

Prelude> foldr (\x y -> concat ["(step ", x, " ", y, ")"]) "z" ["1","2", "3"]
"(step 1 (step 2 (step 3 z)))"
Prelude> foldl (\x y -> concat ["(step ", x, " ", y, ")"]) "z" ["1","2", "3"]
"(step (step (step z 1) 2) 3)"

これをみると、foldr ではリストから取り出された要素が必ず step 関数の第1引き数になるのに対し、foldl では第2引き数になることが分かる。

また、初期値 z は foldr では最後に関数適用されるのに対し、foldl では括弧の最も深いところで最初に関数適用されている。(括弧を外す順序ではどちらも最後になる。)
[PR]
by tnomura9 | 2012-04-24 07:52 | Haskell | Comments(0)

RWH の読み方(37) 第4章

Real World Haskell 第4章 Functional Programming

Why Use Folds, Maps, Fiters

このサブセクションでは、前節の alder32_foldl が adler32_try2 と比べてもさほど短くならなかったのに、なぜ folds を勧めるのかを説明している。

その理由のひとつは、foldl や foldr と同じパターンの再帰関数は Haskell に非常に多く出現するので、folds の使い方に慣れておけば、明示的な再帰関数を読解するより読解が容易になるということだ。

もうひとつの理由は folds を使うことで再帰関数の性質が明確になり、コンパクトで信頼性のあるコードが書けるようになるということだ。

これは、map や filter でも同様に言えることで、高階関数を一度覚えると後はいろいろな状況でそれを利用できるようになる。

ここからは、管理人の意見。

folds や map, filter などの高階関数は、データの処理そのものを扱うのではなく、ある処理を行うにはこういうプログラミングの型を使うというような抽象的な手順を道具として使うことを可能にしている。

そのため、最初は抽象的で理解が難しいが、一旦理解するとあらゆるプログラミングに応用できて、コードも劇的にコンパクトになる。なにしろ、ループを記述しないといけないような処理を一行で片付けてしまうからだ。もちろん可読性も大いに上がる。

たたし、map や filter の動作は比較的理解しやすいが。folds の理解はどうしたらいいのだろうか。

それは、前節で述べたように、foldr は右再帰型の汎用再帰関数で、foldl は左再帰型の汎用再帰関数と考えればいいのだ。

右再帰型とか、左再帰型とかいうのは、構文解析の理論で使われる用語で再帰関数に流用していいかどうかは知らないので注意してほしい。しかし再帰関数をこの様に分類することで foldr と foldl の使い分けが明確になる。

たとえば、リストの要素を合計する関数 sum の再帰的定義は次のようになる。

sum [] = 0
sum (x:xs) = x + sum xs

この関数が実際に使用された時の式の展開の様子は次のようになる。

sum [1,2,3]
= 1 + sum [2,3]
= 1 + (2 + sum [3])
= 1 + (2 + (3 + sum []))
= 1 + (2 + (3 + 0))
= 6

このような、再帰関数では関数の再帰的な展開が右へ右へと行われていくそのため、このタイプの再帰関数を右再帰型と呼ぶことにする。この右再帰型の再帰関数は機械的に foldr に翻訳することができる。

つまり、演算 (+) を foldr の第1引き数に、sum の the base case の値 0 を foldr の第2引き数に、sum の引き数のリストを foldr の第3引き数にすればいいのだ。

Prelude> foldr (+) 0 [1,2,3]
6

foldr の式の展開を機械に聞くと次のようになる。

Prelude> foldr (\x y -> concat ["(",x," + ",y,")"]) "0" ["1","2","3"]
"(1 + (2 + (3 + 0)))"

この右再帰型の再帰関数は、リストの先頭から要素を順次取り出して処理するが、リストの最後から要素を順次取り出す計算もある。例えば [1..n] の階乗を計算するときは、大きい数の n の方から取り出して順に乗算を繰り返していく。

階乗の計算のように、リストの末尾から要素をとりだすパターンは Haskell にはないが、仮想的に (xs:x) というパターンが利用可能であるとする。すると階乗の計算のプログラムは次のようになる。

fact [] = 1
fact (xs:x) = (fact xs) * x

これを、リスト [1,2,3] に展開したものは次のようなる。

fact [1,2,3]
= (fact [1,2]) * 3
= ((fact [1]) * 2) * 3
= (((fact []) * 1) * 2) * 3
= ((1 * 1) * 2) * 3
= 6

再帰関数の展開が左へ左へと進んでいくので左再帰型の再帰関数と呼ぶことにする。

このタイプの再帰関数は foldl に翻訳できるのだ。次のように foldl を展開していけば理由がわかる。

foldl (*) 1 [1,2,3]
= foldl (*) (1 * 1) [2,3]
= foldl (*) ((1 * 1) * 2) [3]
= foldl (*) (((1 * 1) * 2) * 3) []
= (((1 * 1) * 2) * 3)
= 6

具体的な例ではリストの要素を逆転させる reverse という関数がある。これを仮想的なパターン (xs:x) を使って再帰関数で記述すると次のようになる。

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

これを foldl で実装するのだが、その前に一工夫する。foldl で reduce の際に渡される引き数の順序は f z x の順番になる。つまり、[..] : x だ。しかしこれではエラーになってしまうので、cons' z x = x : [..] となるように引き数の順番を逆転させておく。

let cons' = flip (:)

この cons' を使って reverse を foldl で実現したのが次の例だ。

Prelude> let cons' = flip (:)
Prelude> foldl cons' [] [1,2,3]
[3,2,1]

上のプログラムの展開の様子を機械に聞いてみた。

Prelude> foldl (\x y -> concat ["(","cons' ",x," ",y,")"]) "[]" ["1","2","3"]
"(cons' (cons' (cons' [] 1) 2) 3)"

中置記法の場合は次のようになる。

Prelude> foldl (\x y -> concat ["(",x," `cons'` ",y,")"]) "[]" ["1","2","3"]
"((([] `cons'` 1) `cons'` 2) `cons'` 3)"

このように左再帰型の再帰関数は foldl で簡単に書きなおすことができる。

高階関数の活用は RWH の著者たちが強調する Haskell の抽象性の実例のひとつだ。高階関数のおかげで Haskell では同じ型のループのような抽象的な概念をコードとして記述できる。このためコードが非常にコンパクトになり可読性の高いものになるのだ。
[PR]
by tnomura9 | 2012-04-22 10:11 | Haskell | Comments(0)

RWH の読み方(36) 第4章

Real World Haskell 第4章 Functional Programming

The Left Fold その3

Adler-32 チェックサム

まず、チェックサムとは何かということを、
IT用語辞典から引用してみた。 

データを送受信する際の誤り検出方法の一つ。送信前にデータを分割し、それぞれのブロック内のデータを数値とみなして合計を取ったもの。求めたチェックサムはデータと一緒に送信する。受信側では送られてきたデータ列から同様にチェックサムを計算し、送信側から送られてきたチェックサムと一致するかどうかを検査する。両者が異なれば、通信系路上でデータに誤りが生じていることになるので、再送などの誤り訂正手続きをとる。

Adler-32 チェックサムは上の原始的なチェックサムを改良したもので、Wikipedia に記述してあるアルゴリズムは次のようになる。

Adler-32 チェックサムは、まず2つの16ビットのチェックサム A と B を計算し、それらを連結して32ビットの整数にする。Aは全てのバイトの総和に1を加えた値、B は A を計算している各ステップの値を累積した総和である。

初期状態では、A は 1 に初期化され、B は 0 に初期化される。これらの総和は modulo 65521 で保持される(65521 は 216 未満の最大の素数)。これらのバイトはネットワークオーダー(ビッグエンディアン)で格納され、B が最上位バイト側に位置する。

式で表すと、以下のようになる。

A = 1 + D1 + D2 + ... + Dn (mod 65521)
B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
   = n×D1 + (n-1)×D2 + (n-2)×D3 + ... + Dn + n (mod 65521)

Adler-32(D) = B × 65536 + A

ここで D はチェックサム計算対象のバイト列の各バイトを意味し、n はバイト数を意味する。

Java のプログラム

RWH に紹介してある Adler-32 チェックサムの java プログラムは次のようになる。

public class Adler32
{
    private static final int base = 65521;

    public static int compute(byte[] data, int offset, int length)
    {
        int a = 1, b = 0;

        for (int i = offset; i < offset + length; i++) {
            a = (a + (data[i] & 0xff)) % base;
            b = (a + b) % base;
    }

    return (b << 16) | a;
    }
}

詳しい説明は RWH の本文にあるので省略するが、このプログラムの for ループの中の変数 a が Wikipedia の A に、b が B に相当する。このプログラムを Haskell の末尾再帰で記述したのが次のプログラムだ。

Haskell の末尾再帰プログラム

-- file: ch04/Adler32.hs
adler32_try2 xs = helper (1,0) xs
    where helper (a,b) (x:xs) =
              let a' = (a + (ord x .&. 0xff)) `mod` base
                  b' = (a' + b) `mod` base
              in helper (a',b') xs
          helper (a,b) _     = (b `shiftL` 16) .|. a

この末尾再帰関数の第1引き数のペアの a と b がそれぞれ Wikipedia の A と B に相当する。

Haskell の foldl のプログラム

ところで、前回の記事で示したように foldl は末尾再帰の一般形になっている。すなわち、

foldl f z (x:xs) = foldl f (f z x) xs

だ。したがって上の末尾再帰関数 helper (a,b) (x:xs) は foldl に書き換えることができるはずだ。実際に、RWH に記述されたプログラムは次のようになっている。

-- file: ch04/Adler32.hs
adler32_foldl xs = let (a, b) = foldl step (1, 0) xs
                   in (b `shiftL` 16) .|. a
    where step (a, b) x = let a' = a + (ord x .&. 0xff)
                          in (a' `mod` base, (a' + b) `mod` base)

上下のコードを比較すると、再帰関数の helper を foldl に変換しているのがわかる。

helper (a, b) [] = (b `shiftL` 16) .|. a
helper (a, b) (x:xs) = helper (a',b') xs

という再帰的定義が、

foldl step (1, 0) xs

に置き換えられている。

(1, 0) はどこから出てきたのかと思うかもしれないが、helper 関数を実際に使うときは

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

のように第1引き数に初期値を指定して利用する。

また foldl のコードに見られる step は foldl step (a, b) (x:xs) = foldl step (a_next, b_next) xs

という還元 (reduction) が起きるときの (a, b) -> (a_next, b_next) を計算するための関数だ。上の定義式の右辺に step 関数を使うと、

foldl step (a, b) (x:xs) = foldl step (step x (a,b)) xs

と書くことができる。これは、末尾再帰関数である helper が foldl という末尾再帰関数に逐語的に置き換えられたことを示している。

パターン (xs:x) で定義されるプログラム

今度は、見方を変えて、上の helper 関数を仮想的なパターン (xs:x) を使った再帰関数で定義してみよう。すると、上の定義と同じ step 関数を使って、

helper [] = (1, 0)
helper (xs:x) = step (helper xs) x

adler-32 xs = checksum $ helper xs
  where
    checksum (a, b) = (b `shiftL` 16) .|. a

と書くことができる。そうすると foldl を使って上の定義は、

foldl step (1,0) xs

で置き換えることができる。

したがって、末尾再帰関数あるいは仮想的な (xs:x) というパタンで記述された再帰関数は、逐語的に foldl に変換できることが分かる。

foldr は右再帰型の汎用の再帰関数で、foldl は左再帰型の汎用の再帰関数ととらえるとよいのではないか。そう考えると、この二つの関数で Haskell のリストを引数とするほとんどのループは記述できる。

addler32 を左再帰でプログラム設計した実際のコードは次のようになる。

import Data.Char (ord)
import Data.Bits (shiftL, (.&.), (.|.))

base = 65521

adler32 xs = shift $ helper xs
  where
    -- helper is right recursive
    -- helper [] = (1, 0)
    -- helper (xs:x) = (helper xs) `step` x
    helper xs = foldl step (1, 0) xs
    
    step (a, b) x = (a', b')
      where
        a' = (a + (ord x .&. 0xff)) `mod` base
        b' = (a' + b) `mod` base
    
    shift (a, b) = b `shiftL` 16 .|. a
[PR]
by tnomura9 | 2012-04-21 08:14 | Haskell | Comments(0)

RWH の読み方(35) 第4章

Real World Haskell 第4章 Functional Programming

The Left Fold その2

1. foldr と再帰関数

前回の記事で畳込みはループに相当する再帰関数を汎用の関数にしたものだと述べた。例えば foldr について言えば foldr (+) 0 [1,2,3] はリストの要素の和を計算するが、

Prelude> foldr (+) 0 [1,2,3]
6

これは foldr の定義から次のように展開された結果だ。

foldr (+) 0 [1,2,3]
= 1 + (foldr (+) 0 [2,3])
= 1 + (2 + (foldr (+) 0 [3]))
= 1 + (2 + (3 + (foldr (+) 0 [])))
= 1 + (2 + (3 + 0))
= 6

さらに、この展開式の結果は次のように定義された再帰関数の展開と対応する。

sum (x:xs) = x + sum xs
sum [] = 0

上の関数をリスト [1,2,3] に関数適用した時の展開のシミュレーションは次のようなる。

sum [1,2,3]
= 1 + sum [2,3]
= 1 + (2 + sum [3])
= 1 + (2 + (3 + sum []))
= 1 + (2 + (3 + 0))

上の2つの展開式を見比べれば、厳密な証明はしないが、foldr (+) 0 xs が、the recursive case が sum (x:xs) = x + sum xs で the base case が sum [] = 0 の再帰関数(によるループ)と同等であることがわかる。

したがって、このような形式の再帰関数はたやすく foldr に置き換えることができる。

たとえば、つぎのような再帰関数 example があるとすると、

example [] = []
example (x:xs) = (x ^ 2) : example xs

この関数と同じ動作を foldr (\x y -> (x ^ 2) : y) [] [1,2,3] で実行できる。これは、また、foldr を利用することで無名再帰関数を簡単に書くことができることを意味している。

Prelude> foldr (\x y -> (x ^ 2) : y) [] [1,2,3]
[1,4,9]

2. foldl と再帰関数

それでは、foldl はどのような関数なのだろうか。Prelude の foldl の定義は次のようになる。

foldl f z0 xs0 = lgo z0 xs0
  where
    lgo z [] = z
    lgo z (x:xs) = lgo (f z x) xs

ここで、あとで展開のシミュレーションがしやすいように foldl の定義を次のようにする

foldl _ z [] = z
foldl f z (x:xs) = foldl f (z `f` x) xs

この定義がうまく動作するのは次のように ghci で確認できる。

Prelude> let myfoldl _ z [] = z; myfoldl f z (x:xs) = foldl f (z `f` x) xs
Prelude> myfoldl (+) 0 [1,2,3]
6

そこで、foldl (+) 0 [1,2,3] がどのように展開されるかシミュレーションしてみる。

foldl (+) 0 [1,2,3]
= foldl (+) (0 + 1) [2,3]
= foldl (+) ((0 + 1) + 2) [3]
= foldl (+) (((0 + 1) + 2) + 3) []
= (((0 + 1) + 2) + 3)
= 6

この展開の様子を見ると、foldl がまるで末尾再帰関数であるかのように見える。第3引き数のリストの還元のたびに foldl の第2引き数に計算値が積算されていくように見えるからだ。

それでは、この foldl の展開はどんな再帰関数のそれに相当するのだろうか。

ここで、次のような再帰関数 suml を定義してみる。

suml [] = 0
suml (xs:x) = (suml xs) + x

Haskell には (xs:x) というようなパターンはないが、あると仮定してこの再帰関数を展開してみると次のようになる。

suml [1,2,3]
= suml [1,2] + 3
= (suml [1] + 2) + 3
= ((suml [] + 1) + 2) + 3
= (((0 + 1) + 2) + 3
= 6

つまり foldl は、架空のパターン (xs:x) を使った再帰関数と同等の展開結果になるのだ。

Haskell では再帰関数で漸化式を定義するには (x:xs) のようにリストの先頭の要素とそれ以外という漸化式しか書けないにも関わらず、foldl を使うと (xs:x) というパターンを使った、リストの末尾の要素とそれ以外という漸化式が事実上書けてしまうことになる。

つまり、foldr は sum (x:xs) = x + sum xs という漸化式の再帰関数を代行し、foldl は suml (xs:x) = suml xs + x というリストの末尾からの漸化式の再帰関数を代行することになる。

RWHでは Adler-32 チェックサムのプログラムを foldl で書きなおして見せているが、このプログラムは foldr で書くことはできない。それは、Adler-32 チェックサムのアルゴリズムが (xs:x) というパターンを利用するアルゴリズムになるからだ。

次回は、この観点から Adler-32 のアルゴリズムと foldl との親和性を見てみる。
[PR]
by tnomura9 | 2012-04-18 19:27 | Haskell | Comments(0)

土岐麻子

とくに意味はないのだが、何となくメモしておきたかったので。

土岐麻子 / Gift~あなたはマドンナ~
土岐麻子「ロマンチック」
土岐麻子 / 乱反射ガール (from New Album『乱反射ガール』2010.5.26 on sale)
土岐麻子 夢であえたら
土岐麻子 / ファンタジア
土岐麻子 How Beautiful

土岐麻子【渋谷店移転15周年おめでとうコメント】

TOKI ASAKO OFFICIAL WEBSITE
[PR]
by tnomura9 | 2012-04-17 21:35 | ボーカロイド | Comments(0)

RWH の読み方(34) 第4章

Real World Haskell 第4章 Functional Programming

The Left Fold

このサブセクションでは前の Computing One Answer over a Collection で作成した Adler-32 チェックサムのプログラムを左畳込み関数の foldl を使って書きなおしている。

このサブセクションを理解するためには、2つのことを理解している必要がある。まず、Adler-32 とは何かということ、もうひとつはなぜ「畳込み」を理解する必要があるのかということだ。

そこで、順番は逆になるがまず、「何で畳み込みが必要なのか」ということを考えてみる。

Haskell のリスト操作関連の高階関数の動作にはびっくりするような物がたくさんある。例えば map だ。第1引き数にリストの要素に適用したい関数を与えると、リストの全ての要素にそれぞれ関数適用した新しいリストを値として返してくれる。

Prelude> map (*2) [1,2,3,4,5]
[2,4,6,8,10]
Prelude> map (^2) [1,2,3,4,5]
[1,4,9,16,25]

これらは、本来はループを使って記述するプログラムだ。例えば、リストの要素を2倍にするプログラムは次のようになる。

double [] = []
double (x:xs) = (x * 2) : double xs

ghci で確認すると次のようになる。

Prelude> let double [] = []; double (x:xs) = (x * 2) : double xs
Prelude> double [1,2,3,4,5]
[2,4,6,8,10]

リストの要素の二乗を求めるプログラム square は次のようになる。

square [] = []
square (x:xs) = (x ^ 2) : square xs

この square と先ほどの double はプログラムの形が非常に似ているつまり次のような形をしている。

func [] = []
func (x:xs) = (f x) : func xs

square と double は先頭の要素に適用する関数 f が違っているだけだ。それなら f を引き数として与えることでこのループそのものを関数にしてみたらどうだろう。

myMap f [] = []
myMap f (x:xs) = (f x) : myMap f xs

これも ghci で試してみた。

Prelude> let myMap _ [] = []; myMap f (x:xs) = (f x) : myMap f xs
Prelude> myMap (*2) [1,2,3,4,5]
[2,4,6,8,10]

驚いたことに、Haskell はこのように「形の似たプログラム」という抽象的なものも関数にしてしまうことができる。

それでは「畳込み」についてはどうだろうか。

「畳込み」の関数 foldr や foldl を始めて使ってみたときは、何のことかさっぱり分からなかった。foldr を使うと sum や product と同じことができるのは分かるが、だからどうなのという気がした。ちなみに、sum や product の動作を forldr でさせると次のようになる。

Prelude> foldr (+) 0 [1,2,3,4,5]
15
Prelude> foldr (*) 1 [1,2,3,4,5]
120

これだけでは、sum や product をわざわざ複雑にしただけでなにがありがたいのかということになる。

しかし、これも map のときと同じで、「似た形のループ」という抽象的な概念を関数にしたものだと考えるとその意味が分かる。たとえば、sum と product のプログラムは次のようになる。

sum [] = 0
sum (x:xs) = x + sum xs

product [] = 1
product (x:xs) = x * product xs

上の2つのプログラムの共通部分を関数にすると次のようになる。

myFoldr f zero [] = zero
myFoldr f zero (x:xs) = x `f` (myFoldr f zero xs)

これも ghci で試してみることができる。

Prelude> let myFoldr _ zero [] = zero; myFoldr f zero (x:xs) = f x (myFoldr f zero xs)
Prelude> myFoldr (+) 0 [1,2,3,4,5]
15

このように「畳込み」関数とはループという抽象的な操作を関数に落とし込んだものだと考えるとそのありがたみが分かる。また、foldr の動作はそのシミュレーションを手書きでやってみると理解できる。

foldr (+) 0 [1,2,3]
= 1 + (foldr (+) 0 [2,3])
= 1 + (2 + (foldr (+) 0 [3]))
= 1 + (2 + (3 + (foldr (+) 0 [])))
= 1 + (2 + (3 + 0))
= 6

また、foldr の動作は直接機械に教えてもらうこともできる。

Prelude> foldr (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..5])
"(1+(2+(3+(4+(5+0)))))"

foldl の解釈は foldr より少し複雑になるので稿を改めるが、ここで、なぜ畳込みが必要かということについて考えてみたい。ループを畳み込みに置き換えることでどのような利点が発生するのだろうか。

それは、ループを folds に置き換えることでそのループの性質を明示することができるということだ。つまり、map を使った時と foldr を使ったときは異なる種類のループを使っていることを意味している。どんな性質のループを使っているのかを意識しながら使うことができるということだ。

もうひとつは明示的にループを書くよりも簡潔になり可読性を上げタイポを減らすことができる。

いろいろな意味で、リストから単一値を求めるようなプログラムでは、積極的に folds を使う理由がある。
[PR]
by tnomura9 | 2012-04-16 07:56 | Haskell | Comments(0)

踊ってみた美女図鑑

踊ってみたの美人ダンサーを集めてみた。

【いくらミンカ】メランコリックを踊ってみた【魚民】
【みうめ×れいちぇる】リモコン踊ってみた
【ぱん2×こずえ】magnet【踊ってみた】
【@ちーちゃん】バンギャル症候群 踊ってみた【小太郎】
【ねこみみ少女 & 梨乃子】Sweetie×2 踊ってみた【らぶらぶ】HD
【マリス+ぁゆ子】純情☆ファイター踊ってみた【ステーキ】
【DANCE SMILE】光速姉妹【ソレイユの丘】
【もじうさ&あぷりこっと*】Tomur踊ってみた【あぷ*ω*うさ】
【AMU×LUNA】踊ってみた リモコン 【リンレンコス】
[AMU & Hima ] PONPONPON
【BadApple!!】 傷林果 【Japanese Traditional Dance】lyrics & Romaji
【きりり】Senbonzakura【りりり&鬼兵】
【ゆりにゃ】少女未遂踊ってみた【JS最後】
DISCOTHEQUE 【Mirrored】
【足太ぺんた】千本桜 踊ってみた【桜の下で】
【きょお☆】くれよん / Crayon 踊ってみた【ちえ】HD
【わたとぺんたで】キップル・インダストリー踊ってみた【わっぺん。】
【東と加藤】ロゼッタ振り付けてみた【撮り直してみた】HD
【こずえとマリス】I ♥を踊ってみた
【歯茎ピペット】Mermaid マーメイド 踊ってみた【オリジナル振付】HD
【いとくとら】MelodyLineを踊ってみた【あすきょう】
【@小豆】『プラチナ』-shin'in future Mix- 【リベンジ動画
【MAP】Mr. Wonderboy 歌って踊ってみた 【オリジナル振り付け】HD
【うんぱるんぱ】『プラチナ』-shin'in future Mix-を踊ってみたHD
【らんほ】Lily Lily★Burning Night リリリリ★バーニングナイト踊ってみた
【ちゅいが】Yaranaika やらないかを1.25倍速で【踊ってみた】HD
【ぬこ田】Mirai Tokei 未来時計AM4:30 踊りました【誕生日に】
【ぬこ田・hi-lite・のn】Snow Trick スノートリック踊ってみたHD

注:もじうさは「美女うさぎ」
[PR]
by tnomura9 | 2012-04-15 18:08 | ボーカロイド | Comments(0)