From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=unavailable autolearn_force=no version=3.4.4 Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!feeder.eternal-september.org!aioe.org!.POSTED!not-for-mail From: "Dmitry A. Kazakov" Newsgroups: comp.lang.ada Subject: Re: Recursive algebraic data types Date: Wed, 7 Mar 2018 09:31:21 +0100 Organization: Aioe.org NNTP Server Message-ID: References: <7744da76-0ea5-459e-a55d-8b16d7b3ccdb@googlegroups.com> <65e6d0f9-7457-4584-9160-b5ca9db24599@googlegroups.com> NNTP-Posting-Host: MyFhHs417jM9AgzRpXn7yg.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Complaints-To: abuse@aioe.org User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:52.0) Gecko/20100101 Thunderbird/52.6.0 Content-Language: en-US X-Notice: Filtered by postfilter v. 0.8.3 Xref: reader02.eternal-september.org comp.lang.ada:50870 Date: 2018-03-07T09:31:21+01:00 List-Id: 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