4

私は次のTree定義に慣れていました：

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

私がどこかでこれに遭遇するまで：

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

Haskellのイディオムについて疑問に思います。

Leaf aだけなのでNode a Empty Empty、このコンストラクターは存在する必要がありますか？Empty次のような独自のコンストラクタを使用して、削除することもできます。

Tree (Maybe (a, (Tree a), (Tree a)))

またはそのようなもの。

私が書いた2番目の定義は「最も拡張された」定義であり、最初の定義はそれと最後の定義の中間です。実用的かつ理論的に最良のものは何ですか？言い換えれば、パフォーマンスとデータ型の設計はどうですか？

4

2 に答える 2

7

慣用的なHaskellが必要な場合は、最初の定義を使用します。これにより、パターンマッチングするコンストラクターが少なくなります。

リーフがたくさんある巨大な二分木がある場合、リーフごとに約16バイト（追加のポインター）のメモリーを節約したい場合は、2番目の定義を使用します（Tree a使用しているプラ​​ットフォーム/コンパイラーのメモリー量によって大きく異なります）保存）。

あなたが提示する3番目の選択肢は、技術的には有効な表現です（あなたが意図したと仮定しますがTree (Maybe (a, Tree a, Tree a))、作業するのは非常に面倒です。

于 2012-07-31T20:29:18.433 に答える
6

dflemstrの答えは的確ですが、2つのコメントを追加したいと思いました（元の答えにコメントで対応することはできません）。

まず、2番目の定義でメモリを節約できるのと同じロジックで、これについても同様の議論を行うことができます。

data Tree a = Empty 
            | Leaf a 
            | LeftOnly a (Tree a) 
            | RightOnly a (Tree a) 
            | Branch a (Tree a) (Tree a)

これが実際に重要かどうかは、アプリケーションによって異なります。

2番目の、そしてより重要な注意点は、データコンストラクターを直接使用しないようにすると、これらの実装の選択肢から抽象化できるということです。たとえば、foldTreeこれらのタイプのいずれに対しても同等の関数を記述できます。短いタイプの場合は、次のようにします。

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

foldTree :: (a -> b -> b -> b) -> b -> Tree a -> b
foldTree f z Empty = z
foldTree f z (Node v l r) = f v (subfold l) (subfold r)
    where subfold = foldTree f z

そして長いものについては、次のように書くことができます：

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

foldTree :: (a -> b -> b -> b) -> b -> Tree a -> b
foldTree f z Empty = z
foldTree f z (Leaf v) = f v z z
foldTree f z (Node v l r) = f v (subfold l) (subfold r)
    where subfold = foldTree f z

同じことは、あなたのMaybeベースの代替案または私の5コンストラクターの代替案に対しても行うことができます。また、この手法は、必要なツリー上の他の一般的な関数に適用できます。（実際、これらの関数の多くは、の観点から記述できるfoldTreeため、そのほとんどは上記の定義から外れています。）

于 2012-07-31T21:54:26.960 に答える