投稿者: takatoh

cf. id:pylet:20060416

最近のトレンドとしては、やっぱりHello, Woldの次はフィボナッチ数列ですよね(!?)

そうそう，フィボナッチ数列だよ。Haskell なら１行で書ける……って，本に書いてあったものを自慢しても仕方がないので，それを見る前に自分で書いたものをさらしておく。

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

*Main> fib 10
89

これは id:pyletさんのfib1（再帰版）に相当する。
リストを得るには関数をもうひとつ。

fibNumbers 0 = [1]
fibNumbers 1 = [1,1]
fibNumbers n = fibNumbers (n-1) ++ [fib n]

これで第n項までのリストが得られる（初項を第0項とする）。

*Main> fibNumbers 10
[1,1,2,3,5,8,13,21,34,55,89]

ちなみに，ループ版は Haskell ではできない。たぶん。

で，こうすると１行で書ける。

fibonacci = 1:1:zipWith (+) fibonacci (tail fibonacci)

これだけ。これでフィボナッチ数列のリストが得られる。注目すべきなのは得られるリストが無限リストだということ。ほっとくといくらでも数字をはき続ける（まぁ，そのうちリソースを食いつぶして止まるんだろうけど）。

*Main> fibonacci
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,
28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,570
2887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,4
33494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,125862
69025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,
365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881
,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723
460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515
533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,89
44394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721
611591,99194853094755497,160500643816367088,259695496911122585,42019614072748967
（以下略）

第10項がほしければこうする。

*Main> fibonacci !! 10
89

id:nobsun さんからコメントをもらった。ありがとうございます。

fib n = fibIter 1 1 n
  where fibIter a b 0 = a
    fibIter a b n = fibIter b (a+b) (n-1)

（※ちょっと変えました）

*Main> map fib [1..10]
[1,2,3,5,8,13,21,34,55,89]

id:nobsun さんはこれ（↑）が id:pyletさんとこのループ版と同等だというのだけど，むしろ反復版（↓これ）と同等じゃないのかなぁ。

def fib3_iter(a, b, i, n):
    if i == n:
        return a
    else:
        return fib3_iter(b, a + b, i + 1, n)

def fib3(n):
    return fib3_iter(1, 1, 0, n)

このPythonの関数（メソッド？）はカウンタに変数 i を使っているけど，重要なのは n と i の差 n-i なんだから n-i -> n に置き換えて n 自身をカウンタに使えば i をなくせる。内側のfib3_iterの引数は n-(i+1) = (n-i)-1 -> n-1 と置き換えられるから

def fib3_iter(a, b, n):
    if n == 0:
        return a
    else:
        return fib3_iter(b, a + b, n - 1)

def fib3(n):
    return fib3_iter(1, 1, n)

これならまさしく上のHaskellと同じだ。

あー，でも，そうか。既知の第0項と第1項をもとにして第n項まで頭から順に計算していく，という点ではどっちも同等だといえるのか。
いや，まて。再帰してる反復版ではスタックを積まなきゃいけないけどループ版ではいらないはずだな。
いやいや，遅延評価するからいらないのか？……違うか？
だめだ。わかんなくなった。

「入門Haskell」のp.31から二つ目。

② 単語のカウント方法として，`Theory of Everything’のようにバッククォートとシングルクォートで囲まれたパートを，１つの単語として表現するように wordsCount を拡張しなさい。

オリジナルの wordsCount。

wordsCount str = outWords str
    where outWords [] = 0
          outWords (c:cs)
              | isAlphaNum c = 1 + inWords cs
              | otherwise = outWords cs
          inWords [] = 0
          inWords (c:cs)
              | isAlphaNum c = inWords cs
              | otherwise = outWords cs

拡張版。

wordsCount str = outWords str
    where outWords [] = 0
          outWords (c:cs)
              | c == '`' = 1 + inQuote cs
              | isAlphaNum c = 1 + inWords cs
              | otherwise = outWords cs
          inWords [] = 0
          inWords (c:cs)
              | c == '`' = 1 + inQuote cs
              | isAlphaNum c = inWords cs
              | otherwise = outWords cs
          inQuote [] = 0
          inQuote (c:cs)
              | c == '\'' = outWords cs
              | otherwise = inQuote cs

結果。

*Main> wordsCount "`Theory of Everything' by Greg Egan"
4

「入門Haskell」のp.31から。
まずは一つ目。linesCountの拡張

① linesCountでは，空白行が続く場合にどんどんカウントしてきます。これを空白行（何もない行）を無視するように拡張しなさい。

オリジナルのlinesCount。

linesCount [] = 0
linesCount ('\n':cs) = 1 + linesCount cs
linesCount (c:cs) = linesCount cs

結果。1st line，2nd line … は空行を無視した行番号で，1st line と2nd lineの間に空行がある。

*Main> linesCount "1st line\n\n2nd line\n3rd line\n"
4

で，拡張版。

linesCount lines = atHead lines
    where atHead []        = 0
          atHead ('\n':cs) = atHead cs
          atHead (c:cs)    = 1 + inLine cs
          inLine []        = 0
          inLine ('\n':cs) = atHead cs
          inLine (c:cs)    = inLine cs

