Neat and tidy solution to following problem?

Neat and tidy solution to following problem?

[chris.danx]

Hi,

As part of an assignment we have to split text up into words, and check if
they're in a document.  I'm ok with the assignment I just wondered if there
was an Ada like equivalent to tuples that didn't involve defining an
explicit record type (say word_and_remaining type)?  We did a similar task
in Haskell and by passing out more than one item of different types as a
single item was very tidy and easy (see below).


Some Haskell code for a simple text function

> getWord :: String -> (String, String)
> getWord []       = ([], [])
> getWord (' ':[]) = ([], [])
> getWord (x:xs)
>    | (x == ' ')  = ([], trim xs)
>    | otherwise   = ([x] ++ selection, remList)
>      where (selection, remList) = getWord xs


I'm just wondering if there's a way to have something similar in Ada 95 like
have two items returned from a function but not have to declare an explicit
type.


Regards,
Chris

p.s. please don't post any code specific to cutting up text into words, it
could negatively impact ppls marks (and DON'T send me any code privately).

p.p.s. this isn't intended as a Haskell is better than Ada post (both are
good tools).  The intention is to find another way of doing the same task so
no language Holy Wars attributed to my post, if you don't mind.

Re: Neat and tidy solution to following problem?

[Preben Randhol]

On Tue, 7 May 2002 19:24:27 +0100, chris.danx wrote:
> Hi,
> 
> As part of an assignment we have to split text up into words, and check if
> they're in a document.  I'm ok with the assignment I just wondered if there
> was an Ada like equivalent to tuples that didn't involve defining an
> explicit record type (say word_and_remaining type)?  We did a similar task
> in Haskell and by passing out more than one item of different types as a
> single item was very tidy and easy (see below).

I'm not sure I understand your question as I don't know Haskell and
cannot understand the code. But if you have your whole text in a
string why don't you find the beginning and end position of the words
and then scan the document for them? But probably I'm talking about
something different :-)

Preben

Re: Neat and tidy solution to following problem?

[chris.danx]

"Preben Randhol" <randhol+abuse@pvv.org> wrote in message
news:slrnadga2g.c0c.randhol+abuse@kiuk0152.chembio.ntnu.no...
> On Tue, 7 May 2002 19:24:27 +0100, chris.danx wrote:
>
> I'm not sure I understand your question as I don't know Haskell and
> cannot understand the code. But if you have your whole text in a
> string why don't you find the beginning and end position of the words
> and then scan the document for them? But probably I'm talking about
> something different :-)

Yes it is something different.  In an FPL you can return a tuple of items
from a function just as easily as you can return a single item (I think that
FPLs regard them as a single item anyway, they're just easier to use).

In the example given previously, the function getWord is declared like this

getWord :: String -> (String, String)

This means it takes a string and returns a pair of strings as a tuple.  If
you want to add all the words in the String to a data structure in another
function, you can use recursion.  Somethings might just be neater if this
could be done without fussing with explicit* record types.


Chris

*explicit in the sense that is defined/declared(? I hate those two words!!!)
before it is used in the return area of function.

Re: Neat and tidy solution to following problem?

[achrist]

"chris.danx" wrote:
> 
> I'm just wondering if there's a way to have something similar in Ada 
> 95 like have two items returned from a function but not have to 
> declare an explicit type.
> 

You would do this in Ada as a procedure (not a function) with multiple
in out parameters.  

I'd be interested to know how well recursion in Ada substitutes for 
looping (efficiency-wise).  Some of the functional languages are not
really high performance, and it would be interesting to see if you could
get about the same level of performance from the same style of coding 
using a procedural language.  In your example, for example, our spec 
might say that words are never very long (say more than 50 characters or 
so), so we wouldn't have to worry about problems with very deep
recursions.

However, Ada is a procedural language.  If you are using Ada, then 
presumably you are not allergic to procedural devices like looping
and in out parameters.  A recursive algorithm that eliminates but one
level of straightforward looping could be a puzzlement to an Ada reader.


Al

Re: Neat and tidy solution to following problem?

[chris.danx]

<achrist@easystreet.com> wrote in message
news:3CD83B55.75FC2B01@easystreet.com...
> "chris.danx" wrote:
> >
> > I'm just wondering if there's a way to have something similar in Ada
> > 95 like have two items returned from a function but not have to
> > declare an explicit type.
> >
>
> You would do this in Ada as a procedure (not a function) with multiple
> in out parameters.

That's one of two solutions that spring immediately to mind (in fact it's
how I've implemented it, and would usually do so).

> I'd be interested to know how well recursion in Ada substitutes for
> looping (efficiency-wise).  Some of the functional languages are not
> really high performance, and it would be interesting to see if you could
> get about the same level of performance from the same style of coding
> using a procedural language.

It seems the techniques in compiler construction for procedural/imperative
languages are well studied and understood but for functional languages the
situation is different.  We just haven't gotten clever enough to compile
functional languages to similarly efficient code.  :)


