Lambda the Ultimate

I agree on this, only the paper makes a good case of having recursive map as a language feature-- does Haskell make recursive map easy?

Also what if the only way to deal with lists in the language is that, does it help resolve ambiguities?

In fact, the NTD system does not perform a recursive map in the instantiate case. Rather it applies the function on leaves, which are scalar. This becomes obvious with reverse(vector x):

reverse([[[1, 2, 3], [4, 5]], [6, 7]])
transpose -> [reverse([[1, 2, 3], [4, 5]]), reverse([6, 7])]
transpose -> [[reverse([1, 2, 3]), reverse([4, 5])], reverse([6, 7])]
distribute -> [[[3, 2, 1], [5, 4]], [7, 6]]

If that was a recursive map, we would end up with [[7, 6], [[5, 4], [3, 2, 1]]].
I am mostly-convinced that NTD is useful and seriously thinking of adding it to my language dodo now, but it will require a special syntax-- it will not be applied automatically everywhere.

I agree in principle, but my experience with APL variants has taught me that Haskell's support for this kind of thing has a way yet to go. Applicative functor operations help a bit, but then that breaks down for infix operators, which sucks, because of course arithmetic ends up being lifted to sequences all the time.

Anyway, I agree that the "everything is auto-lifted all the time" approach leaves a lot to be desired, but once you've really used it, the convenience is hard to give up. I think the right balance remains to be found.

For balance, I think the spread operator (*.) in Groovy is about right. To lift a method call, just use *. instead of . for the method qualifier. Thus

x*.foo()

is equivalent to

x.collect(element ->element.foo())

where "collect" is Groovy's name for "map" in other functional languages. Thus lifting isn't automatic, and doesn't cover the recursive lift case, but at one character it's hard to beat.

How does spread handle lifting over multiple arguments or lifting infix operators? I'm thinking specifically of things like q's f[x;;y]'[w;z], which partially applies f to x and y and then maps the result over w and z, or x + y * z, which just "does the right thing" whether x, y and z are scalars, collections, etc.

(I'm not trolling, I'm really curious. I also think q does not set a high bar in any respect, I'm only using it as an example. Frankly, I think the language is a mess.)

It only lifts the target, and doesn't do infix operators.

NT is only triggered when an actual argument of a function call is of a different type (specifically, a more "deeply nested" type) than the declared type for the corresponding parameter in the function definition. Therefore. there is no ambiguity in functions on recursive data types. The function is strictly defined for the base case.

SequenceL prevents overloading of functions in ways that conflict with the "automatic" overloading induced by NT. The question is whether it is more valuable to write such overloaded definitions, or to have the convenience of NT. For all of the industrial-size applications we have written, NT was more handy. Your results may vary ;)