Recursive algebraic data types

Recursive algebraic data types

[hnptz]

Does somebody have a generic package on recursive data types in Ada and is willing to share?

Re: Recursive algebraic data types

[hnptz]

On Tuesday, March 6, 2018 at 8:47:00 PM UTC+1, hn...@yahoo.de wrote:
> Does somebody have a generic package on recursive data types in Ada and is willing to share?

for definition: please have a look at https://en.wikipedia.org/wiki/Recursive_data_type

Re: Recursive algebraic data types

[gautier_niouzes]

> for definition: please have a look at https://en.wikipedia.org/wiki/Recursive_data_type

"In computer programming languages, a recursive data type (also known as a recursively-defined, inductively-defined or inductive data type) is a data type for values that may contain other values of the same type."

The definition given above is nonsensical: either the data type is empty or infinitely large...

In the examples given (List), the type names can mean either a pointer to the real data, or the data itself (a list's node in that case). Clearly they are playing with words there: a node doesn't really contain the next node, but a pointer (or a reference) to the next node. So it's not really recursive, only in appearance. They play with a shortcut notation.

Re: Recursive algebraic data types

[Niklas Holsti]

On 18-03-06 22:45 , gautier_niouzes@hotmail.com wrote:
>> for definition: please have a look at
>> https://en.wikipedia.org/wiki/Recursive_data_type
>
> "In computer programming languages, a recursive data type (also known
> as a recursively-defined, inductively-defined or inductive data type)
> is a data type for values that may contain other values of the same
> type."
>
> The definition given above is nonsensical: either the data type is
> empty or infinitely large...

No, the definition makes mathematical sense. Even if the "contained" 
values are of the same _type_ as the containing value, they are 
different (and "smaller") _values_, so the recursive containment can 
terminate.

For example, in mathematics the set of natural numbers, N, is usually 
defined in this recursive way:

    "zero", 0, is the empty set: {}
    "one", 1, is the set that contains zero: {0}
    "two", 2, is the set that contains zero and one: {0,1}
    and so on.

Inductively, a number n is the set that contains the numbers smaller 
than n: {0, 1, ..., n-1}.

> In the examples given (List), the type names can mean either a
> pointer to the real data, or the data itself (a list's node in that
> case). Clearly they are playing with words there: a node doesn't
> really contain the next node, but a pointer (or a reference) to the
> next node. So it's not really recursive, only in appearance. They
> play with a shortcut notation.

They are defining a mathematical (view of a) "type", which can be 
implemented in various ways in a programming language. Of course I agree 
that implementations normally use pointers, mainly to avoid copying 
large values (and to allow values with cycles). In the example, I think 
List is simply a "by reference" type, so all "List" variables are pointers.

One can certainly implement this "List" type in Ada, without pointers, 
by implementing a List-of-A as the Ada type array (Positive range <>) of 
A, where the head element of a list L is L(L'First) and the tail is 
L(L'First+1 .. L'Last). Each "cons" operation would of course require 
making a copy of the operand list, but that is just implementation detail.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Recursive algebraic data types

[Dmitry A. Kazakov]

On 07/03/2018 06:53, Niklas Holsti wrote:
> On 18-03-06 22:45 , gautier_niouzes@hotmail.com wrote:
>>> for definition: please have a look at
>>> https://en.wikipedia.org/wiki/Recursive_data_type
>>
>> "In computer programming languages, a recursive data type (also known
>> as a recursively-defined, inductively-defined or inductive data type)
>> is a data type for values that may contain other values of the same
>> type."
>>
>> The definition given above is nonsensical: either the data type is
>> empty or infinitely large...
> 
> No, the definition makes mathematical sense. Even if the "contained" 
> values are of the same _type_ as the containing value, they are 
> different (and "smaller") _values_, so the recursive containment can 
> terminate.

I disagree. The value terminates, the type does not. It is supposed to 
be a type algebra, not an algebra of values, e.g. to produce an infinite 
set of values as in your example with natural numbers.