> In your example, for example, our spec  might say that words are
> never very long (say more than 50 characters or so), so we
> wouldn't have to worry about problems with very deep recursions.

In this case the length of the strings per line in the file is left
unspecified, and also the size of the document.  If it's large then there'd
probably be a problem with a recursive solution unless the recursion
operates in more or less constant space (can't remember what this is called,
but iirc it's doable for a variety of problems).

Chris

Re: Neat and tidy solution to following problem?

[Jeffrey Carter]

"chris.danx" wrote:
> 
> In the example given previously, the function getWord is declared like this
> 
> getWord :: String -> (String, String)
> 
> This means it takes a string and returns a pair of strings as a tuple.  If
> you want to add all the words in the String to a data structure in another
> function, you can use recursion.  Somethings might just be neater if this
> could be done without fussing with explicit* record types.

In Ada every type must be explicitly declared before it can be used.
There are no exceptions to this rule. So it might be "neat" or "keen" or
even easier to hack in Ada if this weren't the case, but that doesn't
change Ada.

-- 
Jeff Carter
"Hello! Smelly English K...niggets."
Monty Python & the Holy Grail

Re: Neat and tidy solution to following problem?

[Danx]

Jeffrey Carter <jrcarter@acm.org> wrote in message news:<3CD87B38.D3DE1CC4@acm.org>...

> In Ada every type must be explicitly declared before it can be used.

The function would still have a "return type" explicitly given when
it's declared so that wouldn't be non-Adaish.  The explicitness I was
talking about was this

type some_record 
   is record
      the_word : word;
      remaining : some_string;
   end record;

function get_word (text : in some_string) 
   return some_record;

rather than

function get_word (text : in some_string)
   return (word, some_string);


it could be defined like this:

function get_word (text : in some_string)
   return (word, some_string) is
begin
   -- do somethis with the string, 
   -- finding w and str.

   return (w, str);
end get_word;

and used something like this:

...
(a, b) := get_word (temp);
...

> There are no exceptions to this rule. So it might be "neat" or "keen" or
> even easier to hack in Ada if this weren't the case, but that doesn't
> change Ada.

It was curiosity, not an attempt to make things easier to "hack".


Chris

Re: Neat and tidy solution to following problem?

[Robert I. Eachus]

chris.danx wrote:

  
> In this case the length of the strings per line in the file is left
> unspecified, and also the size of the document.  If it's large then there'd
> probably be a problem with a recursive solution unless the recursion
> operates in more or less constant space (can't remember what this is called,
> but iirc it's doable for a variety of problems).


Actually, in this case there is an extremely elegant Ada pattern that 
works for general problems of this type. And I assume that anyone who 
had this as a homework assignment has turned it in.

For example, in KWIC (key word in context) indexing programs, you want 
to find all instances of every token without "losing" the context, so an 
index into the original source is a very useful representation.

You want to create a data structure Token_List of the form:

type Token is record First, Last: Natural; end record;
type Token_Array is array (Integer range <>) of Token;
type Token_List(Length: Integer) is record
   Source: Ada.Strings.Unbounded.Unbounded_String;
   Tokens: Token_Array(1..Length);
end record;

And have a function which returns one object of the type properly 
populated.  Notice that there is no default for the Index, so this is 
not what Alsys called a mutable object.  Also if you felt like it, you 
could replace the Unbounded_String by a String, with another discriminant.

The code looks like this.  I have dressed it up as a generic only as a 
way of leaving the procedure Next_Token undefined.

generic
   Input: String;
   with procedure Next_Token(Start: in Integer;
                             Found: out Boolean;
                             First_Position, Last_Position: out Integer);
function Find_Tokens return Token_List;

function Find_Tokens return Token_List is
   type Token_List_Access is access all Token_List;
   TLA: Token_List_Access;

   procedure Recur(Starting_Place, Index: in Natural) is
     More: Boolean;
     First, Last: Natural;
   begin
     Next_Token(Starting_Place, More, First, Last);
     if More
     then
       Recur(Last+1, Index+1);
       TLA.Tokens(Index).First := First;
       TLA.Tokens(Index).Last := Last;
     else
       TLA := new Token_List(Index - 1);
       TLA.Source := Ada.Strings.Unbounded.To_Unbounded_String(Input);
     end if;
    end Recur;

  begin Recur(1,1); return TLA.all; end Find_Tokens;

This code compiles, if it is suitably packaged. Of course proper 
functioning depends on the definition of Next_Token, and whether it 
meets your definition of proper functioning. Notice that the scope of 
the access type is left when you return from Find_Tokens, so there is no 
question of storage leaks, and only one object of the type is created 
anyway...