>>11I'll finish reading Wadler and some related papers later.
Perhaps I'm a bit fuzzy on what you're suggesting. Is it that Haskell's idea of a function (which is completely different from functions in imperative languages) is sufficient to implement maps in general? Pretending for the moment that Haskell allows you to have two argument functions, a lookup function could take a map and a key and produce the associated value from the map. Using currying to get this in Haskell, we create a function that takes a map and produces a function that takes a key and produces the associated value. Ok, we can save that inner function instead of applying it right away, as it's already "bound" to the particular map. Is this what you're getting at? I'll assume it is for the moment.
Unfortunately, that function falls pretty short of the functionality of a map. It represents only one operation: look up a key. Maps need to be extensible (produce a new map with a key/value added, removed, or replaced), enumerable (what are the keys?), comparable (does this map have the same key/value pairs as this other map? Are they a superset?), and testable (is this key in it?). I suppose that might be its advantage as well. The function just takes a key and produces a value, regardless of how that is accomplished, so its behavior can be independent of its representation. It's just a discrete partial function (if you throw a Maybe in there to make it partial, which also gives you back the testable property above).
Now note that absolutely *any* function with the right signature can be used there instead, which is a kind of polymorphism over a single operation. That might sound freeing, but other languages certainly have closures with signatures. But in other languages you usually choose *not* to implement most polymorphism in this way, because it conceals the intention – that we wanted a map that was readable, extensible, enumerable, comparable, and testable. We didn't want to separate the functionality, we wanted an abstraction of an object for which all these operations apply, all to the same object. We want to carry these capabilities around in a bundle, an object, specifically designed for these purposes. That seems to be why Data.Map exists.
Interestingly, Java 1.1 -1.7 chose the /opposite/ approach by denying functions and /only/ providing bulky inner classes as a way of bundling functionality with functions... even if you only wanted one piece of functionality. Fortunately, this experiment in boilerplate-writing was concluded with Java 1.8.
I'm not particularly skilled at Haskell, so maybe you could walk me through translating the two lines of Avail code I provided earlier. The first line used "_:_:=_" to declare a local variable with a type and set its initial value. We could have left out the type and used "_::=_" instead, to define a local constant whose type was deduced from the expression (we have forward-only type deductions in Avail, for reasons I won't go into). The expression being assigned used the map construction operation "{«_→_‡,»}" (braces around a comma-separated list of right-arrow-separated pairs), and for the keys it used the set construction operation "{«_‡,»}" (i.e., braces around a comma-separated list of elements). For the empty set it used a zero-argument "∅" operation (just because {} means empty map, not set).
The second line created another set via "{«_‡,»}", looked that up as a key in m via "_[_]" (the lookup operation), converted the resulting integer (yes, it was known statically to be an integer) to a string via the smart quotes operator "“_”", and passed that string to "Print:_". Let's ignore the I/O aspect for this example.
I don't mean this to be a difficult challenge, although I suspect it is. I think after this, it should be pretty clear that whoever claimed Avail was based on Haskell was making a major category error :-).