Haskell-BinaryTreeのフォルダに基づいてmapTree関数を作成する方法は？
これは、第11章「第一原理からのHaskellプログラミング」の代数的データ型からの質問です。
data BinaryTree a =
Leaf
| Node (BinaryTree a) a (BinaryTree a)
deriving (Eq, Ord, Show)
実際に既存のツリーに値を挿入することはありません。データ構造に値を挿入するたびに、まったく新しいツリーを構築します。
insert' :: Ord a => a -> BinaryTree a -> BinaryTree a
insert' b Leaf = Node Leaf b Leaf
insert' b (Node left a right)
| b == a = Node left a right
| b < a = Node (insert' b left) a right
| b > a = Node left a (insert' b right)
これは、BinaryTreeのデータ構造のマップ関数です。
mapTree :: (a -> b) -> BinaryTree a -> BinaryTree b
mapTree _ Leaf = Leaf
mapTree f (Node left a right) =
Node (mapTree f left) (f a) (mapTree f right)
BinaryTreeのフォルダーを作成します
私たちが提供したBinaryTreeの定義を前提として、バイナリツリーのカタモルフィズムを記述します。
-- any traversal order is fine
foldTree :: (a -> b -> b)
-> b
-> BinaryTree a
-> b
上記のタイプは、折りたたみ関数を適用する前にツリーをリストに変換しない場合のヒントです。
BinaryTreeのマップを書き換えます
作成したfoldTreeを使用して、foldTreeを使用してmapTreeを書き直します。Ord制約がないのは意図的なものであり、挿入関数を使用する必要はありません。
mapTree' :: (a -> b)
-> BinaryTree a
-> BinaryTree b
mapTree' f bt =
foldTree undefined undefined undefined
私は、次の人から多くの助けを借りて、フォルダに関する最初の質問に役立つ答えを得ることができました。 https://github.com/johnchandlerburnham/hpfp/blob/master/11/BinaryTree.hs
私の答え：
foldTree f b Leaf = b
foldTree f b (Node left a right)
= (foldTree f tempb left) where
tempb = (f a) tempright
tempright = foldTree f b right
しかし、BinaryTree用の新しいmapTreeの作成に関する2番目の質問では、その答えが見つかりませんでした。元のmapTreeは上に提供されています。johnchandlerburnhamリンクの回答でさえ、異なるフォールドツリーを使用しています。
最初の質問に対する私の回答に基づいて、誰かが2番目の質問に対する実行可能な回答を得るのを手伝ってもらえますか？または、最初の質問に対する別の回答が必要ですか？
テスト用のツリーは次のようになります。
testTree :: BinaryTree Integer
testTree =
Node (Node Leaf 3 Leaf) 1 (Node Leaf 4 Leaf)
回答
その署名でmapTreeを使用しfoldTreeて書くことはできません。（@chiが指摘しているように、技術的な問題は、foldTree署名が間違っているために真のカタモルフィズムになることですBinaryTree。）実際、リンクされたHaskellファイルをロードするとBinaryTree.hs、mapTree'正しく機能しないことがわかります。
λ> :l BinaryTree
λ> mapTree (+1) testTree
Node (Node Leaf 2 Leaf) 3 (Node Leaf 4 Leaf)
λ> mapTree' (+1) testTree
Node (Node (Node Leaf 3 Leaf) 2 Leaf) 4 Leaf
正しいノード値が得られますが、ツリーの構造が間違っています。
私はその本のコピーを持っていないので、あなたが見ているものを正確に見ることはできませんが、おそらくこれらのメモが役立つでしょう。セクション11.15の終わりに、著者はの2パラメーターバージョンと3パラメーターバージョンについて説明しfoldTree、3パラメーターバージョンmapTree'を使用するように記述されている場合にのみ正しく機能することを示しています。