lazy-map: a possible implementation
mb
I needed a lazy-map, similar to a lazy-cons. As a first shot I did
the attached implementation. It is not perfect, but it does its job.
Since I'm not very experienced with Lisp, I'd appreciate any comments.
(Also: maybe this can done already in Clojure?)
Basic idea:
The lazy-map macro returns a closure over map, whose values are
evaluated
lazily on the first access. The resulting value is stored. This could
also be done via a memoized function (as pointed out by Chouser),
however
I wonder whether this will cause a space leak. Therefore I didn't use
memoize from clojure-contrib.
(def lmap (lazy-map :Key1 (something-to-be 'done :lazily)
:Key2 "may be also simple"))
...
(lmap :Key1) ; (something-to-be) call will be evaluated here.
Sincerely
Meikel
Hmmm... Google doesn't let me attach files via the online interface.
So I put here inline. Sorry.
----8<----
;-
; Copyright 2008 (c) Meikel Brandmeyer.
; All rights reserved.
;
; Permission is hereby granted, free of charge, to any person
obtaining a copy
; of this software and associated documentation files (the
"Software"), to deal
; in the Software without restriction, including without limitation
the rights
; to use, copy, modify, merge, publish, distribute, sublicense, and/or
sell
; copies of the Software, and to permit persons to whom the Software
is
; furnished to do so, subject to the following conditions:
;
; The above copyright notice and this permission notice shall be
included in
; all copies or substantial portions of the Software.
;
; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR
; IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY,
; FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
SHALL THE
; AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER
; LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM,
; OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN
; THE SOFTWARE.
(clojure/in-ns 'lazy-map)
(clojure/refer 'clojure)
(defmacro lazy-map
"Lazy-map creates the map and returns a closure as function over the
map's
keys. Each value is evaluated as most once."
[& kvs]
(loop [[k v & r :as kvs] kvs
lmap {}]
(if (nil? kvs)
`(let [lmap# (ref ~lmap)
emap# (ref {})]
(fn [key#]
(or ((deref emap#) key#)
(let [lv# ((deref lmap#) key#)]
(when-not (nil? lv#)
(let [lve# (lv#)]
(dosync
(commute emap# assoc key# lve#)
; We dissoc the old value here to prevent a
space leak.
(commute lmap# dissoc key#))
lve#))))))
(recur r `(assoc ~lmap ~k (fn [] ~v))))))
Dave E
if you do (iterate inc 1) it will explode off of your REPL because it
goes for ever (the REPL automatically tries to get every element in
the returned list).
similarly doing (map (partial * 2) (iterate inc 1)) will explode off
of your REPL...
but doing (take 5 (map (partial * 2) (iterate inc 1))) will NOT force
you to leave the REPL because it will only run for the 5 elements you
requested from map. this is because map is already lazy!
however, it won't memoize your results unless you bind it to a
variable.
(def even-numbers
(map (partial * 2) (iterate inc 1)))
this will automatically memoize your numbers with no effort.
similarly, this map in a let statement will also do memoization.
try (take 5 even-numbers)
- dave
Chouser
>
> map is already lazy.
This was my first thought as well, but we've got a name space
collision here. mb is referring to map as in IPersistentMap, not the
map function. mb's lazy-map is very similar to what you would get if
you memoized a function that took one parameter and then went into a
big case statement. ...if Clojure had a case statement.
--Chouser
Dave E
On Jul 10, 10:43 am, Chouser <chou...@gmail.com> wrote:
Meikel Brandmeyer
I extended the implementation a bit. lazy-assoc and lazy-dissoc are also
available now. So for some use cases it should now be a simple drop-in
for the "normal" map. The rest of the interface like keys and merge and
such will (hopefully) follow soon.
The current version may be found at:
http://kotka.de/projects/clojure/lazy-map.html
Sincerely
Meikel
Chouser
Very interesting.
Have you considered implementing this as a Java class derived from
IPersistentMap? I think using proxy would be sufficient (no need for
gen-class) then users could use the existing assoc, dissoc, and
keyword-function API for you lazy-map, just as we do already for
hash-maps and sorted-maps.
Just a thought.
--Chouser
Meikel Brandmeyer
Am 12.07.2008 um 23:57 schrieb Chouser:
> Very interesting.
And yesterday I noticed, that it doesn't really help me
in my specific problem. Argghh...
> Have you considered implementing this as a Java class derived from
> IPersistentMap? I think using proxy would be sufficient (no need for
> gen-class) then users could use the existing assoc, dissoc, and
> keyword-function API for you lazy-map, just as we do already for
> hash-maps and sorted-maps.
Hmmm... I have no clue about Java whatsoever. I had a
short look at it ten years ago and decided that it looked like
C without dirty tricks. So Scheme, Smalltalk and OCaml
looked more interesting (read "different").
In general for your idea: I will have a look at it. If I can just
use proxy w/o droping to Java itself, I will probably try it.
However there are some issues. assoc for example has
to be a macro since it must not evaluate the value. So
there will be at least the lazy-map and lazy-assoc macros.
dissoc, keys, merge, ... they should all basically work.
Let me see...
Sincerely
Meikel
Meikel Brandmeyer
the proxy implementation is ready. The lazy-map may be used now
as a complete drop-in replacement for the normal map. The only
gotcha, I found up to now, is that merge doesn't work, yet. However
find, keys, assoc, dissoc, etc. all work as with the normal map.
Value are only evaluated on access! Eg. find does not evaluate
the value! Calling val on the resulting MapEntry does.
For assoc: of course this works as the usual assoc, ie. a normal,
evaluated value is associated with the map. To associate a lazy
value one has to use lazy-assoc. By their nature lazy-assoc and
lazy-map are macros. Hence no apply et al...
Currently the implementation relies on a "feature" of proxy, which
qualifies as Dark Voodoo or Black Magic.
(def m (proxy [I] [] (foo [] :bar)))
Suppose the interface I does not support foo. Then (.foo m) gives
an exception, but (((proxy-mappings m) 'foo) this) gives :bar. This
is used to leak information out of the closure for the lazy-assoc.
Otherwise we cannot easily transfer non-evaluated values to
other maps.
The current version may be found at:
http://kotka.de/projects/clojure/lazy-map.html
Sincerely
Meikel