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?)