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!news.swapon.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Niklas Holsti Newsgroups: comp.lang.ada Subject: Re: Recursive algebraic data types Date: Wed, 7 Mar 2018 07:53:27 +0200 Organization: Tidorum Ltd Message-ID: References: <7744da76-0ea5-459e-a55d-8b16d7b3ccdb@googlegroups.com> <65e6d0f9-7457-4584-9160-b5ca9db24599@googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Trace: individual.net NjS0/khLrYexpL4MdQD2Bw5CBWWvkFXq+Ge3Pp6jTUQ/GmXxen Cancel-Lock: sha1:L7hySunvyr2YvR8Lk9H6cBst9rw= User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:45.0) Gecko/20100101 Thunderbird/45.8.0 In-Reply-To: <65e6d0f9-7457-4584-9160-b5ca9db24599@googlegroups.com> Xref: reader02.eternal-september.org comp.lang.ada:50868 Date: 2018-03-07T07:53:27+02:00 List-Id: 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 . @ .