I can't find the thread that was talking about trees in Haskell vs trees in 
an OO language, but...

I realized why I thought trees in an OO language have child nodes with null 
branches - It's OO. You have pointers to things. In Haskell, it's expected 
that when you add a new leaf down at the bottom of the tree, the root node 
changes. In OO, you don't want to have to reassign all variables holding 
pointers to the root when you add a leaf. And that applies recursively as 
well. Even balancing a tree, you tend to rotate the child pointers rather 
than reassign the parent pointer, per se.

So that's at least part of it.

-- 
Darren New, San Diego CA, USA (PST)
   The question in today's corporate environment is not
   so much "what color is your parachute?" as it is
   "what color is your nose?"

Post a reply to this message

"Darren New" <dne### [at] sanrrcom> wrote in message 
news:4b8fdf63$1@news.povray.org...
>I can't find the thread that was talking about trees in Haskell vs trees in 
>an OO language, but...
>
> I realized why I thought trees in an OO language have child nodes with 
> null branches - It's OO. You have pointers to things. In Haskell, it's 
> expected that when you add a new leaf down at the bottom of the tree, the 
> root node changes. In OO, you don't want to have to reassign all variables 
> holding pointers to the root when you add a leaf. And that applies 
> recursively as well. Even balancing a tree, you tend to rotate the child 
> pointers rather than reassign the parent pointer, per se.
>
> So that's at least part of it.

Ah, trees of data...

I'm having a fun time learning to communicate with our new DBA. I look at 
data entirely from an OO point of view; trees of data where a parent object 
owns a collection of child objects (which might or might not be of the same 
type), and I tend to set up my tables so that each class refers to a table. 
Her perspective is different, and I'm learning new things.

The fun just never stops...

--
Jack

Post a reply to this message

Darren New wrote:

> I realized why I thought trees in an OO language have child nodes with 
> null branches - It's OO. You have pointers to things. In Haskell, it's 
> expected that when you add a new leaf down at the bottom of the tree, 
> the root node changes. In OO, you don't want to have to reassign all 
> variables holding pointers to the root when you add a leaf. And that 
> applies recursively as well. Even balancing a tree, you tend to rotate 
> the child pointers rather than reassign the parent pointer, per se.

More succinctly: In OO, trees are usually mutable. In Haskell, trees are 
usually immutable.

> So that's at least part of it.

A bigger part of it is that, while essentially Haskell has pointers, 
null pointers are explicitly prohibited.

Post a reply to this message

Captain Jack wrote:
> Her perspective is different, and I'm learning new things.

Yep. That was how people did it before the relational model was invented. 
(Well, with appropriate understanding that OO was invented after RDBMS.)

Learning to model data in a database well is an important skill for bigger 
systems. Otherwise, you wind up a couple years down the road with data that 
reflects what you wanted to do with the system when you started, and no way 
of getting the information you need now.

Sort of like the difference between procedural and OO programming - the 
procedural code assumes the whole ecosystem the procedure is in, while the 
OO class/data is more modular. The point of relational is to make the data 
unrelated to the actual code that uses it, but rather related to the real 
world stuff it represents. Ideally, for example, you'd have no "unique IDs" 
in your database - the only reason you do is that some real-world items have 
unique properties that you can't digitize.

-- 
Darren New, San Diego CA, USA (PST)
   The question in today's corporate environment is not
   so much "what color is your parachute?" as it is
   "what color is your nose?"

Post a reply to this message

Invisible wrote:
> More succinctly: In OO, trees are usually mutable. In Haskell, trees are 
> usually immutable.

Not that so much as identity is an important aspect of OO, where it isn't in 
functional programming. Two different objects with exactly the same value 
are nevertheless not interchangable.

> A bigger part of it is that, while essentially Haskell has pointers, 
> null pointers are explicitly prohibited.

You could always have Branch hold a couple of Maybe Leaf's.

-- 
Darren New, San Diego CA, USA (PST)
   The question in today's corporate environment is not
   so much "what color is your parachute?" as it is
   "what color is your nose?"

Post a reply to this message

>> More succinctly: In OO, trees are usually mutable. In Haskell, trees 
>> are usually immutable.
> 
> Not that so much as identity is an important aspect of OO, where it 
> isn't in functional programming. Two different objects with exactly the 
> same value are nevertheless not interchangable.

The OO definition of "object": "An object has identity, state and 
behaviour."

Of course, objects have identity *because* they're mutable. For 
immutable objects, identity is irrelevant. (Even in an OO system it's 
unimportant, regardless of whether you can measure it or not.)

Since most Haskell things are immutable, identity isn't much of an issue.

(The other thing, of course, is the whole "behaviour" part. Objects 
aren't passive data structures, but active mini-programs. This makes 
identity kinda important!)