結果。

*Main> linesCount "1st line\n\n2nd line\n3rd line\n"
3

定義。

even1 = [2,4..]
even2 = filter (\x -> x `mod` 2 == 0) [1..]
even3 = filter (\x -> x `mod` 2 /= 1) [1..]
even4 = zipWith (+) [1..] [1..]
even5 = map (\x -> x * 2) [1..]
even6 = 2:(map (2+) even6)
even7 = map (\x -> sum $ replicate x 2) [1..]
even8 = scanl (\x y -> x + y) 2 $ repeat 2
even9 = scanl1 (\x y -> x + y) $ repeat 2
even10 = map (\x -> sum $ take x $ repeat 2) [1..]
even11 = map (\x -> length $ replicate (x*2) "Haskell") [1..]
even12 = iterate (2+) 2

結果。

*Main> take 20 $ even1
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40]
*Main> take 20 $ even2
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40]
*Main> take 20 $ even3
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40]
*Main> take 20 $ even4
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40]
*Main> take 20 $ even5
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40]
*Main> take 20 $ even6
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40]
*Main> take 20 $ even7
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40]
*Main> take 20 $ even8
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40]
*Main> take 20 $ even9
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40]
*Main> take 20 $ even10
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40]
*Main> take 20 $ even11
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40]
*Main> take 20 $ even12
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40]

foldl と foldr はちょっとわかりにくい。なのでこんなのを書いてみた。
括弧内の数字は引数を表している。0 が初期値で 1, 2, 3… がリストの各要素。内側の括弧から順に評価される。
foldl はこう。

*Main> foldl (\x y -> "(" ++ x ++ "," ++ y ++ ")" ) "0" ["1","2","3","4","5"]
"(((((0,1),2),3),4),5)"

で foldr はこう。

*Main> foldr (\x y -> "(" ++ x ++ "," ++ y ++ ")" ) "0" ["1","2","3","4","5"]
"(1,(2,(3,(4,(5,0)))))"

何となくわかりやすい……？

パターンマッチングの後，引数の具体的な値を条件に分岐したい場合には次のように書く。
| と = の間の分岐条件の部分をガード節という。
条件は上から順にチェックされる，でいいのかな。otherwise は「その他の場合」。

swapCase は文字列の中の大文字と小文字を入れ替える。アルファベットでないならそのまま。

import Data.Char

swapCase []     = []
swapCase (c:cs)
    | isUpper c = (toLower c):(swapCase cs)
    | isLower c = (toUpper c):(swapCase cs)
    | otherwise = c:(swapCase cs)

*Main> swapCase "Haskell"
"hASKELL"
*Main> swapCase "03^-c,aa"
"03^-C,AA"

ある関数の内部で別の関数が評価されるとき，もしその内部の関数がプログラムのほかのどの部分でも評価されないなら－－言い換えればその場でしか使われないなら，その関数を局所的な定義にすることができる。局所的に定義された関数はプログラムのほかの部分からは見えなくなる。
局所的な定義はインデントを下げて where と書いたあとに続けて通常の関数定義と同じように書く。
where 以降を where 節という。

というわけで Capitalize をこうしてみた（関数名は先頭に大文字を使えないから capitalize）。

import Data.Char

capitalize []     = []
capitalize (c:cs) = (toUpper c):(lower cs)
    where lower []     = []
          lower (c:cs) = (toLower c):(lower cs)

先頭の文字だけ大文字にして，２文字目以降は局所的に定義された lower を適用している。where 以降が lower の定義。

実行結果。

*Main> capitalize "haskell"
"Haskell"

追記：
map を使えば lower なんて関数を定義しなくてもすむ。

capitalize []     = []
capitalize (c:cs) = (toUpper c):(map toLower cs)

*Main> capitalize "haskell"
"Haskell"

Capitalize ならぬ capitalizE。字面どおり最後の文字だけを大文字に変える。
……いや，名前はともかく（っていうか，こんな動作に名前がついてるとは思えないが）。
toUpper や toLower を使うには Data.Char モジュールを import する。

import Data.Char

capitalizE []     = []
capitalizE [c]    = (toUpper c):[]
capitalizE (c:cs) = (toLower c):(capitalizE cs)

実行結果。

*Main> capitalizE "Haskell"
"haskelL"

OK。

で，Capitalize のほう。こうやったら全部大文字になった。

capitalize []     = []
capitalize (c:cs) = (toUpper c):(capitalize cs)

*Main> capitalize "haskell"
"HASKELL"

”リストの先頭”は常にあるんだから当然だよな。

要素と要素の間ごとに新しい要素を挟み込む。

join s []     = []
join s (c:cs) = c:s:(join s cs)

実行結果。

*Main> join '-' "abc"
"a-b-c-"

あれ？

そうか，一番最後の要素も c:cs にマッチングしてるんだな。てことは”最後の要素”を表すパターンがあればいいのか。これでどうだ。

join s []     = []
join s (c:[]) = c:[]
join s (c:cs) = c:s:(join s cs)

実行。

*Main> join '-' "abc"
"a-b-c"

OK。