![](/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) |
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
|
![](/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 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
|
![](/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 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/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 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
From: Nicolas Alvarez
Subject: Re: Binary trees, branches and leaves
Date: 4 Mar 2010 21:58:24
Message: <4b907350@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/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 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |