関数型言語に慣れる - capriccioso String Creating(Object something){ return My.Expression(something); }

Haskellの勉強を始めたのは、先日のエントリで書いたとおりです。

それまでも、なんとなくLispを触ってみた事はあったのですが、表面を撫でた程度で終わっていたので、これでようやく関数型言語への本格的な第一歩を踏み出した事になります。

今はちょうど、すっかり頭が「手続き言語脳」になっている事を、思い知らされている所です。
とりあえず新しい考え方に慣れていかないといけませんね。

試しに、フィナボッチ数を計算してみました。

module Fib where

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib x = fib (x-1) + fib (x-2)

漸化式そのままですが、自力ではこれが限界。
とりあえず計算はちゃんとできるので、これを使って色々ためしてみます。

tune@tune-pgmPC:~/Proguram/Haskell/Test03$ ls -l
合計 4
-rw-r--r-- 1 tune tune 94 2011-10-08 01:48 Fib.hs
tune@tune-pgmPC:~/Proguram/Haskell/Test03$ ghci Fib.hs
GHCi, version 6.12.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Fib              ( Fib.hs, interpreted )
Ok, modules loaded: Fib.
*Fib> let fibLst = map fib [0,1..]
*Fib> fibLst
[0,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,^CInterrupted.
*Fib> zip [0,1..] fibLst
[(0,0),(1,1),(2,1),(3,2),(4,3),(5,5),(6,8),(7,13),(8,21),(9,34),(10,55),(11,89),(12,144),(13,233),(14,377),(15,610),(16,987),(17,1597),(18,2584),(19,4181),(20,6765),(21,10946),(22,17711),(23,28657),(24,46368),(25,75025),(26,121393),(27,196418),(28,317811),(29,^CInterrupted.
*Fib> let takeFibLst x = take x fibLst
*Fib> takeFibLst 30
[0,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]
*Fib> let square x = x*x
*Fib> map square fibLst
[0,1,1,4,9,25,64,169,441,1156,3025,7921,20736,54289,142129,372100,974169,2550409,6677056,17480761,45765225,119814916,313679521,821223649,2149991424,5628750625,14736260449,38580030724,101003831721,264431464441,692290561600,^CInterrupted.

どれも手続き言語だといくらか頭をひねる必要のありそうな処理ですが、Haskellなら対話形式で簡単に記述できます。
入り口の敷居さえ跨いでしまえば、「ちょっとした計算はとりあえずできるようにする」段階まではむしろ手続き言語より簡単かもしれません。

とはいえ、漸化式をそのまま記述すると、計算に無駄が多く処理に時間がかかるので、もっと良い方法があるはずと色々検索してみた所、シンプルで解りやすい例を発見しました。

*Fib> let fibc a b = a : fibc b (a+b)
*Fib> let fib2 = fibc 0 1
*Fib> take 30 fib2
[0,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]

リストの最初の要素として0と1を渡せば、あとの要素は再帰処理で評価していくだけです。

自分でも遅延評価を使うところまではイメージできていたのですが、引数一つでどうにかしようと奮闘して結局答えに辿りつけませんでした。ううん、頭が硬い。

そして一番よく見かける例が、次の１行で書き下しているパターン。

*Fib> let fib3 = 0 : 1 : zipWith (+) fib3 (tail fib3)

zipWithという関数を知ったので、色々実験してみます。

*Fib> zipWith (+) [1,2,3] [4,5,6]
[5,7,9]
*Fib> zipWith (*) [1,2,3] [2,2,2]
[2,4,6]
*Fib> zipWith (++) [[1,2,3],[4,5,6],[7,8,9]] [[9,8,7],[6,5,4],[3,2,1]]
[[1,2,3,9,8,7],[4,5,6,6,5,4],[7,8,9,3,2,1]]

関数の効果自体は簡単ですね。実際に上のfib3関数で何が行われているか追うと、どうなるでしょうか。

*Fib> zipWith (+) [0,1] [1]
[1]
*Fib> zipWith (+) [0,1,1] [1,1]
[1,2]
*Fib> zipWith (+) [0,1,1,2] [1,1,2]
[1,2,3]
*Fib> zipWith (+) [0,1,1,2,3] [1,1,2,3]
[1,2,3,5]
*Fib> zipWith (+) [0,1,1,2,3,5] [1,1,2,3,5]
[1,2,3,5,8]
*Fib> zipWith (+) [0,1,1,2,3,5,8] [1,1,2,3,5,8]
[1,2,3,5,8,13]
*Fib> zipWith (+) [0,1,1,2,3,5,8,13] [1,1,2,3,5,8,13]
[1,2,3,5,8,13,21]
*Fib> zipWith (+) [0,1,1,2,3,5,8,13,21] [1,1,2,3,5,8,13,21]
[1,2,3,5,8,13,21,34]

分かったような分からないような。
リストを返却するような関数で、遅延評価がどのように行われているのかというのがまだちゃんと飲み込めていないので、もうちょっとじっくり考える必要がありそうです。

実用的なプログラムを書けるようにするのはまだまだ先の話になりそうですが、ちょっとづつでも、関数型言語に慣れていこうと思います。