A recursive definition of a type could deploy generics when a generic 
instance were used in another instance. The progression would stop at 
some point. E.g. a multidimensional array defined recursively

    generic
       N : Natural;
    package Generic_Array
       type Array_Type is array (Positive range <>)
          of Generic_Array (N - 1);
    end Generic_Array;

Once instantiated with some N there will be no recursion, because type 
algebra is a meta-language to object language of normal types and values.

I would say where it comes to the type algebra, languages like Ada have 
much better type operations than recursion: built-in arrays, access 
types, class-wide types/inheritance.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Recursive algebraic data types

[Randy Brukardt]

<hnptz@yahoo.de> wrote in message 
news:e3aea96c-8c5d-4569-abad-0d98e6cfc993@googlegroups.com...
> Does somebody have a generic package on recursive data types in Ada and is 
> willing to share?

A "recursive data type" is illegal in Ada: a type can never depend on 
itself, directly or indirectly. You have to break this sort of thing with an 
intervening access type, which brings a world of complications in storage 
management.

Perhaps you meant something else???

                                 Randy.

Re: Recursive algebraic data types

[Jeffrey R. Carter]

On 03/06/2018 09:28 PM, Randy Brukardt wrote:
> 
> A "recursive data type" is illegal in Ada: a type can never depend on
> itself, directly or indirectly. You have to break this sort of thing with an
> intervening access type, which brings a world of complications in storage
> management.

You have to break it with something, but that doesn't need to be an access type. 
Consider S expressions (usually shortened to sexes), which are either an atom or 
a list of zero or more sexes:

    type Sex (Is_Atom : Boolean := False) is tagged private;
private
    type Root is interface;

    package Sex_Lists is new
       Ada.Containers.Indefinite_Vectors (Positive, Root'Class);

    type Sex (Is_Atom : Boolean := False) is new Root with record
       case Is_Atom is
       when False =>
          List : Sex_Lists.Vector;
       when True =>
          Atom : Atom_Value;
       end case;
    end record;

The only downside of this is that any element you obtain from S.List has to be 
converted to Sex, which is just noise. Better would be if we could instantiate 
Indefinite_Vectors with type Sex directly, before it's full definition is seen.

-- 
Jeff Carter
"He that hath no beard is less than a man."
Much Ado About Nothing
132

Re: Recursive algebraic data types

[Dmitry A. Kazakov]

On 2018-03-06 21:28, Randy Brukardt wrote:
> <hnptz@yahoo.de> wrote in message
> news:e3aea96c-8c5d-4569-abad-0d98e6cfc993@googlegroups.com...
>> Does somebody have a generic package on recursive data types in Ada and is
>> willing to share?
> 
> A "recursive data type" is illegal in Ada: a type can never depend on
> itself, directly or indirectly. You have to break this sort of thing with an
> intervening access type,

Right, but it is self-referential nonetheless.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Recursive algebraic data types

[Dmitry A. Kazakov]

On 2018-03-06 20:46, hnptz@yahoo.de wrote:
> Does somebody have a generic package on recursive data types in Ada and is willing to share?

That is impossible because generics are instantiated manually, so 
recursion cannot be built on instantiation.

Otherwise self-referential types are allowed on generics.

P.S. As it was already said the definition from Wikipedia does not make 
sense.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Recursive algebraic data types

[hnptz]

On Tuesday, March 6, 2018 at 8:47:00 PM UTC+1, hn...@yahoo.de wrote:
> Does somebody have a generic package on recursive data types in Ada and is willing to share?

It is mentioned at several places e.g. in

http://web.mit.edu/6.005/www/fa16/classes/16-recursive-data-types/recursive/

that an implementation exists. Can it be simulated in Ada from Java or Haskell?

Re: Recursive algebraic data types

[Jacob Sparre Andersen]

hnptz@yahoo.de writes:

> http://web.mit.edu/6.005/www/fa16/classes/16-recursive-data-types/recursive/

Implementing that in Ada isn't too hard.  But it is also a part of the
Ada standard library, so why worry about writing it yourself?

See <http://www.ada-auth.org/standards/rm12_w_tc1/html/RM-A-18-3.html>.

Greetings,

Jacob
-- 
Beware of people with Gnus, they may Hurd you.