0

I have an infinite list like that:
((1 1)(3 9)(5 17)...)
I would like to make a hash map out of it:
{:1 1 :3 9 :5 17 ...)

Basically 1st element of the 'inner' list would be a keyword, while second element a value. I am not sure if it would not be easier to do it at creation time, to create the list I use:

(iterate (fn [[a b]] [(computation for a) (computation for b)]) [1 1])

Computation of (b) requires (a) so I believe at this point (a) could not be a keyword... The whole point of that is so one can easily access a value (b) given (a).

Any ideas would be greatly appreciated...

--EDIT--
Ok so I figured it out:

(def my-map (into {} (map #(hash-map (keyword (str (first %))) (first (rest %))) my-list)))

The problem is: it does not seem to be lazy... it just goes forever even though I haven't consumed it. Is there a way to force it to be lazy?

6
  • 1
    What's the point of having an infinite hash-map? You cannot build that structure in creation time since hash-map doesn't support nth operation.
    – guilespi
    Apr 9, 2013 at 0:50
  • I am never intrested in nth, but I will always know the keyword and I am intrested in a value associated with that keyword Apr 9, 2013 at 0:54
  • I've posted a way to create a hash-map after the lazy-seq has been created, let me know if ok
    – guilespi
    Apr 9, 2013 at 1:01
  • 1
    Clojure's maps are not lazy, and It's hard to see how they could be correct if they where. Apr 9, 2013 at 1:39
  • yep this makes sense now that I think about it... Apr 9, 2013 at 1:42

5 Answers 5

3

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
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.

4
  • 1
    Thanks for the in-depth explanation. It seems to me as this is too much trouble so I will stay with a list. Since I know the keys are all the odd numbers, for a key X I can quickly look-up by doing (nth mylist (/ (- X 1) 2)) Apr 9, 2013 at 8:40
  • Fair enough, but if the input is a lazy seq, nth will still do a linear scan from the beginning for each lookup.
    – Chouser
    Apr 9, 2013 at 13:04
  • I know, but this is always the deal, I will have to consume the sequence up to a nth element sooner or later right? whether I transform it somehow to a map, wrap it in a function to get nth element or just simply (nth) it... Apr 9, 2013 at 22:32
  • There will be no difference on the first call to the get-val function, but by transforming your lazy-seq into a map you'll save a lot on later calls. Apr 10, 2013 at 10:13
1

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.

1
  • And is not lazy either (def testme (apply hash-map (lazy-seq-here))) chokes the CPU Apr 9, 2013 at 1:11
0

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}
0

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}
2
  • this would work but I need the hash-map to be infinite (and lazy) just like the list... Apr 9, 2013 at 1:09
  • But if you have a sequence where each value is constructed from the previous one, there is no way to obtain a particular key without realizing all the previous ones. In that case just redefine the get function to do that(realize the sequence until the desired key found)
    – guilespi
    Apr 9, 2013 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.