haskell - Haskell のツリーで zip 関数を定義する方法

Question

data Tree a = Leaf a | Node (Tree a ) (Tree a)

Haskellで関数zipと関数のツリー バージョンを作成する方法がわかりません。zipWith

Answer 1

あなたのツリーは、きれいに形成された空のツリーを許可しません - 危険なツリーを作成することはできますがNode undefined undefined、これはあまり良くありません。他の人がコメントしているように、素朴なtreeZipは、「良い」結果を得るために両方のツリーが同じ形状である必要があります。

zipTree :: Tree a -> Tree b -> Tree (a,b)
zipTree (Leaf a)     (Leaf b)     = Leaf (a,b)
ZipTree (Node l1 r1) (Node l2 r2) = 
    let l = zipTree l1 l2
        r = zipTree r1 r2 
    in Node l r 

-- Problems...
zipTree (Node _ _)  (Leaf _)   = Node undefined undefined
ZipTree (Leaf _)    (Node _ _) = Node undefined undefined

単純なツリーの圧縮は、「長さ」だけでなく形状で切り捨てられることに注意してください (形状が一致しない場合は切り捨てられます)。これは、「長さ」で切り捨てられるリストよりも深刻です (厳密に言えば、リストは「形状」で切り捨てられますが、 shape" は常に同じでなければなりません)。

このため、私が Tree ライブラリを作成する場合、zipTree を定義しません。