www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Re: Type unions in D

reply bearophile <bearophileHUGS lycos.com> writes:
Justin Johansson:

But what if xs contains no numbers i.e. xs = (), the empty list?  What should
max( xs) return in the way of a meaningful result short of throwing an
exception?<

In both Python and my dlibs it throws an exception.
An elegant solution to this problem is to specify the max function as taking a
quantified list of zero or more numbers and returning another quantified list
of numbers which may contain either zero numbers or just one number: zero
numbers if the argument list is empty and a single number (being the maximum
number in the argument list) if the argument number list is non-empty.<

Cute.
The important point in this solution is realizing a type system that treats a
list of zero_or_one numbers, a list of zero numbers, a list of zero_or_more
numbers, etc, as distinct types.<

I don't understand the correlation from this last part and what you have written about max(). Maybe what can be useful is to define as a type a "not empty iterable", so if max() takes as input such type it's sure to not throw an exception. In general iterables can be lazy, their items can be computed on the fly, so there's no way to know at compile time if an iterable will be empty or not. Bye, bearophile
Sep 17 2009
parent Justin Johansson <procode adam-dott-com.au> writes:
bearophile Wrote:
 Justin Johansson:
The important point in this solution is realizing a type system that treats a
list of zero_or_one numbers, a list of zero numbers, a list of zero_or_more
numbers, etc, as distinct types.<

I don't understand the correlation from this last part and what you have written about max(). Maybe what can be useful is to define as a type a "not empty iterable", so if max() takes as input such type it's sure to not throw an exception. In general iterables can be lazy, their items can be computed on the fly, so there's no way to know at compile time if an iterable will be empty or not.

Perhaps I'm not as eloquent as some writers are, so perhaps I could recast the scene as follows: What is a type system? (Rhetorical question) When speaking of types most programmers think, well, is an int or a double, is it a thing (aka object) that one could apply some taxonomy to? Classical CS101: You have a car and a bike. Now come up with the typical OO class structure that has Vehicle as a base class of Car and of Bike. Mostly when thinking about types we think about the qualitative attributes of what we are trying to model .. and we make distinction of types based upon those qualities (and class hierarchies accordingly -- well up to the point that single inheritance breaks down but that's a side issue). OTH quantitative typing (layperson speak .. I'm not a published academic) considers the quantity of things to be separate types. For example, in some problem spaces, typically pattern matching, it may be useful to consider a dozen eggs (12 off) as being a different type to baker's dozen of eggs (13 off). Taking this further, one might well consider how to unify a type system based upon both qualities and quantities. Anyway, regarding my max() example, this was just a single case taken illustrating a problem in the quantitative typing domain. Noting that a number of repondents on this thread suggested various work arounds/solutions for this particular example, me thinks the bigger picture for my particular problem was missed. I've got a good collection of links regarding type systems which I can post if people are interested further in the subject. To be honest though, some of the literature looks like you have to be Einstein to understand it. Google for "type union", "existential types", "quantified types" and similar and you'll find yourself buried up to your neck in literature in no time. Cheers Justin Johansson
Sep 17 2009