In the book Learn You a Haskell For Great Good Chapter 7 Module, section Data.Map. I try to understand the type “Map.Map a b”, where import qualified Data.Map as Map and the function type “a → b”.
Here are my observation :
By author’s explanation, I feel like a term in type “Map.Map a b” looks like an association list in which any two tuples in the list don’t have same component in the first entry.
A term f in the function type “a → b” always defined by composition of some “known” functions.
But the author also introduce a function map which has type “(a → b) → [a] → [b]”.
I want to know are there any relation between the function map and the type “Map.Map”? I also want to know if type “Map.Map” and “a → b” are different representation of same thing. Please correct me if I have the wrong idea in mind! I was really confused!
Map k v is what some other languages call a dictionary. It’s a key-value mapping that associates keys of type k with values of type v. It is like an association list but much more efficient (You really wouldn’t want to use association lists in practice).
The connection between Map k v and k -> v is that technically speaking, Map k v represents a partial finite function from k to v, i.e. a function that is only defined on a finite number of inputs (and mathematicians call functions maps sometimes).
In day to day programming it’s more useful to think of Map as a data structure with an insert and a lookup operation though.
map-the-function is completely unrelated. I don’t actually know why it’s called that, but it’s definitely not because of any connection to Map.
map and Map aren’t entirely unrelated; both have their origin in the mathematical term ‘mapping’, and both are meant to evoke a sort of correspondence between two domains. A Map represents a correspondence between keys and values. map the function (a naming tradition that dates back at least as far as LISP 1 in 1960) uses a per-element function to create a correspondence between an input list and an output list.
Consider the correspondence between a physical map and the territory it depicts. The map function might evoke the process of creating the physical map, roaming around the territory and constructing a copy of the territory on paper using some fixed translation logic. Or, you might imagine storing geographical coordinates of landmarks as the keys in a Map data structure, with the corresponding values being the landmark names that appear in the paper document. Two very different approaches, but both gesturing at a similar concept, and different corners of computer science borrowed the word ‘map’ to represent that concept at different times.