インデントスタイル(またはレイアウトシステム)

入門Haskell」ではインデントスタイルについては,必要なときにその都度,といった感じでまとまった説明がなかった。

moiの頭の中 – 3.5 Functions(その3)

Haskellはコードを構築するのに「レイアウト」と呼ばれるシステムを用いる(プログラミング言語Pythonは似たシステムを用いている)。レイアウトシステムは、CやJavaのような他の言語が必要とする明示的なセミコロンや中括弧なしでコードを書くことができる。

moiの頭の中 – 3.5 Functions(その4)

レイアウトについての一般的な規則は、let、doそしてofキーワードの位置の次に開き中括弧が挿入され、次の命令が現れる桁位置が記憶されることである。それ以降、セミコロンが同じ量を字下する全ての行の前に追加される。次の行を字下げしないなら、閉じ中括弧が追加される。

つまり,let,do,of のあとに続く語とそれに続く行の先頭をそろえろってことだな。こんな風に。

f x = case x of 1 -> "one"
                2 -> "two"
                3 -> "three"
                _ -> "many"

中括弧やセミコロンが云々というのは,上のコードがこんな風に解釈されるってことか。

f x = case x of {1 -> "one";
                 2 -> "two";
                 3 -> "three";
                 _ -> "many"}

ようするに見やすく書けば問題なさそうだ。

ところで,if ~ then ~ else や where 節については書いてないがどうなんだろう。
まずはif ~ then ~ else から。いままで then,else は if よりも下げて書いてたけどおなじインデントでも大丈夫。

f x = if x > 0
      then "Positive"
      else "Negative or Zero"
*Main> f 0
"Negative or Zero"

if よりも前にあっても大丈夫のようだ。

f x = if x > 0
    then "Positive"
  else "Negative or Zero"
*Main> f 2
"Positive"

なら where 節は?

f x = map g x
  where g 0 = 1
        g 1 = 0
*Main> f [1,0,0,1,1,1]
[0,1,1,0,0,0]

こっち(↓)がダメなのは,関数(g)定義の先頭があってないからだろうな。

f x = map g x
  where g 0 = 1
      g 1 = 0
*Main> :l ind.hs
Compiling Main             ( ind.hs, interpreted )

ind.hs:14:8: parse error on input `g'

ついでにガード節。これも大丈夫なんだ。

f x | x < 0 = (-1) * x
  | x > 0 = 1 * x
 | otherwise = 0
*Main> f 3
3
*Main> f 0
0
*Main> f (-2)
2

まとめ。

  • let,do,of のあと(という中というか)は頭をそろえる。
  • 関数定義の頭はそろえる。
  • where 節やガード節はそろえなくても大丈夫(だけど見やすいようにそろえる)。

入出力と do 記法

プログラムと言うからには入力と出力を扱えなきゃいけない。でないと何の役にも立たないからな。
ただ,純粋関数型言語の Haskell にとってはこの入出力というのは特殊なもののようだ。

  • 入出力は手続き的にならざるを得ない。なぜなら出力が入力よりも先に行えるはずがないから。だから,いつ,どんな順で評価しても結果が変わらない他の関数とはちがう。
  • 副作用がある。入出力をする関数を評価すると,評価の結果として値が返ってくるのとはべつに,入力を受け取ったり,画面に何かを出力したりということが起こる。これを副作用という。
  • 評価するたびに結果が異なる。たとえば Ruby では gets で標準入力から値を得ることができるけど実行するたびに違う値が返ってくる。Haskell ではこれはまずい。

Haskell ではこのような問題を避けるために特別な仕組みがある。それが do 記法。
口(?)で説明するのは難しいので例を示す。このプログラムはコマンドラインから受け取ったパラメータを標準出力に出力する。ようするに echo だ。

import System

main = do args <- getArgs
          putStr $ unlines args

この do 記法の中には2つの動作 (action) がある。 args <- getArgs でコマンドラインパラメータを受け取ってargsに代入する(空白で区切られて文字列のリストになる)。そして putStr $ unlines args で標準出力へ1行にひとつずつ出力する。do 記法の中の action は順番に実行される。 この様に do 記法の中ではプログラムの他の部分と違って手続き的に書くことができる。というか,(Haskellにとって)異質なものを他の部分から分離している,という方がいいだろうか。 もう少し詳しく言うと,do記法はべつに入出力のためだけのものではなくて,モナドという仕組みなんだけど,このモナド,なんだかよくわからないのでここでは脇に置いておく。とにかく,標準入出力やファイルを使おうとしたら do 記法を使えばいいってことだ。 上のプログラムをコンパイルして実行するとこうなる。あ,import System は getArgs を使うのに必要。

>type hecho.hs
import System

main = do args <- getArgs
          putStr $ unlines args

>ghc -o hecho hecho.hs

>hecho abc def ghi
abc
def
ghi

OK。これでプログラムが書けるぞ。

uniq

入出力の練習(その2)。

import System

main = do args <- getArgs
          mapM_ uniqFile args

uniqFile fileName = do contents <- readFile fileName
                       putStr $ unlines $ uniq $ lines contents

uniq [] = []
uniq (c:cs) = uniq' c cs
  where uniq' str [] = [str]
        uniq' str (c:cs) 
            | str == c = uniq' str cs
            | otherwise = [str] ++ uniq' c cs

結果。

>cat sample.txt
Perl
Perl
Ruby
Ruby
Ruby
Javascript
VBA
Haskell
Haskell
>uniq sample.txt
Perl
Ruby
Javascript
VBA
Haskell

cat

入出力の練習。ファイルの内容を表示する。

import System

main = do args <- getArgs
          mapM_ catFile args

catFile fileName = do contents <- readFile fileName
                      putStr $ contents

コンパイルして実行。

>cat sample.txt
FORTRAN
AWK
sed
C++
Perl
Ruby
Javascript
VBA
Haskell

readFile はファイルを読み込む。 mapM_ は動作を繰り返す。この場合は引数に指定したファイルについて繰り返す。

>cat week.txt year.txt
Sun
Mon
Tue
Wed
Thu
Fri
Sat
Jan
Feb
Mar
Apl
May
Jun
Jul
Aug
Seb
Oct
Nov
Dec

練習問題

入門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