I want to make:
data BinTree a b = b | Branch a (BinTree a b) (BinTree a b) deriving Show
But there is an error that b is not a data constructor. How can i fix that because i want my tree to always return b type.
Add a comment
|
2 Answers
How can i fix that because i want my tree to always return b type.
You need to define a data constructor that wraps the b value:
data BinTree a b = Leaf b | Branch a (BinTree a b) (BinTree a b) deriving ShowThen in functions where you obtain leaves, you can use pattern matching to "unwrap" the value out of the Leaf data constructor.
For example you can obtain a list of the values wrapped in the leaves for a BinTree a b with:
leaves :: BinTree a b -> [b]
leaves (Leaf b) = [b]
leaves (Branch _ la lb) = leaves la ++ leaves lb
answered Jan 21, 2020 at 14:20
willeM_ Van Onsem
482k33 gold badges483 silver badges624 bronze badges
2 Comments
Tống Việt Dũng
Oh i haven't thought about that. Thank you
Tống Việt Dũng
can you give me an example how i can "unwrap" the value out?
You need a data constructor for the leaf; the type alone isn't not sufficient.
data BinTree a b = Leaf b | Branch a (BinTree a b) (BinTree a b) Is there a reason you allow leaves and interior nodes to store values of different types? Also, you can't represent an empty tree with this data type. You might want
data BinTree a = Empty | Branch a (BinTree a) (BinTree a)
instead. With this, a leaf is now just a Branch value with both children empty: Branch 3 Empty Empty instead of Leaf 3.
4 Comments
Will Ness
Huffman encoding: frequencies govern branching, chars are the payload.
chepner
Are the frequencies usually stored in the interior nodes, though? You only need them to build the tree, not to do {en,de}-coding with the tree.
chepner
I mean, once you have the tree, you don't need the frequencies. You can keep a separate table of frequencies while building the tree, and discard them when you are done.
Will Ness
your "Is there a reason you allow leaves and interior nodes to store values of different types? " in the answer reads like "you really shouldn't, there's no reason for it". so I provided a counterexample, where such trees are useful. (in the comments that question would read as just asking for a specific clarification, but not in the answer, I don't think). see e.g. the picture here. whether it can be optimized away, is a separate concern.