[Nickle] How to make min do the right thing?
Bart Massey
nickle@nickle.org
Mon, 16 Sep 2002 10:06:13 -0700
The other obvious alternative is to use (representing lists
as arrays for convenience, ignoring the temporarily
extraneous s structure, and coding the whole thing out so
that we're clear on what's what)
real min2(real emptymin, real[*] vals) {
if (dim(vals) == 0)
return emptymin;
real m = vals[0];
for (int i = 1; i < dim(vals); i++)
if (vals[i] < m)
m = vals[i];
return m;
}
In this case
real argmin(real[*] vals) {
if (dim(vals) == 0)
return -1;
real m = vals[0];
int n = 0;
for (int i = 1; i < dim(vals); i++) {
if (vals[i] < m) {
m = vals[i];
n = i;
}
}
return n;
}
we should probably raise an exception on an empty input,
since this is essentially an error condition, but by that
logic so should String::index(), so what the heck. :-)
Finally, "the Nickle way" to do what you originally wanted
is probably to make an int list out of the arg list and
apply one of the above functions to it:
int min2a(int emptymin, s[*] vals) {
int[dim(vals)] as = { [i] = vals[i].a };
return min2(emptymin, as);
}
Note that the return is only allowed by the type system
because of our weirdo "implicit supertyping" rule, and that
indeed, we know we're doing the right thing here.
Interesting.
Alternatively, although it's ugly now because of no
parametric polymorphism, you could use the functional
approach...
poly[*] map(poly(poly) f, poly[*] vals) {
poly[dim(vals)] result = { [i] = f(vals[i]) };
return result;
}
int min2a(int emptymin, s[*] vals) {
return
min2(emptymin,
map(int func(s val) { return val.a; },
vals));
}
Of course, the *really* functional approach would use
compose() to get min2a from min2 and the lambda, but you get
the idea... Programming with combinators is cool if you
want to be really general, but kind of painful otherwise.
Bart
In message <15750.1439.119365.312422@scream.east.isi.edu> you wrote:
> I've got what seems like the simplest of problems, but I'm looking for
> a little guidance.
>
> I've got:
>
> typedef struct {
> int a, b;
> } s;
>
> I want to define the following three functions for computing minimum
> values in the obvious ways:
>
> int mina(s list ...) { /* return minimum a value */ }
> int minb(s list ...) { /* return minimum b value */ }
> int min(int list ...) { /* return minimum arg value */
>
> What's not obvious is what to do when any of these functions receive
> an empty list. Throwing an exception would seem natural, but it so
> happens that I have the following case in my algorithm:
>
> result = min(mina(foo ...), minb(bar ...))
>
> where I "know" that either dim(foo) or dim(bar) may be 0, but never
> both. So, I wouldn't mind getting an exception from the outer min, but
> I don't want either of the inner calls to throw an exception; I just
> want them to do the right thing.
>
> In C I would use INT_MAX to get what I want, but of course that's not
> an option.
>
> I guess I could achieve a similar result by using a union to return
> either an int or a value that should compare greater than any
> int. Something like:
>
> typedef union {
> int val;
> void max;
> void min;
> } extremal;
>
> extremal mina(s list ...)
> {
> extremal min = extremal.max;
>
> for (int i=0; i < dim(list); i++)
> if (min == extremal.max || list[i].a < min.val)
> min.val = list[i].a;
>
> return min;
> }
>
> That's pretty good. It's still easy to use mina directly to get an int
> or a run-time exception as appropriate:
>
> mina(foo...).val
>
> And I can also rewrite min as:
>
> extremal min(extremal list ...) { /* return minimum arg value */ }
>
> so that I get exactly the behavior I want with:
>
> min(mina(foo...), minb(bar...)).val
>
> The only downside is that the "min" function is no longer easy to use
> with int arguments since it now only accepts arguments of type
> extremal. And the guts of the min functions aren't as elegant as I
> would wish since I can't use the relational operators with extremal
> values, (min is even a little uglier than mina above). Clearly I'm
> really wanting better polymorphism here.
>
> What think ye, am I getting close to the nicklest way of doing this?
> (At least with the present-day implementation).
>
> -Carl
>
> --
> Carl Worth
> USC Information Sciences Institute cworth@east.isi.edu
> 3811 N. Fairfax Dr. #200, Arlington VA 22203 703-812-3725
>
> _______________________________________________
> Nickle mailing list
> Nickle@nickle.org
> http://nickle.org/mailman/listinfo/nickle