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

>>>    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

>> 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

Orchid XP v8 <voi### [at] devnull> wrote:
> 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.

  Ostensibly there could be other types of nodes in the list besides regular
nodes and end nodes. These could, for example, contain different types of
data. Any operation you do on the data would have to first check that the
node is of the correct type (if the node is a union).

-- 
                                                          - Warp

Post a reply to this message

On 28/10/2010 08:36 PM, Warp wrote:
> Orchid XP v8<voi### [at] devnull>  wrote:
>> 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.
>
>    Ostensibly there could be other types of nodes in the list besides regular
> nodes and end nodes. These could, for example, contain different types of
> data. Any operation you do on the data would have to first check that the
> node is of the correct type (if the node is a union).

Sure. But the compiler statically knows what all the possibilities are, 
and it can decide on some suitable arrangement for doing this efficiently.

Instead of writing the above, in Haskell you end up doing something like

   do_stuff list =
     case list of
       Node data next -> ... [recursively call do_stuff next] ...
       End            -> ...[do something else]...

If there are more possibilities than just "Node" or "End", you just list 
them as extra possibilities. Either way, the compiler is going to build 
a multi-way jump. (I believe GHC handles this using indirect code 
pointers rather than actual integer comparisons against an ID tag.)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Warp wrote:
> These could, for example, contain different types of data. 
 > Any operation you do on the data would have to first check that the
> node is of the correct type (if the node is a union).

But you still need to do this, even if it's a struct, unless by "struct" you 
mean all the data in every element is always valid, in which case you 
wouldn't use a union in Haskell either.

Either you're operating on invalid data, or you're checking if the data is 
valid before operating on it. Yes?

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message

On 10/22/2010 12:33 PM, Warp wrote:
> Darren New<dne### [at] sanrrcom>  wrote:
>> http://journal.stuffwithstuff.com/2010/10/21/the-language-i-wish-go-was/
>
>    I'm not so sure I agree with the necessity of 'union'.
>
>    'union' in C is basically a construct which exists to save some bytes
> of memory in some rare circumstances. The price you pay for it is reduced
> type safety: You always have to make sure you are using the object with
> the correct type, or else you'll get garbage. More often than not, unions
> are not used raw, but embedded in structs, where one of the struct members
> tells the type of the union. While in some situations you can use this to
> save memory (especially if you need to instantiate this struct millions of
> times), it introduces the overhead of the type member and having to always
> check it. (Without the union there would be no need to write any conditionals
> based on the type.)
>
>    You could have the language always automatically check the proper type
> of the union, but then you'll be having overhead on every single operation
> you are doing with that union (overhead which could in many cases be avoided).
> It would be rare for the memory saving advantage to be worth the overhead.

There might be an application in which a set of classes derived from a 
common ancestor need to be forced to have the same size.  Then a member 
which is of a different type in different classes would best be a union. 
  Class member functions (late bound) would know which member of the 
union to access without having to type check.

Really, though, the union is a kludge built into C for the resource-poor 
early days of computing.

Regards,
John

Post a reply to this message

Warp wrote:
>   The most clever use of 'union' I have seen was like this:
> 
> union Matrix4x4
> {
>     double m[4][4];
>     struct
>     {
>         double m11, m12, m13, m14,
>             m21, m22, m23, m24,
>             m31, m32, m33, m34,
>             m41, m42, m43, m44;
>     };
> };
> 
>   This means you can access the matrix like "transform.m[1][2] = 5;"
> or like "transform.m23 = 5;";
> 
>   Of course in this case this is just a trick to have two naming
> conventions to access the same data (rather than to save memory).

I know someone who got this to work via C++ operator overloading and other 
nasties:

Vector3D a, b;
a.xy = b.zx;

It's equivalent to a.x=b.z; a.y=b.x; Any combination of xyz letters would 
work, probably even a.xxx=b.yzy;

IIRC it even used SSE inline assembly to do the assignments.

Post a reply to this message

Nicolas Alvarez <nic### [at] gmailcom> wrote:
> I know someone who got this to work via C++ operator overloading and other 
> nasties:

> Vector3D a, b;
> a.xy = b.zx;

> It's equivalent to a.x=b.z; a.y=b.x; Any combination of xyz letters would 
> work, probably even a.xxx=b.yzy;

  All to save typing a few extra characters... :P

> IIRC it even used SSE inline assembly to do the assignments.

  And probably hindering any possibility for the compiler to perform
optimizations resulting in even more efficient code...

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>> It's equivalent to a.x=b.z; a.y=b.x; Any combination of xyz letters would 
>> work, probably even a.xxx=b.yzy;
> 
>   All to save typing a few extra characters... :P

AFAIK, this is the sort of syntax that the 3D graphics cards use for 
built-in vector operations. Of course, that's a separate compiler with 
"custom" syntax, so it's probably just as efficient if not moreso.

I'm guessing given the name of the class he was trying to duplicate the 
syntax used in the grpahics card stuff.

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message