![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible <voi### [at] dev null> wrote:
> In Haskell, "unions" are a fundamental part of the language. One of the
> fundamental branching primitives is based on them. Nullable fields use
> unions, lists are unions, trees are unions, just about everything ends
> up being a union. [Insert witty Thatcher jokes here.]
I'm not exactly sure if your concept of "union" is the same as C's
concept of "union". A union in C has a fixed size. It's not a dynamic
data container, like a list or a tree.
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp wrote:
> It's not a dynamic data container, like a list or a tree.
Remember that in Haskell these are defined recursively. So a "tree" in this
case is union { struct { tree*left, tree*right }, struct { node data } }
A list is
union { struct {node data, list* next} , struct {node data} }
I.e., what he's calling "tree" would be "node of a tree" in C.
--
Darren New, San Diego CA, USA (PST)
Serving Suggestion:
"Don't serve this any more. It's awful."
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 27/10/2010 07:27 PM, Darren New wrote:
> I.e., what he's calling "tree" would be "node of a tree" in C.
Yeah, I should have been clearer about that. A list *node* is a union. A
tree *node* is a union.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Orchid XP v8 <voi### [at] dev null> wrote:
> On 27/10/2010 07:27 PM, Darren New wrote:
> > I.e., what he's calling "tree" would be "node of a tree" in C.
> Yeah, I should have been clearer about that. A list *node* is a union. A
> tree *node* is a union.
What would the harm be if eg. list nodes were structs instead?
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>>> I.e., what he's calling "tree" would be "node of a tree" in C.
>
>> Yeah, I should have been clearer about that. A list *node* is a union. A
>> tree *node* is a union.
>
> What would the harm be if eg. list nodes were structs instead?
Nothing. It's just that in Haskell, you can't implement it that way.
[Correction: You can't implement *finite* lists that way.] And, with
unions being a fundamental part of the language, you don't need to.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp wrote:
> What would the harm be if eg. list nodes were structs instead?
Since "null" is a union in Haskell to (i.e., it either has data in it or it
has no data in it), this wouldn't really save you anything.
--
Darren New, San Diego CA, USA (PST)
Serving Suggestion:
"Don't serve this any more. It's awful."
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Darren New <dne### [at] san rr com> wrote:
> Warp wrote:
> > What would the harm be if eg. list nodes were structs instead?
> Since "null" is a union in Haskell to (i.e., it either has data in it or it
> has no data in it), this wouldn't really save you anything.
It saves checking the node type for each single operation you do to any
node in the list. It the node is a struct, its contents are fixed and thus
you don't have to check anything.
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp wrote:
> It saves checking the node type for each single operation you do to any
> node in the list. It the node is a struct, its contents are fixed and thus
> you don't have to check anything.
If the node is a struct, you still have to check if it's the end of the list
or a leaf of the tree. You still have to do the equivalent of the text in
if (node->next != NULL) ...
In any case, this checking process is built into the syntax of the language.
That (and more) is what is meant by "pattern matching" constructs. So
checking the tag on the union (so to speak) is done in a type-safe way with
pretty much the same amount of work as checking for a NULL pointer.
--
Darren New, San Diego CA, USA (PST)
Serving Suggestion:
"Don't serve this any more. It's awful."
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>>> What would the harm be if eg. list nodes were structs instead?
>
>> Since "null" is a union in Haskell to (i.e., it either has data in it or it
>> has no data in it), this wouldn't really save you anything.
>
> It saves checking the node type for each single operation you do to any
> node in the list. It the node is a struct, its contents are fixed and thus
> you don't have to check anything.
On the other hand, in a language where unions appear all over the place,
the implementors go to great lengths to make it really efficient.
Besides, normally just about any code that does stuff to a linked list
ends up doing something like
while (list != null)
do stuff;
list = next node;
So there's a check in there anyway. All we're doing by using a union is
making it a different check.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> Yeah, I should have been clearer about that. A list *node* is a union. A
>> tree *node* is a union.
>
> What would the harm be if eg. list nodes were structs instead?
Perhaps I should elaborate further:
I'm not attempting to argue that unions are such a fundamental feature
that every programming language should have them. I'm just pointing out
that *in Haskell* they are extremely fundamental. Which, clearly, is a
different statement.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |