Haskell型のコンストラクタでパラメータの型を定義する方法は？

Question

は、最初のツリーの標準建設を想像してみて：

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

は、私はそれらをカウントすることにより、重複したエントリに対処するこのバージョンを実装したいので、私はこのようなタイプがあります。

data Tree k count = Leaf | Node k count (Tree k count) (Tree k count) 

をしたがって、私のコードは次のとおりです。

tree_insert :: Ord k => k -> Tree k count -> Tree k count 
tree_insert k Leaf = Node k 1 Leaf Leaf 
tree_insert k (Node n count l r) 
    | k == n = Node n (count+1) l r 
    | k < n = Node n count (tree_insert k l) r 
    | k > n = Node n count l (tree_insert k r) 

あなたはしかし、このコードを使用しようとすると、次のエラーが発生します。

それを修正する

Could not deduce (Num count) arising from the literal ‘1’

私はこれに関数の型宣言変更：しかし、私はさらに問題に走ったラインの下

tree_insert :: (Ord k, Num count) => k -> Tree k count -> Tree k count 

を。私にとっては、Haskellのように、Num countがないと、どのタイプのものなのかわからないので、最初のパターンに1を代入するとエラーになります。 Num countは本当に問題を解決する良い方法のようには思えません。

data Tree k count = Leaf | Node k count (Tree k count) (Tree k count) 
where count is Int 

明らかに上記のコードは良くないが、私は考えているものの種類の例：理想的には、私は最初の型宣言を行うとき、のようなものが何であるかの種類数を定義することができるはずですの。

もし私が望むものがあれば、あるいは理想的にはこの問題に近づく別の方法があるなら、それを聞いて欲しいです。この特定の問題だけでなく、すべてのデータ型と関数の定義に重点が置かれています。

ありがとうございます！

Answer 1

2つの選択肢があります。より直接的なものは、Treeタイプに対してcountをパラメータ化しないだけです。

data Tree k = Leaf | Node k Int (Tree k) (Tree k) 

tree_insert :: Ord k => k -> Tree k -> Tree k 
tree_insert ... 

また、より一般的なツリータイプが必要な場合は、synonynタイプを使用することもできます。

data Tree k count = Leaf | Node k count (Tree k count) (Tree k count) 
type TreeInt k = Tree k Int 

tree_insert :: Ord k => k -> TreeInt k -> TreeInt k 
tree_insert ... 

Answer 2

オリジナルのツリータイプは、各ノードに格納されているデータのタイプですでに完全にパラメトリックです。ちょうどk値の代わりに(k, Int)の値を格納するツリーで作業することができます。

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

tree_insert :: a -> Tree (a, Int) -> Tree (a, Int) 
tree_insert k Leaf = Node (k, 1) Leaf Leaf 
tree_insert k (Node (n, count) l r) 
    | k == n = Node (n, count+1) l r 
    | k < n = Node (n, count) (tree_insert k l) r 
    | k > n = Node (n, count) l (tree_insert k r)