LazyなFibonacci

勉強会 Haskell C#

10/11に第4回北海道関数型言語勉強会が開かれました。
ちなみに前日の10/10で21歳になりました！目尻のシワが気になる年頃。


さて、勉強会の終盤。
ずっとSmalltalkをやってきたのにお墓にはHaskellのプログラムを刻むことになったsumimさんが、お墓に刻むプログラムを紹介してくれました。

fib = 1 : 1 : zipWith (+) fib (tail fib)
main = print $ take 15 fib
-- print (fib !! 3) で4番目の数だけ取れる

会場にいた時何となく分かった気になっていたけど実際分かってなくて（汗）、帰宅後復習して理解しました。（後述）


ちなみにzipとzipWithを再定義してみると

zip' :: [a] -> [b] -> [(a,b)]
zip' (x:xs) (y:ys) = (x,y) : zip' xs ys
zip' _ _ = []

testZip = zip' [1..3] [6..10]

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys
zipWith' _ _ _ = []

testZipWith = zipWith' (**) (replicate 11 2) [0..10]

main = print testZipWith

理解の過程

fibを理解するために書いたメモを載せとこう。
暗号チックだったので少し補足を入れた。

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


最初の状態で先頭２つは求まっている。
あとは知らん。
f = 1, 1, ?


そして zipWith (+) [1:1:?] [1:?]
まず両方のリストの先頭要素を取って来て(+)する
[1:1:?]の先頭と、tail fib(==[1:?])の先頭
(fib!!0) + ((tail fib)!!0)　←(fib!!1)
= 2
これをとりあえず連結する
1:1:2


この時点でのfibは、
f = 1, 1, 2, ?


次↓
(fib!!1) + (fib!!2)
= 3
1:1:2:3


f = 1, 1, 2, 3, ?


次↓
(fib!!2) + (fib!!3)
=5
1:1:2:3:5


ずっと続く

C#で

ここまでは良かったんだけどここからが苦労した。何度か無限にメモリを奪われた...（´人｀）
mrkn先生に、「k泉君・・・C#で！」と振られたので頑張ってみました。
なるべく似せて書いたつもり。memoizeなしだったらもうちょっとスマートに書けるんだけどなぁ。。。もっと良い回答がありましたらご指南ください。

public class Fibonacci
{
	public IEnumerable<int> Fib()
	{
		yield return 1;
		yield return 1;

		var memo = new Dictionary<int, int>();
		memo[ 0 ] = memo[ 1 ] = 1;
		var fib = this.Fib2( memo );
		var fibTail = fib.Skip( 1 );

		for ( int memoIndex = 2, i = 0 ; true ; memoIndex++, i++ )
		{
			yield return
				memo[ memoIndex ] = fib.ElementAt( i ) + fibTail.ElementAt( i );
		}
	}
	private IEnumerable<int> Fib2( Dictionary<int, int> memo )
	{
		for ( int key = 0 ; true ; key ++ )
			yield return memo[ key ];
	}
	

	public void Test1()
	{
		var f = this.Fib().Take( 40 );
		f.ToList().ForEach( x => Console.Write( "{0}.", x ) );

		//Console.WriteLine( "\n===\n{0}", f.ElementAt( 40 ) );
		Console.WriteLine( "\n===\n{0}", f.Take( 40 ).Last() );
	}
}


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.

5702887.9227465.14930352.24157817.39088169.63245986.102334155.

===

102334155

  • TakeはHaskellで言う take
  • Skip(1)で先頭以降（==tail）
  • ElementAt(x)で fib!!x
  • 無限再帰に陥るのでFib2が存在する
    • yieldは匿名メソッドやラムダ式の中では使えないため別の関数に
  • Int32使ってるので正確には無限じゃない...


また、Test1メソッドの中で出力を1行コメントアウトしてますが、これやると例外が。
順に求めていかないと値を取り出せないのです。
Haskellの方の「fib !! 40」も必要になった際に先頭から求めてると思われますが、C#の場合はElementAt拡張メソッドを呼んだぐらいじゃ勝手に反応してくれません。ということでその次の行のような取り出し方になる。


無限リストに対して拡張メソッドのTakeとかSkip呼び出したら、その時点で止まらなくなるのかなと思ってましたが、そんなことはないんですね。この点は言語側で遅延？しているんですね。おじちゃん安心しました。


他の言語で書いたらどうなるのかな。C++とか！
PythonかLispで書いてみようかと思ったけどやめた（というかTODOが...）。

もう一つのfib

リスト内包のこんなのも見つけた

循環性を使用した別の例をみてみましょう。フィボナッチ数列はつぎのような循環数列をつかって効率よく計算することができます。

fib = 1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ]

A Gentle Introduction to Haskell: Functions

tail2

//フィボナッチとは関係ないです
ふつけるの110ページのやつ。

main = do cs <- getContents
          putStr $ lastNLines 10 cs

lastNLines :: Int -> String -> String
lastNLines n cs = unlines $ takeLast n $ lines cs

takeLast :: Int -> [String] -> [String]
takeLast n xs = diffList xs (drop n xs)

diffList :: [String] -> [String] -> [String]
diffList xs []         = xs
diffList [] ys         = ys
diffList (_:xs) (_:ys) = diffList xs ys
http://i.loveruby.net/ja/stdhaskell/samples/tail2.hs.html