Re: Recursive algebraic data types

["Jeffrey R. Carter" <spam.jrcarter.not@spam.not.acm.org>]

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