フィボナッチ

http://d.hatena.ne.jp/smoking186/20071205/

ねえ、きみ。それにしても、こんどの小さな事件でもわかったんだが、世の中のいざこざは、悪意や策謀から起こるというよりは、むしろ誤解や怠慢から起こるのではないだろうか。少なくとも、悪意や策謀なんて場合は、めったにないのだ。(「若きウェルテルの悩み」井上正蔵訳だと思う)

http://d.hatena.ne.jp/ita/20071203/p1

data Tree a = Node {first::a, second::(Tree a), third::(Tree a)}
  deriving (Eq, Show)
newtype Matrix a = Matrix (a,a,a,a)
  deriving (Eq, Show)
a (Matrix (x,_,_,_)) = x
b (Matrix (_,x,_,_)) = x
c (Matrix (_,_,x,_)) = x
d (Matrix (_,_,_,x)) = x

instance Num a => Num (Matrix a) where
    (+) (Matrix (a1,b1,c1,d1)) (Matrix (a2,b2,c2,d2)) = Matrix (a1+a2,b1+b2,c1+c2,d1+d2)
    (*) (Matrix (a1,b1,c1,d1)) (Matrix (a2,b2,c2,d2)) = Matrix (a1*a2+b1*c2, a1*b2+b1*d2, c1*a2+d1*c2, c1*b2+d1*d2)
    negate (Matrix (a1,b1,c1,d1)) = Matrix (-a1,-b1,-c1,-d1)
    signum = error "no signum"
    abs = error "no abs"
    fromInteger i = Matrix (fromInteger i, 0, 0, fromInteger i)

mapT f (Node a b c) = Node (f a) (mapT f b) (mapT f c)
zipWithT f (Node a1 b1 c1) (Node a2 b2 c2) = Node (f a1 a2) (zipWithT f b1 b2) (zipWithT f c1 c2)

seed = Matrix (1,1,1,0)
fibo = Node 1 (mapT (^2) fibo) (mapT ((seed*).(^2)) fibo)
num = Node 0 (mapT (*2) num) (mapT ((1+).(*2)) num)

nn = 1:map (2*) nn
n2b n = snd $ n2bh n 1 where
  n2bh n x = if n < x
    then (n,[])
    else
      if x == 1
        then (error "", (case p of
                             1 -> True
                             0 -> False
                             _ -> error ""):q)
        else (if p >=x then (p-x,True:q) else (p,False:q)) where
          (p,q) = n2bh n (2*x)


fib n = b $ first $ foldr (flip (.)) id m $ fibo
  where m = map (\x->if x then third else second) $ n2b n

main = putStrLn $ show $ fib 1000

なんか色々ごちゃごちゃ考えていたら、妙なことになったので無意味にさらしておく。あまりいいコードではない。

無限二分木を作って、自然数を二進数に展開してからアクセスするとフィボナッチ数がでてくる。