* Recursive algebraic data types @ 2018-03-06 19:46 hnptz 2018-03-06 19:58 ` hnptz ` (3 more replies) 0 siblings, 4 replies; 11+ messages in thread From: hnptz @ 2018-03-06 19:46 UTC (permalink / raw) Does somebody have a generic package on recursive data types in Ada and is willing to share? ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Recursive algebraic data types 2018-03-06 19:46 Recursive algebraic data types hnptz @ 2018-03-06 19:58 ` hnptz 2018-03-06 20:45 ` gautier_niouzes 2018-03-06 20:28 ` Randy Brukardt ` (2 subsequent siblings) 3 siblings, 1 reply; 11+ messages in thread From: hnptz @ 2018-03-06 19:58 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Recursive algebraic data types 2018-03-06 19:58 ` hnptz @ 2018-03-06 20:45 ` gautier_niouzes 2018-03-07 5:53 ` Niklas Holsti 0 siblings, 1 reply; 11+ messages in thread From: gautier_niouzes @ 2018-03-06 20:45 UTC (permalink / raw) > 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. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Recursive algebraic data types 2018-03-06 20:45 ` gautier_niouzes @ 2018-03-07 5:53 ` Niklas Holsti 2018-03-07 8:31 ` Dmitry A. Kazakov 0 siblings, 1 reply; 11+ messages in thread From: Niklas Holsti @ 2018-03-07 5:53 UTC (permalink / raw) 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 . @ . ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Recursive algebraic data types 2018-03-07 5:53 ` Niklas Holsti @ 2018-03-07 8:31 ` Dmitry A. Kazakov 0 siblings, 0 replies; 11+ messages in thread From: Dmitry A. Kazakov @ 2018-03-07 8:31 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Recursive algebraic data types 2018-03-06 19:46 Recursive algebraic data types hnptz 2018-03-06 19:58 ` hnptz @ 2018-03-06 20:28 ` Randy Brukardt 2018-03-06 20:54 ` Jeffrey R. Carter 2018-03-06 21:14 ` Dmitry A. Kazakov 2018-03-06 21:25 ` Dmitry A. Kazakov 2018-03-06 21:54 ` hnptz 3 siblings, 2 replies; 11+ messages in thread From: Randy Brukardt @ 2018-03-06 20:28 UTC (permalink / raw) <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. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Recursive algebraic data types 2018-03-06 20:28 ` Randy Brukardt @ 2018-03-06 20:54 ` Jeffrey R. Carter 2018-03-06 21:14 ` Dmitry A. Kazakov 1 sibling, 0 replies; 11+ messages in thread From: Jeffrey R. Carter @ 2018-03-06 20:54 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Recursive algebraic data types 2018-03-06 20:28 ` Randy Brukardt 2018-03-06 20:54 ` Jeffrey R. Carter @ 2018-03-06 21:14 ` Dmitry A. Kazakov 1 sibling, 0 replies; 11+ messages in thread From: Dmitry A. Kazakov @ 2018-03-06 21:14 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Recursive algebraic data types 2018-03-06 19:46 Recursive algebraic data types hnptz 2018-03-06 19:58 ` hnptz 2018-03-06 20:28 ` Randy Brukardt @ 2018-03-06 21:25 ` Dmitry A. Kazakov 2018-03-06 21:54 ` hnptz 3 siblings, 0 replies; 11+ messages in thread From: Dmitry A. Kazakov @ 2018-03-06 21:25 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Recursive algebraic data types 2018-03-06 19:46 Recursive algebraic data types hnptz ` (2 preceding siblings ...) 2018-03-06 21:25 ` Dmitry A. Kazakov @ 2018-03-06 21:54 ` hnptz 2018-03-07 7:58 ` Jacob Sparre Andersen 3 siblings, 1 reply; 11+ messages in thread From: hnptz @ 2018-03-06 21:54 UTC (permalink / raw) 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? ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Recursive algebraic data types 2018-03-06 21:54 ` hnptz @ 2018-03-07 7:58 ` Jacob Sparre Andersen 0 siblings, 0 replies; 11+ messages in thread From: Jacob Sparre Andersen @ 2018-03-07 7:58 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2018-03-07 8:31 UTC | newest] Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2018-03-06 19:46 Recursive algebraic data types hnptz 2018-03-06 19:58 ` hnptz 2018-03-06 20:45 ` gautier_niouzes 2018-03-07 5:53 ` Niklas Holsti 2018-03-07 8:31 ` Dmitry A. Kazakov 2018-03-06 20:28 ` Randy Brukardt 2018-03-06 20:54 ` Jeffrey R. Carter 2018-03-06 21:14 ` Dmitry A. Kazakov 2018-03-06 21:25 ` Dmitry A. Kazakov 2018-03-06 21:54 ` hnptz 2018-03-07 7:58 ` Jacob Sparre Andersen
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox