Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

フィボナッチ数個の要素からなる木を表す非正則な代数的データ型

More than 5 years have passed since last update.

非正則データ型 (non-regular data type) というのは、再帰的な代数的データ型のうち、定義において自身を呼び出すときの引数が左辺と異なるものです。下の例では、左辺では F a b ですが右辺では引数が変わり F b (a,b) となっています。

非正則データ型は単純ですが奥が深いです。昔から知られているものだと完全二分木やドブラウン (de Bruijn) インデックスのラムダ項、最近だとフリーアプリカティヴFunListBazaar などが有名です。ちなみに完全二分木は『関数プログラミングの楽しみ』第10章でバタフライ回路の記述のために、アローと組み合わせて活用されています。

いろいろ別のことを考えていたらそういえば完全二分木だけでなくてフィボナッチ数個の要素からなる木も作れるな、と思って書いてみました。実用例は思いつきませんが、複数引数の非正則データ型の例として参考になるかもしれません。

-- fibonacci-number-element tree
newtype Fib a = Fib {unFib :: F a a}
data F a b = DoneF b | MoreF (F b (a, b))

-- binary tree
data Bin a = Leaf a | Node (Bin a) (Bin a)
instance Functor Bin where
    fmap f (Leaf a) = Leaf (f a)
    fmap f (Node l r) = Node (fmap f l) (fmap f r)
join :: Bin (Bin a) -> Bin a
join (Leaf b) = b
join (Node l r) = Node (join l) (join r)

-- fmap for fibonacci-number-element tree
instance Functor Fib where
    fmap f (Fib x) = Fib (bimap f f x)
bimap :: (a -> a') -> (b -> b') -> F a b -> F a' b'
bimap g h (DoneF b) = DoneF (h b)
bimap g h (MoreF x) = MoreF (bimap h (\(a,b) -> (g a, h b)) x)

-- fibonacci-number-element tree to binary tree
treeifyFib :: Fib a -> Bin a
treeifyFib = fmap (\e -> case e of Left a -> a; Right a -> a) . treeifyF . unFib
treeifyF :: F a b -> Bin (Either a b)
treeifyF (DoneF b) = Leaf (Right b)
treeifyF (MoreF f) = join $ fmap (\e -> case e of
    Left b -> Leaf (Right b); Right (a,b) -> Node (Leaf (Left a))
    (Leaf (Right b))) (treeifyF f)

ghci で型を確かめてみると、要素の数が確かにフィボナッチ数個になっています。

> :t Fib . MoreF . MoreF . MoreF . MoreF . MoreF . DoneF
Fib . MoreF . MoreF . MoreF . MoreF . MoreF . DoneF
  :: (((a, a), (a, (a, a))), ((a, (a, a)), ((a, a), (a, (a, a)))))
     -> Fib a
shiatsumat
音楽 https://goo.gl/abY3NE : 開発 http://github.com/shiatsumat : 雑記 http://shiatsumat.hatenablog.com
http://shiatsumat.hatenablog.com
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away