Clojure 2d list to hash-map

Question 1

In order to be lazy, the computer will have to do a linear scan of the input sequence each time a key is requested, at the very least if the key is beyond what has been scanned so far. A naive solution is just to scan the sequence every time, like this:

(defn get-val [coll k]
  (some (fn [[a b]] (when (= k a) b)) coll))

(get-val '((1 1)(3 9)(5 17))
         3)
;=> 9

A slightly less naive solution would be to use memoize to cache the results of get-val, though this would still scan the input sequence more than strictly necessary. A more aggressively caching solution would be to use an atom (as memoize does internally) to cache each pair as it is seen, thereby only consuming more of the input sequence when a lookup requires something not yet seen.

Regardless, I would not recommend wrapping this up in a hash-map API, as that would imply efficient immutable "updates" that would likely not be needed and yet would be difficult to implement. I would also generally not recommend keywordizing the keys.

Question 2

The problem is that hash-maps can be neither infinite nor lazy. They designed for fast key-value access. So, if you have a hash-map you'll be able to perform fast key look-up. Key-value access is the core idea of hash-maps, but it makes creation of lazy infinite hash-map impossible.

Suppose, we have an infinite 2d list, then you can just use into to create hash-map:

(into {} (vec (map vec my-list)))

But there is no way to make this hash-map infinite. So, the only solution for you is to create your own hash-map, like Chouser suggested. In this case you'll have an infinite 2d sequence and a function to perform lazy key lookup in it.

Actually, his solution can be slightly improved:

(def my-map (atom {}))

(def my-seq (atom (partition 2 (range))))

(defn build-map [stop]
  (when-let [[k v] (first @my-seq)]
    (swap! my-seq rest)
    (swap! my-map #(assoc % k v))
    (if (= k stop)
        v
        (recur stop))))

(defn get-val [k]
  (if-let [v (@my-map k)]
    v
    (build-map k)))

my-map in my example stores the current hash-map and my-seq stores the sequence of not yet processed elements. get-val function performs a lazy look-up, using already processed elements in my-map to improve its performance:

(get-val 4)
=> 5
@my-map
=> {4 5, 2 3, 0 1}

And a speed-up:

(time (get-val 1000))
=> Elapsed time: 7.592444 msecs
(time (get-val 1000))
=> Elapsed time: 0.048192 msecs

Question 3

If you flatten it down to a list of (k v k v k v k v) with flatten then you can use apply to call hash-map with that list as it's arguments which will git you the list you seek.

user> (apply hash-map (flatten '((1 1)(3 9)(5 17))))
{1 1, 3 9, 5 17}

though it does not keywordize the first argument.

At least in clojure the last value associated with a key is said to be the value for that key. If this is not the case then you can't produce a new map with a different value for a key that is already in the map, because the first (and now shadowed key) would be returned by the lookup function. If the lookup function searches to the end then it is not lazy. You can solve this by writing your own map implementation that uses association lists, though it would lack the performance guarantees of Clojure's trei based maps because it would devolve to linear time in the worst case.

Im not sure keeping the input sequence lazy will have the desired results.

Question 4

To make a hashmap from your sequence you could try:

(defn to-map [s] (zipmap (map (comp keyword str first) s) (map second s)))

=> (to-map '((1 1)(3 9)(5 17)))
=> {:5 17, :3 9, :1 1}

Question 5

You can convert that structure to a hash-map later this way

(def it #(iterate (fn [[a b]] [(+ a 1) (+ b 1)]) [1 1])) 
(apply hash-map (apply concat (take 3 (it))))
=> {1 1, 2 2, 3 3}