Re: ADTs in Euphoria
At 18:44 20/12/00 -0500, Ray Smith kindly replied:
>Hi sns,
>
>Without going into details .... cause I'm just a bit busy now ...
>you might like to look in Euphoria\demo directory.
>
>There is a demo prograsm called tree.ex - that counts words by adding
>them to a binary tree.
>
>There is also animal.ex which states that it uses a "tree like" structure
>for a very simple Expert system that guesses animals.
>
>Hope this hepls.
>
>Ray Smith
>
>
>
>On Thu, 21 Dec 2000 12:39:23 +1300, S Ns <sw at PARADISE.NET.NZ> wrote:
>
>>In reply to my query:
>>
>>>Hi I'm a newbie evaluating euphoria.
>>>
>>>Could someone briefly illustrate (or give a reference to some
>>>info on) how one would implement a doubly-linked list or
>>>binary search tree in Euphoria?
>>>
>>>Thanks in advance.
>>>
>>>--sns
>>
>>Dan Moyer kindly replied:
>>-------------------------
>>Not sure if this is what you mean, but in the RDS archives,
>>http://www.rapideuphoria.com/contrib.htm
>>Jiri Babor has "Associative Lists", Routines for manipulating lists of
>>key/value pairs.
>>
>>Can download directly from:
>>http://www.rapideuphoria.com/list.zip
>>
>>and Jeff Fielding expanded:
>>---------------------------
>>Both of these are a little more difficult, and less effective implemented
>>in Euphoria than implemented in C since Euphoria does not support
>>pointers, and it already has a dynamic array - the sequence.
>>
>>Doubly linked lists can be completely replaced by a simple sequence, since
>>sequences are dynamic arrays. Instead of dealing with pointers etc. you
>>can just use append, prepend, & and subscripts to get the same
>>functionality.
>>
>>Binary search trees can also be implemented in multi-dimensional
>>sequences, though all the subscripting would probably make them rather
>>ineffective.
>>
>>Of course, you could use allocate, peek, poke, and free to do a C-like
>>implementation of the above. However, these are all rather expensive
>>functions and it is much faster to use sequences and other built-in
>>Euphoria data types.
>>---------------------------------------------------------------------
>>
>>I'd like to be able to use Euphoria for more than
>>just little scripts.
>>
>>From the version 2.2 reference manual:
>>-------------------------------------
>><quote>
>>
>> 2.3 Euphoria versus Conventional Languages
>> ==========================================
>>
>> By basing Euphoria on this one, simple, general, recursive
>> data structure, a tremendous amount of the complexity
>> normally found in programming languages has been avoided.
>> The arrays, structures, unions, arrays of records,
>> multidimensional arrays, etc. of other languages can all
>> be easily represented in Euphoria with sequences. **So can
>> higher-level structures such as lists, stacks, queues, trees etc.**
>>
>></quote>
>>
>>The last line talks about a capability that is important to
>>me. I think it can be done 'fairly' efficiently after all
>>RDS mention porting apps from C to Eu and advertise this
>>service on their website.
>>
>>I don't know if this is possible, but I'll just sketch
>>it anyway as indication. Look at a binary tree:
>>
>>The node is a 3-element sequence where element:
>>1. is the data (this could be a record - represented as a
>> sequence of course)
>>2. is the left child which is a node sequence like the
>> parent (recursive)
>>3. is the right child like 2.
>>
>>I don't know if 2 and 3 are possible in this fashion.
>>
>>I don't think that this is the same as Jeff's
>>mutlidimensional sequence.
>>
>>If this is possible in Eu then we have to implement some
>>operations: e.g. assume our tree is tree1:
>>
>>our interface operations could be:
>>
>> tree_new(tree1)
>> tree_add(tree1, some_data)
>> tree_find(tree1, some_data)
>> tree_copy(tree2, tree1)
>>
>>Clearly, we need a function to traverse the tree.
>>
>>So,
>>if we can represent the node and a traversal function
>>we are most of the way there.
>>
>>Thoughts?
>>
>>Thanks in advance.
>>
>>-- sns
---------------------------------------------------------
Yep, that's what I was looking for. Thank you Ray.
--sns
|
Not Categorized, Please Help
|
|
