Lambda the Ultimate

There was a good discussion of automatic lifting in APL in this previous discussion.

If you are really interested in lifting in the domain of arrays, I suggest that you study J rather than APL. J is the successor of APL, cleaning-up and advancing many of its concepts. There is a huge, up-to-date literature on J, and freely available implementations to play with and learn from.

In J, the central concept that one needs to know with respect to ‘lifting’ is rank, but there are a number of related and also important concepts: axis, shape, frame, cell, item, tally, verb rank….

The official J reference is the Dictionary (see esp. Chapter 20 ‘Rank’), but it is not suitable for a beginner. I'd suggest reading the following instead:

• the J Primer – Part 5, titles ‘Atom’, ‘List’, ‘Table’, etc;
• this article;
• Roger Hui's ‘Rank’ essays 1 and 2.

Now, J is also, like APL, dynamically typed. There are several substantial reasons for that, but think of it this way: in J, ranks play a similar role to that of types in, say, languages with algebraic type systems. In Haskell, types control how things interact; in J, it is ranks. And as value ranks are necessarily dynamic, the very concept of static ‘typing’ does not make much sense in J.

Wonderful, going to work through these. I see what you are saying about the typing. I will try to see types the J way.

The previous discussion James posted (excellent, thank you) brings up this issue. I'm not sure that I follow why this is a show stopper. My plan, which is why the suggestion of APL threw me off a bit :), was to rely on the type to dictate how, e.g., your above examples would behave. Indeed, I see now that a functor alone isn't sufficient, but perhaps an additional operation * : F(a->b)->F(a)->F(b) (applicative functor?) would do the trick.

In particular, it is clear that f: a->b should map to f:[a]->[b] via the map function in either APL or Haskell examples, i.e (+) [1,2] : [Double->Double]. The question lies as to how ((+) [1,2]) [10,20] should behave. i.e. how should we evaluate [Double -> Double][Double]. To be faithful to Haskell, this would lift to: do f <- (+)[1,2]; x <- [10,20]; return $ f x. But we could just as easily lift it to: map (\(f,x) ->f x) $ zip ((+)[1,2]) [10,20].

In general, given F(a->b) F(a) we get a choice as to how to evaluate, and we can do so by transforming F(a->b)F(a) to (*)(F(a->b)) F(a). If the list functor were to be augmented with the above * operation (call it Zip for APL behavior/and Cart for Haskell behavior), then we would be able to differentiate:
x : Zip a, y : Zip b, f : a -> b -> c |- f x y : Zip c
x : Cart a, y : Cart b, f : a -> b -> c |- f x y : Cart c
x : [a], y : [b], f : a -> b-> c |- f x y : (unable to resolve)

Is this the source of the "ambiguity" problem, or is there something I am missing?

You might be spot on with applicative functors. See f.e.
http://haskell.org/ghc/docs/latest/html/libraries/base/src/Control-Applicative.html#ZipList

So I think this changes your question to if there is a language with good syntactic support for applicative functors. Which I would like to know about too.