Re: Heap types
Bart Massey
type Heap e = Tree (Int, e)
Here the tupling is not gratuitous---we want to reuse our
Tree type.
I'm always a little confused by how generic to make these
things. Shouldn't I say this instead?
type Heap e = Integral a => Tree (a, e)
This seems to require RankNTypes, however, so probably not.
Uggh. Maybe I should just default to using Integer instead
of Int in these cases?
Unfortunately, using a tuple makes ordering a tricky business,
which matters for heaps. You probably prefer something like
data HeapNode e = HeapNode { count :: Int, value :: e }
instance Eq e => Eq (HeapNode e) where
e1 == e2 = value e1 == value e2
instance Ord e => Ord (HeapNode e) where
e1 `compare` e2 = value e1 `compare` value e2
type Heap e = Tree (HeapNode e)
Uggh. (And no, don't ask me why Ord isn't an instance of Eq
automatically. You'd think, wouldn't you?)
Heap is arguably a lousy name for this data structure; one
can imagine many other things than heaps that want trees
whose label contains some kind of count. Maybe CountedTree?
Bart
Tom
> One could make an argument that the right typing is
>
> type Heap e = Tree (Int, e)
>
> Here the tupling is not gratuitous---we want to reuse our
> Tree type.
what you're saying here. IIUC you're teasing apart Okasaki's
] data Heap e = E | T Int e (Heap e) (Heap e)
into
] data Tree e = E | T e (Tree e) (Tree e)
and
] type Heap e = Tree (Int, e)
I like this because it isolates the part needed for the basic correct
behavior, the Tree, from the auxiliary information needed to make it
blindingly fast, the Int part which caches the depth of the right
spine.
> I'm always a little confused by how generic to make these
> things. Shouldn't I say this instead?
>
> type Heap e = Integral a => Tree (a, e)
depth. In this case it's definitely Int, in fact, it should even be
Nat, if there were such a thing. In a different data structure you
might cache something else, maybe a pointer to the leftmost
descendent, if that's what you need for speed.
> [snip]
> Uggh. (And no, don't ask me why Ord isn't an instance of Eq
> automatically. You'd think, wouldn't you?)
your elements need to be in Ord, but not necessarily in Eq (while for
sets you need Eq, but not necessarily Ord). The two are independent.
> Heap is arguably a lousy name for this data structure; one
> can imagine many other things than heaps that want trees
> whose label contains some kind of count. Maybe CountedTree?
standard trick in algorithm design, to cache values you anticipate
using frequently.
Barton C Massey
> No! The sole purpose of the Int is avoid repeatedly recomputing
> depth. In this case it's definitely Int, in fact, it should even be
> Nat, if there were such a thing. In a different data structure you
> might cache something else, maybe a pointer to the leftmost
> descendent, if that's what you need for speed.
Yeah, I was thinking it was node count, not depth. In
general, though, the question is what to do when you have
some count that could potentially be larger than would fit
in an Int, but normally wouldn't be. The "solution" in
Data.List makes me wonder what should really happen.
> > Uggh. (And no, don't ask me why Ord isn't an instance of Eq
> > automatically. You'd think, wouldn't you?)
>
> Okasaki makes a good point for this. For a priority queue interface
> your elements need to be in Ord, but not necessarily in Eq (while for
> sets you need Eq, but not necessarily Ord). The two are independent.
In general, one can have partial orders with equality
undefined. Given that the Haskell type Ord has EQ as a
constructor, though, anything in Ord is necessarily testable
for equality, I think?
I guess I want Equality, PartialOrder and TotalOrder
typeclasses, with the obvious relationships?
Bart