>> A bigger part of it is that, while essentially Haskell has pointers, 
>> null pointers are explicitly prohibited.
> 
> You could always have Branch hold a couple of Maybe Leaf's.

Sure. But it's simpler (and probably more performant) to just define 
multiple node types. ;-)

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

Post a reply to this message

Darren New wrote:
> Ideally, for example, you'd have no "unique
> IDs" in your database - the only reason you do is that some real-world
> items have unique properties that you can't digitize.

Hmm...

Suppose I have "tasks" (CPU-intensive processing tasks, such as rendering a 
certain frame of a certain POV-Ray scene at specified settings). I store 
those tasks in a relational table. Each task has a unique *name*.

I have another table that holds information about input files, such as the 
.pov. And a third table that links the task and file tables together, since 
it's n-to-n (a task may use multiple files, a file may be used by multiple 
tasks).

From a *practical* point of view... Should that link table refer to tasks by 
their names? It's a known unique property, and I can "digitize" it. Or 
should I add a numerical "unique ID" to the task table, and use that from 
the link table, with the purpose of needing less storage for the link table 
and making lookups faster? Heck, would integers *be* faster than strings,
if I use indexes in either case?

Post a reply to this message

Nicolas Alvarez wrote:
> From a *practical* point of view... Should that link table refer to tasks by 
> their names? 

It should refer to the task table by its primary key. Assuming users adding 
tasks are required to pick unique (and hopefully meaningful) names, that 
would be a good primary key. If there's nothing else actually unique about 
the job, then a uniqueID field is about as well as you can do. But you can 
almost always find something unique, like timestamp+submitter.

Now, if you're going to start mucking up your relational model because it's 
too slow, first ask yourself if it's actually too slow. :-) Alternately, add 
a *second* unique key, and put that in both tables, just for efficiency.

> It's a known unique property, and I can "digitize" it.

By "digitize", I meant stuff like each customer is actually unique, but what 
makes that customer unique is not something that's easy to get into the 
database. Every attribute of an actual customer that's easy to put into a 
database is also something that a customer might change some day. Phone 
number? Obviously not. Name? Hope they don't get married. Etc. Tax number? 
Hope they don't change citizenship.  Etc.

-- 
Darren New, San Diego CA, USA (PST)
   The question in today's corporate environment is not
   so much "what color is your parachute?" as it is
   "what color is your nose?"

Post a reply to this message

Darren New wrote:

> The point of relational is to make 
> the data unrelated to the actual code that uses it, but rather related 
> to the real world stuff it represents.

One of the points of a relational database is that several programs can 
use the data, possibly in ways not originally envisaged. If you make the 
data related to the code that uses it... it's kind of hard to use it in 
new, unexpected ways.

Today, lots and lots of people seem to forget this. They think of a 
database as being a system for holding data that only one application 
uses and only that application understands. This isn't what a database 
is supposed to be. It's supposed to facilitate access by multiple programs.

> Ideally, for example, you'd have 
> no "unique IDs" in your database - the only reason you do is that some 
> real-world items have unique properties that you can't digitize.

Or sometimes it's just for performance. An order can be completely 
identified by the customer it's for, the date it was placed, and what 
was ordered. But that's a heck of a lot of information for a key. (In 
fact, that *is* the entire order!) Having an artificial key [to use the 
technical term] is much more convinient - especially if you want to 
refer to the order from outside the database (e.g., over the phone).

Post a reply to this message

One interesting question: If objects are in an array rather than being
individually allocated (and handled through references/pointers), can it
still be called object-oriented? (I'm not talking about an array of
references to objects, but an array of actual objects.)

  For example a heap (ie. what is used eg. in heap sorting) is an extremely
ingenuous form of binary tree in that all the elements in a heap can be
stored in an array and they require no ancillary data whatsoever (ie.
left/right/parent pointers or anything). Elements can be added and removed
from the heap in O(log n) regardless of this. (About the only thing that
is guaranteed about the distribution of the elements in the heap is,
however, that the largest element will always be at the root. However,
even this guarantee is quite useful in many tasks, such as maintaining
a fast priority queue or heap sorting.)

  The advantage of a heap is, of course, that it consumes the least amount
of memory because all the objects are in a contiguous array, rather than
being allocated individually and handled through references/pointers.

  However, can this be called object-oriented? Having objects in an array
excludes the possibility of using objects of a derived type (unless an
object of the derived type has the exact same size as the base type object;
even then it requires some low-levelish trickery to get it working, at
least in C++, and probably other languages where objects can be handled
by value and put into arrays). However, one of the basic ideas of OOP is
that whenever an object of type A is expected, an object of type B can be
given to it instead, if B has been derived from A (or from any of its
subclasses). An array of objects wouldn't support this.

-- 
                                                          - Warp

Post a reply to this message