Revamping the numeric classes

Bjorn Lisper lisper@it.kth.se
Thu, 8 Feb 2001 13:39:51 +0100 (MET)


>I see. So you can transform arbitrary function of type a->b->c
>to a function of type [a]->b->[c], by applying
>    \f x y -> map (\z -> f z y) x
>and similarly a->b->c to a->[b]->[c]. But then there are two ways of
>transforming a->b->c to [a]->[b]->[[c]] and the order of applying the
>former transformations does matter. Worse: a third way is to apply zipWith
>and then promote the result to a single-element list. Or maybe map the
>result to a list of single-element lists...

There should be no transformation to type [a]->[b]->[[c]] in this case.
If f is applied to arguments of type [a] and [b] then this should be
interpreted as the elementwise application of f to the two argument lists,
and the result type should then be [c]. Note that [a]->[b]->[[c]] is
"more lifted" than [a]->[b]->[c].

Elementwise application to one argument should transform to map, of several
arguments to zipWith with appropriate arity.

It is easier to see how it should work if we skip lists, so we don't have to
deal with maps and zipWiths and other list functions.  Let us consider
elementwise application of f over indexed entitites. For simplicity we
consider functions as our indexed entities, but it could as well be arrays.
With f as above, then f x y should be transformed to:

(1) x :: d -> a, y :: b yields \i -> f (x i) y
(2) x :: a, y :: d -> b yields \i -> f x (y i)
(3) x :: d -> a, y :: d -> b yields \i -> f (x i) (y i)

Here (3) is "full" elementwise application, and (1) and (2) are "partial"
elementwise applications where the unlifted argument can be seen as
promoted.  If you have list instead of functions, then the transformation
should insert list primitives with the corresponding effect.

>Sorry, IMHO it's ambiguous as hell except very simple cases.

Of course the type/term transformation system must have the property that
if different transformations can yield the "best" type (wrt liftedness),
then the transformed expressions should be semantically equivalent. I believe
a type/term transformation system with this property can be designed, but
the details remain to be worked out.

Björn Lisper

(Is this discussion still of interest to the Haskell list members? Or should
we take it offline?)