sorted by walk
Timothy Pratley
I noticed that clojure.walk does not support sorted-map-by and
sorted-set-by, but thanks to a recent change:
http://www.assembla.com/spaces/clojure/tickets/128
It can now. I asked Stuart about it and he said someone had contacted
him about it but it seems they never raised a ticket (at least I can't
find it).
Attached is a quick fix patch if desired, may I open a ticket for this?
Also the tests for walk don't appear to have been brought over from
contrib. Would it be ok for me to include bringing them over in the
same ticket, or I can create 2 separate if desired. [I'll make a
separate one for the contrib removal naturally.] I'll add some tests
for sorted-by walks.
Just thought I'd check in here first in case this would be stepping on
anyones toes.
Regards,
Tim.
Sean Devlin
A sort-by walk does sound cool, and bringing over the tests is a good
idea. :)
The walk fn cold have written walk this way for a while, though. What
#128 lets you do (I fixed it) is use empty with a sorted collections.
A lot of these use cases should read:
(outer (into (empty form) (map inner form))
In fact, I think the cond should now read like this:
Granted, at this point walk looks like a less general version of two
other ideas on this list...
http://fulldisclojure.blogspot.com/2010/01/12-fn-proposal-same-multisame.html
http://fulldisclojure.blogspot.com/2009/11/rfc-feedback-for-visitor-closure.html
> sorted_walk.diff
> 3KViewDownload
Stuart Sierra
> The walk fn cold have written walk this way for a while, though.
Yes. I just didn't get around to it.
> A lot of these use cases should read:
>
> (outer (into (empty form) (map inner form))
That doesn't work with lists, because they conj on the front. You end
up with the reverse of what you started with. Also, map entries have
to be handled specially or as vectors.
The following works:
(defn walk [inner outer form]
(cond
(list? form) (outer (apply list (map inner form)))
(instance? clojure.lang.IMapEntry form) (outer (vec (map inner
form)))
(seq? form) (outer (doall (map inner form)))
(coll? form) (outer (into (empty form) (map inner form)))
:else (outer form)))
But this could also be written more efficiently with protocols.
-SS
Timothy Pratley
http://www.assembla.com/spaces/clojure/tickets/244-walk-support-for-sorted-by-collections
which is ready for inclusion.
I also have some questions about walk...
My first impression is that walk is a 'map' operation that returns the
same type instead of a seq, is that the idea?
My second impression is that walking over a hash-map is tedious
because there is no nice builtin to 'update' a mapentry
#(update-in % [1] inc) kind of works but seems ugly. Granted this is
the same as for map, I've just never mapped over a hash-map before it
seems... but maybe the walk namespace would benefit from (update-val)
(update-key)?
And my third impression is that I can't think of a reason to ever
supply an 'outer' function...
In the tests the only thing I could think of that made any sense to me
was a reduce, which completely removes the point of walking over
mapping in the first place:
+ (is (= (w/walk #(update-in % [1] inc) #(reduce + (vals %)) c)
+ (reduce + (map (comp inc val) c))))
+ (is (= (w/walk inc #(reduce + %) c)
+ (reduce + (map inc c)))))
I can only ever think of passing identity, but I think I'm missing
some important point in all this.
Would it make sense to have (walk inner form) as well as (walk inner
outer form)?
Regards,
Tim.
Sean Devlin
I'l take a stab at these points. I'll start with issues 2 & 3.
For issue 2, I'm assuming you are simply mapping over a map. This is
easily enough done when you use the right mapping operation. Remember
that you mapping fn has to take 2 entries in, and return a two element
vector. I have 2 utility hofs I use for this purpose.
(defn key-entry
[f] (fn [[k v]] [(f k) v]))
(defn val-entry
[f] (fn [[k v]] [k (f v)]))
As to your third point, outer fns are very useful when manipulating
keywords/symbols like strings. The pattern
(keyword (some-fn (name k)))
where some-fn is a string fn is useful. Well, this isn't quite the
identical case as walk. Still, it shows how outer fns can be useful.
As to your first point, the short answer is yes. However, I'm going
to take this chance to re-raise an issue.
I've purposed a more versatile version of walk, same. Here's how to
write walk in terms of my fn, same
(defn walk
[inner outer form])
(outer (same map inner form)))
My fn same has the advantage of working with EVERY SINGLE SEQUENCE
FN. All of them.
Since my last post, I've addressed the following issues w/ same
* Wrote same as a protocol
* same doesn't reverses lists anymore
* same works on MapEntry objects, too
Could somebody take a look at my latest proposal? Please?
http://github.com/francoisdevlin/devlinsf-clojure-utils/blob/master/src/lib/sfd/same.clj
Thanks,
Sean
PS - I use same in this video:
On Jan 27, 6:52 pm, Timothy Pratley <timothyprat...@gmail.com> wrote:
> I've uploaded a patch with fix and test coverage tohttp://www.assembla.com/spaces/clojure/tickets/244-walk-support-for-s...
Timothy Pratley
2010/1/28 Sean Devlin <francoi...@gmail.com>:
> Could somebody take a look at my latest proposal? Please?
I can see the appeal of "same" on its own for things like:
(same take 2 "foobar")
=> "fo"
Unexpectedly for walk the 'same' version you proposed appears to be slower:
user=> (time (dotimes [i 10000] (walk2 inc identity '(1 2 3 4 5 6 7))))
"Elapsed time: 68.287662 msecs"
user=> (time (dotimes [i 10000] (walk inc identity '(1 2 3 4 5 6 7))))
"Elapsed time: 22.009291 msecs"
Perhaps there are some optimizations that can improve it?
Microbenchmarking is evil disclaimer attached.
Regarding key-entry and val-entry, I wonder if fkey and fval would be
better names?
Regards,
Tim.
Stuart Sierra
-SS
On Jan 12, 4:01 am, Timothy Pratley <timothyprat...@gmail.com> wrote:
> sorted_walk.diff
> 3KViewDownload
Sean Devlin
Why?
--
You received this message because you are subscribed to the Google Groups "Clojure Dev" group.
To post to this group, send email to cloju...@googlegroups.com.
To unsubscribe from this group, send email to clojure-dev...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/clojure-dev?hl=en.
Stuart Sierra
> Okay, wow.
>
> Why?
It's a hack that I scribbled up ages ago. It doesn't have much
general utility. It only got promoted into core, prematurely, as part
of the testing integration.
-SS
Sean Devlin
You're totally right, my version was slower. I did a few things to
speed it up.
* Removed the option to specify the argument. Now same matches on the
last argument every time. Nobody seemed to like that feature anyway.
* You notice how Rich "repeats himself" when defining things like
partial? It has for signatures when conceptually it needs only one?
Well, it turns out that using arity overloading this way really does
speed up the code a lot.
When it's all said & done, I was able to get about a 2.5-3x speed up.
multi-same had the same improvements made, and it also saw a
significant cleanup.
Thanks for pointing this out.
Sean
On Jan 28, 2:58 am, Timothy Pratley <timothyprat...@gmail.com> wrote:
> Hi Sean,
>
> 2010/1/28 Sean Devlin <francoisdev...@gmail.com>:
Sean Devlin
user=> (time (dotimes [i 100000] (same take 2 [\a \b \c \d])))
"Elapsed time: 159.167 msecs"
user=> (time (dotimes [i 100000] (into [] (take 2 [\a \b \c \d]))))
"Elapsed time: 140.893 msecs"
We're looking at about a 12-15% speed hit compared to the "by hand"
version. I think this is good enough performance.
Timothy Pratley
> When it's all said & done, I was able to get about a 2.5-3x speed up.
Awesome!
2010/1/29 Stuart Sierra <the.stua...@gmail.com>:
> clojure.walk just needs to die.
Yikes, just when I thought I was getting the hang of it. I apologize
if my fumbling has precipitated this feeling. FWIW my questions were
out of interest in the library, not intended as criticisms.
Regards,
Tim.