概要

すごいH本読書会@渋谷某所 #3, #4 での話題です。
#3, #4 では、第3, 4, 5章を読了しました。

次回 #5 は 2015/03/05 19:30 から渋谷某所で行います。というか、今日です。

今回話題になった内容は以下の通り。

フィボナッチ数列
カリー化と部分適用
第一引数以外への部分適用
filterの述語に&&を使う方法

優しくまさかりを飛ばして下さる方大歓迎です。
厳しいまさかりも頑張って受け止めます。

フィボナッチ数列

公式サイト曰く、フィボナッチ数列は Hello World らしい。種類多すぎわろた。

Implementing the Fibonacci sequence is considered the "Hello, world!" of Haskell programming.

The Fibonacci sequence

今回の勉強会では、3種類のフィボナッチ数列についてだけ触れました。

まずは1つめ、シンプルに定義通り書き下した場合。

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

こいつは鬼のように重い。多分2分木っぽくなるので、計算量はざっくりO(2^n)とかそれ系な気がします。ググってみたらフィボナッチ数の計算と計算量というページがヒット。どうやら計算量はO( ((1 + sqrt(5)) / 2)^n-1 )になるらしい。

次に、試したのがこの書き方。計算した結果を覚えておく（メモ化する）方法。

fib n = fibs !! (n-1) + fibs !! (n-2)
fibs = 1:2:[fib i | i <- [2..] ]

最後はzipWith (+)を使ったフィボナッチ数列。これは癖が強くて読みにくい。
この3つの中だとzipWithを使った方法が最も計算が早かった。

fibs = 1:2:zipWith (+) fibs (tail fibs)

イメージとしては次のような感じ。

1 2 x y z .. n ..
    1 2 x .. n-2 ..
    2 x y .. n-1 ..

x = 1 + 2
y = 2 + x
z = x + y
  :
  :
n = n-2 + n-1

例えば、「fibsの4項目fibs !! 4を知りたい！」といった場合は次のようになる。

zを知りたい！そのためにはyとzが必要……。
x = 1+2 = 3
y = 2+y = 2+3 = 5
z = x+y = 3+5 = 8

4項目を出すには計算が3回必要、5項目は4回、n回目はn-1回といった感じ。おそらく計算量はO(n)になるかと思う。

……アルゴリズムと計算量の勉強し直そう。

カリー化と部分適用

カリー化と部分適用は全く別の概念です。詳細についてはこちらの資料がわかりやすかったです。

詳細な説明については、上記の資料を見ていただければと思います。

カリー化

カリー化 (currying, カリー化された=curried) とは、複数の引数をとる関数を、引数が「もとの関数の最初の引数」で戻り値が「もとの関数の残りの引数を取り結果を返す関数」であるような関数にすること（あるいはその関数のこと）である。

Wikipedia: カリー化

複数引数の関数、これを単一引数の関数の組み合わせに変換することがカリー化。 Curring, Curried の2つの意味で使われることがありそうなので注意。

Curring: 関数をカリー化すること
Curried: カリー化された関数のこと

部分適用

複数引数の関数の一部変数のみ束縛した新たな関数を得る操作。

カリー化されていると、1引数目への部分適用が非常に簡単になる。 flip 使えば 2引数目への部分適用も容易。

第一引数以外への部分適用

次のような疑問が勉強会中に出ました。

f x y zのような関数に対してyやzだけに部分適用したい場合、果たして Haskell ではどう記述するのだろうか。どうやらScalaではf _ 2 _のような感じで_を用いて書けるとのことらしい。

Haskell ではおそらく、以下で実現できます。

そのまま書く
flipを使う
セクション化
ラムダ式を使う

そのまま書く

そのまま書けます。

Prelude> let f a b c = a:b:c:[]
Prelude> let f' a b = f a b 3
Prelude> f' 1 2
[1,2,3]

Prelude> let f a b c = a:b:c:[]
Prelude> let f' a b c = f b c a
Prelude> let f'' = f' 3
Prelude> f'' 1 2
[1,2,3]

非カリー化（引数がタプル）でも大丈夫。第何引数へも部分適用できちゃいます。

Prelude> let f(a,b,c) = a:b:c:[]
Prelude> let f'(a,b) = f(a,b,3)
Prelude> f'(1,2)
[1,2,3]

Prelude> let f(a,b,c) = a:b:c:[]
Prelude> let f'(a,b) = f(a,b,3)
Prelude> let f''(b) = f'(1,b)
Prelude> f''(2)
[1,2,3]

flip を使う

第二引数に部分適用するだけならflipを使えば楽勝です。

Prelude> let f a b c = a:b:c:[]
Prelude> let f' = flip f 2
Prelude> f' 1 3
[1,2,3]

第一引数と第三引数を入れ替える flip 関数を定義すれば第三引数への部分適用もできます。

Prelude> let f a b c = a:b:c:[]
Prelude> let flip31 f a b c = f b c a
Prelude> let f' = flip31 f 3
Prelude> f' 1 2
[1,2,3]

セクション化

こちらも第二引数に部分適用するだけなら楽勝です。

Prelude> let f a b c = a:b:c:[]
Prelude> let f' = (`f` 2)
Prelude> f' 1 3
[1,2,3]

Prelude> let a = (`div` 10)
Prelude> a 100
10
Prelude> let b = (10 `div`)
Prelude> b 100
0

ラムダ式を使う

ラムダ式を使えば自由自在！

Prelude> let f a b c = a:b:c:[]
Prelude> let f' =  \a b -> f a b 3
Prelude> f' 1 2
[1,2,3]

filter の述語で && を使う方法

すごいH本の P.70 に&&もfilterの述語に使えるよ！と書いてあったのに、全く使い方が書いてなかったので、試してみました。

まずは何も考えずに書いてみる。

Prelude> filter (<15) && even [1..20]

<interactive>:57:1:
    Couldn't match expected type ‘Bool’ with actual type ‘[a0] -> [a0]’
    Probable cause: ‘filter’ is applied to too few arguments
    In the first argument of ‘(&&)’, namely ‘filter (< 15)’
    In the expression: filter (< 15) && even [1 .. 20]

ふむ、ダメです。Bool 型を寄越せとのことです。

Prelude> filter (\x -> x < 15 && even x) [1..20]
[2,4,6,8,10,12,14]

できました。

次回も楽しく読み進めていきましょう！

雀巽の日記帳

雀巽が綴る日常の記録

すごいH本読書会@渋谷某所 #3, #4

概要