練習問題

入門Haskell―はじめて学ぶ関数型言語」 p.33 より。

wordScan 利用版の wordsCount で,同じように `~’ を1単語と見なす拡張を追加しなさい。またその際,wordScan を積極的に利用すること。

これはめんどくさかった。
まずは`~’に対応していない wordScan 利用版。

wordsCount2 str = outWords str
  where wordScan f []   = 0
        wordScan f (c:cs)
         | isAlphaNum c = f (inWords cs)
         | otherwise    = outWords cs
        outWords str = wordScan (\n -> 1 + n) str
        inWords str = wordScan id str

それから`~’に対応してるけど wordScan を利用しない版。

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

このうちの条件分岐を wordScan の中に押し込めるんだけど,次に呼び出す関数との組み合わせをどうやったらうまく整理できるか,でずいぶんと試行錯誤した。
表にするとこんなふうになる。縦の軸が wordScan を呼び出す関数,横の軸が分岐条件で,各欄に書いてあるのはカウントアップのための関数と次に呼び出す関数。

c == ‘`’ c == ‘\”isAlphaNum cotherwise
 outWords(1+) inQuoteoutWords(1+) inWordsoutWords
inWords(1+) inQuoteoutWordsid inWordsoutWords
inQuoteid inQuoteoutWordsid inQuoteinQuote

右上の2×2マスが拡張前の版に相当する。この場合はどの関数(outWOrdsとinWords)から呼び出されても次に呼び出す関数は,条件ごとにおなじだった。
それが,拡張版ではおなじ条件でもどの関数から呼び出されたかによって,次に呼び出す関数が変化する。しかも isAlphaNum c のときと otherwise のときの2つもだ。
だからこの2つのときに呼び出すべき関数を wordScan に引数として与えてやることにした。

wordsCount2 str = outWords str
  where wordScan f g1 g2 [] = 0
        wordScan f g1 g2 (c:cs)
          | c == '`' = (1+) (inQuote cs)
          | c == '\'' = outWords cs
          | isAlphaNum c = f (g1 cs)
          | otherwise = g2 cs
        outWords str = wordScan (1+) inWords outWords str
        inWords str = wordScan id inWords outWords str
        inQuote str = wordScan id inQuote inQuote str

wordScan は関数を3つ(f,g1,g2)と文字列を1つ引数にとるようになった。f はカウントアップのための関数,g1とg2はそれぞれisAlphaNum c ,otherwise のときに呼び出す関数だ。
で,実行結果。

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

うん,ちゃんと `~’ を1単語と認識してるな。

高階関数とカリー化

map,zip,zipWith などのように引数に関数をとる関数を高階関数という。

まぁ,すでに今までにもずいぶん使ってるんだけど。
ちょっと練習。chrOr,chrAnd は ‘1’ または ‘0’ を2つ引数にとってビット演算もどきをする。
zipWith と組み合わせれば文字列のビット演算もどきができる。

chrOr a b | a == '1' || b == '1' = '0'
          | otherwise            = '1'

chrAnd a b | a == '1' && b == '1' = '1'
           | otherwise            = '0'
*Main> zipWith chrOr "10010010" "10011100"
"01100001"
*Main> zipWith chrAnd "10010010" "10011100"
"10010000"

複数の引数をとる関数に,より少ない数の引数を与えると,残りの数の引数をとる関数ができる。これをカリー化という。
ちょっと説明がわかりにくいな。たとえば2つの引数をとる関数 f a b に引数を1つだけ与えると,1つの引数をとる関数 g b ができるってこと。
上の例で言えば,zipWith に chrOr やchrAnd を与えると strOr や strAnd ができる。

strOr = zipWith chrOr

strAnd = zipWith chrAnd
*Main> strOr "10010010" "10011100"
"01100001"
*Main> strAnd "10010010" "10011100"
"10010000"

フィボナッチ数列

cf. id:pylet:20060416

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

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

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 ではできない。たぶん。

で,こうすると1行で書ける。

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’のようにバッククォートとシングルクォートで囲まれたパートを,1つの単語として表現するように 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]

リストを操作する関数(その3)

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 以降を where 節という。

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

import Data.Char

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

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

実行結果。

*Main> capitalize "haskell"
"Haskell"

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

capitalize []     = []
capitalize (c:cs) = (toUpper c):(map toLower cs)
*Main> capitalize "haskell"
"Haskell"