1

私は典型的な二分探索木のデータ型を持っています:

data Tree a
  = Empty
  | Branch a (Tree a) (Tree a) deriving Show

そしてカタモルフィズム

foldt :: b -> (a -> b -> b -> b) -> Tree a -> b
foldt empty _ Empty = empty
foldt empty branch (Branch a l r) = branch a (foldt empty branch l) (foldt empty branch r)

を使用して挿入関数を定義しようとしましたfoldtが、興味深い結果が得られました。

insert :: (Ord a) => a -> Tree a -> Tree a
insert x = foldt (single x) insertb
  where insertb a left right
          | x == a = Branch x left right
          | x < a = Branch a (insert x left) right
          | x > a = Branch a left (insert x right)

ghci> mytree = insert 2 (Branch 3 Empty Empty)  
ghci> mytree
Branch 3 (Branch 2 (Branch 2 Empty Empty) (Branch 2 Empty Empty)) (Branch 2 Empty Empty)
ghci>

もちろん、従来の挿入メソッドは期待どおりに動作します。

insert' :: (Ord a) => a -> Tree a -> Tree a
insert' x Empty = single x
insert' x (Branch a left right)
  | x == a = Branch x left right
  | x < a = Branch a (insert' x left) right
  | x > a = Branch a left (insert' x right)

ghci> mytree2 = insert' 2 (Branch 3 Empty Empty)
ghci> mytree2
Branch 3 (Branch 2 Empty Empty) Empty
ghci>

insertの観点から定義する方法はありますfoldtか、またはここで間違ったツリー ( ha ) を吠えていますか?

4

2 に答える 2

3

パラモーフィズムに関するヒントを提供してくれた dfeuer と amalloy に感謝します、TIL!

Tree データ型のパラモーフィズムを考えると、次のようになります。

parat :: b -> (a -> (Tree a, b) -> (Tree a, b) -> b) -> Tree a -> b
parat empty _ Empty = empty
parat empty branch (Branch a l r) =
  branch a
         (l, parat leaf branch l)
         (r, parat leaf branch r)

挿入関数は次のように記述できます。

insert :: Ord a => a -> Tree a -> Tree a
insert x = parat (single x) branch
  where branch a (l, l') (r, r')
          | x == a = Branch x l r
          | x < a = Branch a l' r
          | x > a = Branch a l r'

ghci> mytree = insert 2 (Branch 3 Empty Empty)
ghci> mytree
Branch 3 (Branch 2 Empty Empty) Empty
ghci>

より大きなツリーのテスト...

import Data.Function

mytree :: Tree Integer
mytree = (Branch 3 Empty Empty) & insert 2 & insert 4 & insert 6 & insert 5 & insert 10

inorder :: Tree a -> [a]
inorder = foldt [] (\a l r -> l ++ [a] ++ r)

ghci> mytree
Branch 3 (Branch 2 Empty Empty) (Branch 4 Empty (Branch 6 (Branch 5 Empty Empty) (Branch 10 Empty Empty)))
ghci> inorder mytree
[2,3,4,5,6,10]
ghci>
于 2021-04-16T01:28:29.237 に答える