１．数列
リストは多様に解釈できる。前の記事の「リスト内包表記を利用して鶴亀算を解く」では、リストを集合と見なした。今回は、リストを数字の並びとみなすこととする。
数字の並びは、通常、数列と呼ばれる。高校で、等差数列、等比数列を学んだ事と思う。Haskellでは、等差数列は初項と二番目の項を示すことで簡単に表現できる。例えば、奇数は、1で始まり、隣り合う項の差が2である数列である。二番目の項は３なので、次のように記述できる。
[1,3..]
奇数の数列の各項を足し合わせた数列は、
1 3 5 7 ... +1 3 5 7 ... ------------ 2 6 10 14 ...
即ち、
[2,6..]
だが、Haskellには、数列同士の各項を足し合わせて新たな数列を求める場合には、便利な関数がある。zipWithと呼ばれる関数だが、丁度、ジッパーのように、線上に並んだ二つのものを一つの線に噛み合せる機能を有している。
Zipwithは三つの引数を取る。最初の引数は関数(演算)でどのように噛み合せるかを指定する。残りの二つの引数は数列である。先ほどの奇数の数列を足し合わせる場合には、噛み合せの方法は足し算(+)なので、次のようにする。
zipWith (+) [1,3..] [1,3..]
となる。これは無限数列なので、最初の10個だけを見たいときは次のようにする。
take 10 $ zipWith (+) [1,3..] [1,3..]
上のプログラムはtake 10 (zipWith (+) [1,3..] [1,3..])と同じである。takeの二番目の引数が関数zipWithになっている。takeを実行するためには、二番目の関数zipWithを実行してからとなるため、カッコでくくる必要がある。しかし、カッコはプログラムを読みにくくするので、$を用いる。これは、$以下を先に評価することを意味する。
２．リストの表現法
これまで、リストは、初項と終項、例えば、[1..10]、あるいは、初項と第二項、例えば、[1,3..]、あるいは、初項と第二項と終項、例えば、[1,3..11]、で作成できると説明したが、別の方法として、その要素が有限である場合には、カッコの中にすべてを列挙してもかまわない。例えば、(意味のない並びだが)[1,3,6,9]である。
また、リストに対する操作に、最初の要素を取り出すheadと、最初の要素を取り除いたリストを取り出す操作tailがある。headとtailの部分を明示的に表現してリストを表すこともできる。即ち、最初の要素xと残りのリストxsを用いてリストをx:xsと表すことも可能である。
さらに、拡張して、最初の要素x1からn番目までの要素xnまでと、残りのリストxsを用いてx1:x2:,,:xn:xsのように表すこともできる。例えば、先の意味のない並びは1:3:6:9:[]と表すことができる。リストはこの様にいろいろな形式で表わすことができるので、後の記事で紹介するパターン照合が威力を発揮する。
３．再帰的表現
奇数の数列は次のようになっていた。
1 3 5 7 9 ...
奇数の数列から一つずらした奇数の数列で項毎に引き算を行うと次のようになる。
1 3 5 7 9 ...
- 1 3 5 7 ...
-------------------
2 2 2 2 ...上記の式から、奇数の数列は、headが１で、tailが奇数の数列の各項に2を加えた数列であることが分かる
そこで、奇数の数列をoddとすれば、奇数の数列は
odd = 1:zipWith (+) odd [2,2..]
となる。oddを求めるのに、oddを用いているので、この関数は再帰的である。一般に、等差数列は、関数oddで、1のところを初項の値に、2のところを公差にすることで、再帰的な関数としてあらわすことができる。
それでは、等比数列はどうであろうか、等比数列は、隣り合う項の比(公比）がrであるものをいう。初項（0項）を\(a\)とすれば、n番目の項は、\(ar^n\)となる。
等比数列の例を挙げる。以下は３乗の数列を示したものである。
1 3 9 27 81 ...
３乗の数列から一つずらした３乗の数列で項毎に割ると次のようになる。
1 3 9 27 81 ...
÷ 1 3 9 27 ...
-------------------
3 3 3 3 ...引き算が割り算に代わっただけで、等差数列と同じようなことが成り立っている。即ち、３乗の数列は、headが１で、tailが３乗の数列の各項に3を掛けた数列であることが分かる。
そこで、３乗の数列をtriとすれば、３乗の数列は
tri = 1:zipWith (*) tri [3,3..]
となる。一般に、等比数列は、関数triで、1のところを初項の値に、3のところを公比にすることで、再帰的な関数としてあらわすことができる。
４．総和
Haskellでは、関数sumを用いて数列の総和は簡単に求めることができる。例えば、3乗の数列で最初の10項の和を求めたいときは、
sum $ take 10 tri
で求めることができる。
５．実行結果
以下に実行結果を示す。Preludeでは、関数はletを用いて定義する。
５．発展させると
フィボナッチ数列は\(f_n=f_{n-1} + f_{n-2}\)、但し、\(f_0=1, f_1=\)である。即ち、{1,1,2,3,5,8,13..}である。これは次のように表すことができる。
1 1 2 3 ... +0 1 1 2 ... ------------ 1 2 3 5 ...
そこで、再帰的に表現すると次のようになる。
fib = 1:zipWith (+) fib (0:fib)
別の記事でも、数列を扱った。例えば、「数を整然と並べる」と「ライプニッツの公式から円周率を求める」を参考にして欲しい。
