Because I'd expect all maps to provide roughly similar interfaces whether they're assoc lists, hashmaps, btrees, HAMT, …: iterate all entries, presence of a key, get value for key, insert (key, value), remove key (and value), possibly some other niceties on top (e.g. update value in-place, merge maps, …) but those are extras.
let max_map_regexp = 500 (* lines - see below *)
(* Format of the map_file. *)
type map_file_t =
| Map of ((Pcre.regexp * Pcre.regexp *
Pcre.regexp * Pcre.regexp) *
(float option * bool * Inp.params)) list
| Hash of (string * string * string * string,
float option * bool * Inp.params) Hashtbl.t
let run map_filename =
(* Parse the map file. *)
let csv = Csv.load map_filename in
if Csv.lines csv < 2 then
failwith (map_filename ^
": bid file should contain headings and at least one row of data");
let csv' = List.tl csv in (* Ignore headings. *)
(* If the map file is > max_map_regexp lines long then regular
* expressions are banned and a more efficient hash table format
* is used for lookups. Otherwise the program takes far too long
* to run.
*)
let map_file =
if List.length map_file <= max_map_regexp then (
Map (List.map (
fun ((c_name, ag_name, kw_text, kw_type), a) ->
(compile c_name, compile ag_name, compile kw_text,
compile kw_type), a
) map_file)
) else (
(* Regexps banned from large map files. *)
Hash (
let h = Hashtbl.create (List.length map_file) in
List.iter (
fun ((c_name, ag_name, kw_text, kw_type), a) ->
Hashtbl.add h (c_name, ag_name, kw_text,
String.lowercase kw_type) a
) map_file;
h
)
) inTo make an n^2 algorithm n (or n log n), you pretty much always need to add in some constant time or logarithmic data structure. That requires tracking that structure, usually generating a good key, etc.
I'm not saying that's really all that extreme. It just means your previous 5 line algorithm will often "bloat" to 10 or more lines with a new concept to track. This is where I see some saying "not elegant".
> Being written in a functional language meant that using association lists (linked lists for key/value) was very natural. […] After changing all the places to use a hash table it again ran in sub-second, although the code was nowhere near as elegant.
You're not tracking more things (just tracking a hashmap instead of a list), you're not generating anything different, you don't have any new concept to track.
All I'm asking is where the apparently significant loss of elegance would come from.
In a word, you're losing a persistent data structure[1]. And this can go beyond just loss of elegance. Sometimes, functional programs will depend on immutability of data structures for performance optimizations and even for functionality (like keeping a version history).
It's true that there are a few 3rd party implementations that I've noticed before, but not sure how robust and well-tested these are. I'd hesitate to use them or something I wrote in production without careful review.
In any case, persistent HAMTs are a relatively new phenomenon that are just starting to catch on, and this story is described as being "back in the day". It's unlikely this option was available to him even if he were willing to write an implementation himself or use an untested 3rd-party implementation.
Maybe one will be added eventually to one of the OCaml standard libraries, which would be great.
A trivial example, I recall about 1 month ago calling it out on a Javascript code review where someone was doing a `someList.find(x => x === "something")` inside a loop creating O(n^2) complexity. Rather than change the entire codebase wherever `someList` is used into a new type it is often easier just to suggest we build a Set (linear on length of `someList`) before the loop and use that for lookups within the loop (constant).
Of course, I am talking about circumstances clearly outside of your original model of OPs description. I am tracking more things (the new Set). However, I realize that to give the full context as to why the type of `someList` from my trivial example _couldn't_ be changed easily and why creating a new Set was the most prudent option would require a comment even longer than this essay. So I give OP the benefit of the doubt that he was in a similar situation where using the hashmap everywhere was either difficult or impossible.
let m' = (k, v) : m
let m' = insert k v m
In contrast, languages like Perl or Python have literals and syntax support for both lists and mapping-type data structures (hashes in Perl, dicts in Python), so using either one is roughly equally elegant, and you are more free to choose one or the other based on performance concerns.
But well. In Haskell assotiation lists are also the default, as they don't impose any stictness and are very fast to iterate. So that is what you get from libraries.
If you need a map, you will have to first construct it, then run your code. But of course, if you are the one creating the lists, it does change very little.