Ch 3 Heap constructors

[philvarner]

In Ch 3, I'm curious about the declaration of the heap datatype. For
the Tree, the declaration was:

data Tree e = E | T (Tree e) e (Tree e)

Coming from a OO background, this seems really elegant since the
physical layout of the T value constructor mimics its logical
structure.

However, for the Heap, the type is given as:

data Heap e = E | T Int e (Heap e) (Heap e)

I can't think of a good reason why you wouldn't want a similar
structure as Tree, like

data Heap e = E | T Int (Heap e) e (Heap e)

or

data Heap e = E | T (Heap e) (Int, e) (Heap e)

Ideas?

[Julian Blake Kongslie]

On Tue, 2009-09-15 at 11:07 -0700, philvarner wrote:
> In Ch 3, I'm curious about the declaration of the heap datatype. For
> the Tree, the declaration was:
>
> data Tree e = E | T (Tree e) e (Tree e)
>
> Coming from a OO background, this seems really elegant since the
> physical layout of the T value constructor mimics its logical
> structure.
>
> However, for the Heap, the type is given as:
>
> data Heap e = E | T Int e (Heap e) (Heap e)
>
> I can't think of a good reason why you wouldn't want a similar
> structure as Tree, like
>
> data Heap e = E | T Int (Heap e) e (Heap e)

The ordering of arguments to the constructor is largely left to the
whims of the programmer; sometimes an order is chosen because it
facilitates a useful instance of currying, but more frequently it is
simply whichever arbitrary order the programmer happened to type in.

> or
>
> data Heap e = E | T (Heap e) (Int, e) (Heap e)

Tuple forms tend to be discouraged in constructors. They add extra
punctuation to pattern matches without really adding anything useful.

> Ideas?

--
-Julian Blake Kongslie
If this is a mailing list, please CC me on replies.

vim: set ft=text :

[Tom]

I second what Jules says, but I'll presume to speculate on what whim
Okasaki had when he wrote these.

On Tue, Sep 15, 2009 at 11:07:58AM -0700, philvarner wrote:
] [snip]
]
] data Tree e = E | T (Tree e) e (Tree e)

]
] Coming from a OO background, this seems really elegant since the
] physical layout of the T value constructor mimics its logical
] structure.

It does mimic the structure you'd use to draw a tree, with the data
between the left and right subtrees. It's not elegant, it's nothing
out of the normal.

] However, for the Heap, the type is given as:

]
] data Heap e = E | T Int e (Heap e) (Heap e)

]
] [snip]

Since an invariant of the heap is that the element at the root is less
than all elements in the subheaps, perhaps he's positioned that least
element first.

... Or then again, maybe it's random.