Showing posts with label maps. Show all posts
Showing posts with label maps. Show all posts

Tuesday, August 23, 2011

Clojure: partition-by, split-with, group-by, and juxt

Today I ran into a common situation: I needed to split a list into 2 sublists - elements that passed a predicate and elements that failed a predicate. I'm sure I've run into this problem several times, but it's been awhile and I'd forgotten what options were available to me. A quick look at http://clojure.github.com/clojure/ reveals several potential functions: partition-by, split-with, and group-by.

partition-by
From the docs:
Usage: (partition-by f coll)

Applies f to each value in coll, splitting it each time f returns
a new value. Returns a lazy seq of partitions.
Let's assume we have a collection of ints and we want to split them into a list of evens and a list of odds. The following REPL session shows the result of calling partition-by with our list of ints.
user=> (partition-by even? [1 2 4 3 5 6])

((1) (2 4) (3 5) (6))
The partition-by function works as described; unfortunately, it's not exactly what I'm looking for. I need a function that returns ((1 3 5) (2 4 6)).

split-with
From the docs:
Usage: (split-with pred coll)

Returns a vector of [(take-while pred coll) (drop-while pred coll)]
The split-with function sounds promising, but a quick REPL session shows it's not what we're looking for.
user=> (split-with even? [1 2 4 3 5 6])

[() (1 2 4 3 5 6)]
As the docs state, the collection is split on the first item that fails the predicate - (even? 1).

group-by
From the docs:
Usage: (group-by f coll)

Returns a map of the elements of coll keyed by the result of f on each element. The value at each key will be a vector of the corresponding elements, in the order they appeared in coll.
The group-by function works, but it gives us a bit more than we're looking for.
user=> (group-by even? [1 2 4 3 5 6])

{false [1 3 5], true [2 4 6]}
The result as a map isn't exactly what we desire, but using a bit of destructuring allows us to grab the values we're looking for.
user=> (let [{evens true odds false} (group-by even? [1 2 4 3 5 6])]

[evens odds])
[[2 4 6] [1 3 5]]
The group-by results mixed with destructuring do the trick, but there's another option.

juxt
From the docs:
Usage: (juxt f)
              (juxt f g)
              (juxt f g h)
              (juxt f g h & fs)

Alpha - name subject to change.
Takes a set of functions and returns a fn that is the juxtaposition
of those fns. The returned fn takes a variable number of args, and
returns a vector containing the result of applying each fn to the
args (left-to-right).
((juxt a b c) x) => [(a x) (b x) (c x)]
The first time I ran into juxt I found it a bit intimidating. I couldn't tell you why, but if you feel the same way - don't feel bad. It turns out, juxt is exactly what we're looking for. The following REPL session shows how to combine juxt with filter and remove to produce the desired results.
user=> ((juxt filter remove) even? [1 2 4 3 5 6])

[(2 4 6) (1 3 5)]
There's one catch to using juxt in this way, the entire list is processed with filter and remove. In general this is acceptable; however, it's something worth considering when writing performance sensitive code.

Saturday, August 20, 2011

Clojure: Apply a Function To Each Value of a Map

I recently needed to update all of the values of map, and couldn't find an individual function in clojure.core that did the trick. Luckily, implementing an update-values function is actually very straightforward. The following function reduces the original map to a new map with the same elements, except the values are all the result of applying the specified function and any additional args.
(defn update-values [m f & args]

(reduce (fn [r [k v]] (assoc r k (apply f v args))) {} m))
The code is concise, but perhaps a bit terse. Still, it does the trick, as the REPL session below demonstrates.
Clojure 1.2.0

user=> (defn update-values [m f & args]
(reduce (fn [r [k v]] (assoc r k (apply f v args))) {} m))
#'user/update-values
user=> (update-values {:a 1 :b 2 :c 3} inc)
{:c 4, :b 3, :a 2}
user=> (update-values {:a 1 :b 2 :c 3} + 10)
{:c 13, :b 12, :a 11}
user=> (update-values {:a {:z 1} :b {:z 1} :c {:z 1}} dissoc :z)
{:c {}, :b {}, :a {}}
The last example is the specific problem I was looking to solve: remove a key-value pair from all the values of a map. However, the map I was working with actually had a bit of nesting. Let's define an example map that is similar to what I was actually working with.
user=> (def data {:boxes {"jay" {:linux 2 :win 1} "mike" {:linux 2 :win 2}}})

#'user/data
Easy enough, I have 2 linux boxes and 1 windows box, and Mike has 2 linux and 2 windows. But, now the company decides to discard all of our windows boxes, and we'll need to update each user. A quick combo of update-in with update-values does the trick.
user=> (update-in data [:boxes] update-values dissoc :win)

{:boxes {"mike" {:linux 2}, "jay" {:linux 2}}}
As you can see, the update-values function plays nice with existing Clojure functions as well.

Disclosure: I am long AAPL and own every device Apple puts out. Don't take my example numbers to literally. Also, much to my dismay, DRW has yet to discard all of our windows boxes.

Wednesday, May 04, 2011

Clojure: Get All Nested Map Values (N levels deep)

I recently needed to pull all the values from a nested map. The map I was working with was designed to give easy access to data like so (formatted):
user=>
(def my-data {"Jay"
{"clojure"
{:name "Jay", :language "clojure", :enjoys true},
"ruby"
{:name "Jay", :language "ruby", :enjoys true}}
"Jon"
{"java"
{:name "Jon", :language "java", :enjoys true}}} )
#'user/my-data
user=> (get-in my-data ["Jon" "java"])
{:name "Jon", :language "java", :enjoys true}
user=> (get-in my-data ["Jay" "ruby"])
{:name "Jay", :language "ruby", :enjoys true}
This worked for all of the ways the data was accessed, until someone asked for a list of all people and all languages.

I needed a function that grabbed all the values nested to a point in the map (grabbing only the values instead of the deepest map wouldn't have provided valuable information). I created the following function that should grab all the values up to the nesting level specified.
(defn nth-vals* [a i m]
(if (and (map? m) (> i 0))
(reduce into a (map (fn [v] (nth-vals* a (dec i) v)) (vals m)))
(conj a m)))

(defn nth-vals [i m]
(if (nil? m)
{}
(nth-vals* [] i m)))
The nth-vals function can be used as the following example shows. (assuming the same map for my-data) (formatted)
user=> (nth-vals 2 my-data)
[{:name "Jay", :language "clojure", :enjoys true}
{:name "Jay", :language "ruby", :enjoys true}
{:name "Jon", :language "java", :enjoys true}]
For reference, here's what's returned if we reduce the map all the way to it's values.
user=> (nth-vals 3 my-data)
["Jay" "clojure" true "Jay" "ruby" true "Jon" "java" true]
That list of values may be helpful for someone else, but it wouldn't have solved our current problem.

And, if you're interested, here's what's returned if you ask for 1 level deep of values. (formatted, again)
user=> (nth-vals 1 my-data)
[{"clojure" {:name "Jay", :language "clojure", :enjoys true},
"ruby" {:name "Jay", :language "ruby", :enjoys true}}
{"java" {:name "Jon", :language "java", :enjoys true}}]
I wouldn't at all be surprised if something like this already exists in Clojure core, but I haven't found it yet.

Monday, May 02, 2011

Clojure: Converting a Java Object to a Clojure Map

Clojure has a great library that helps facilitate most things you'd want to do, but it's also easy to roll your own solution if you need something more specific. This blog entry is about converting an object to a map, something Clojure already has a function for: bean. From the docs:
Takes a Java object and returns a read-only implementation of the
map abstraction based upon its JavaBean properties.
The bean function is easy enough to use, as the following example shows (formatted for readability).
user=> (import 'java.util.Calendar)
java.util.Calendar
user=> (-> (Calendar/getInstance) .getTime bean)
{:seconds 16,
:date 2,
:class java.util.Date,
:minutes 35,
:hours 12,
:year 111,
:timezoneOffset 240,
:month 4,
:day 1,
:time 1304354116038}
The bean function is simple and solves 99% of the problems I encounter. Generally I'm destructuring a value that I pull from a map that was just created from an object; bean works perfectly for this.

However, I have run across two cases where I needed something more specialized.

The first case involved processing a large amount of data in a very timely fashion. We found that garbage collection pauses were slowing us down too much, and beaning the objects that were coming in was causing a large portion of the garbage. Since we were only dealing with one type of object we ended up writing something specific that only grabbed the fields we cared about.

The second case involved working with less friendly Java objects that needed to be converted to maps that were going to be used many times throughout the system. In general it isn't a big deal working with ugly Java objects. You can destructure the map into nice var names, or you can use the rename-keys function if you plan on using the map more than once. This probably would have worked for me, but I had an additional requirement. The particular Java objects I was working with had many methods/fields and the maps contained about 80% more information than I needed. So, I could have used bean, then rename keys, then dissoc. But, this felt similar enough to the situation in the past where I was working with specific method names and I thought I'd look for a more general solution.

The following example shows the definition of obj->map and the REPL output of using it.
user=> (import 'java.util.Date)
java.util.Date
user=> (defmacro obj->map [o & bindings]
(let [s (gensym "local")]
`(let [~s ~o]
~(->> (partition 2 bindings)
(map (fn [[k v]]
(if (vector? v)
[k (list (last v) (list (first v) s))]
[k (list v s)])))
(into {})))))
#'user/obj->map
user=> (obj->map (Date. 2012 1 31)
:month .getMonth
:year [.getYear #(* 2 %)]
:day .getDate)
{:month 2, :year 4024, :day 2}
As you can see from the output, the macro grabs the values of the methods you specify and stores them in a map. At one point I also needed to do a bit of massaging of a value, so I included the ability to use a vector to specify the method you care about and a function to apply to the value (the result of the function will become the value). In the example, you can see that the :year is double the value of what .getYear returns.

In general you should stick with bean, but if you need something more discriminating, obj->map might work for you.

Wednesday, January 05, 2011

Clojure: select-keys, select-values, and apply-values

Clojure provides the get and get-in functions for returning values from a map and the select-keys function for returning a new map of only the specified keys. Clojure doesn't provide a function that returns a list of values; however, it's very easy to create such a function (which I call select-values). Once you have the ability to select-values it becomes very easy to create a function that applies a function to the selected values (which I call apply-values).

The select-keys function returns a map containing only the entries of the specified keys. The following (pasted) REPL session shows a few different select-keys behaviors.
user=> (select-keys {:a 1 :b 2} [:a])   
{:a 1}
user=> (select-keys {:a 1 :b 2} [:a :b])
{:b 2, :a 1}
user=> (select-keys {:a 1 :b 2} [:a :b :c])
{:b 2, :a 1}
user=> (select-keys {:a 1 :b 2} [])
{}
user=> (select-keys {:a 1 :b 2} nil)
{}
The select-keys function is helpful in many occassions; however, sometimes you only care about selecting the values of certain keys in a map. A simple solution is to call select-keys and then vals. Below you can find the results of applying this idea.
user=> (def select-values (comp vals select-keys))
#'user/select-values
user=> (select-values {:a 1 :b 2} [:a])
(1)
user=> (select-values {:a 1 :b 2} [:a :b])
(2 1)
user=> (select-values {:a 1 :b 2} [:a :b :c])
(2 1)
user=> (select-values {:a 1 :b 2} [])
nil
user=> (select-values {:a 1 :b 2} nil)
nil
The select-values implementation from above may be sufficient for what you are doing, but there are two things worth noticing: in cases where you might be expecting an empty list you are seeing nil; and, the values are not in the same order that the keys were specified in. Given that (standard) maps are unsorted, you can't be sure of the ordering the values.

(side-note: If you are concerned with microseconds, it's also been reported that select-keys is a bit slow/garbage heavy.)

An alternative definition of select-values uses the reduce function and pulls the values by key and incrementally builds the (vector) result.
user=> (defn select-values [map ks]
(reduce #(conj %1 (map %2)) [] ks))
#'user/select-values
user=> (select-values {:a 1 :b 2} [:a])
[1]
user=> (select-values {:a 1 :b 2} [:a :b])
[1 2]
user=> (select-values {:a 1 :b 2} [:a :b :c])
[1 2 nil]
user=> (select-values {:a 1 :b 2} [])
[]
user=> (select-values {:a 1 :b 2} nil)
[]
The new select-values function returns the values in order and returns an empty vector in the cases where previous examples returned nil, but we have a new problem: Keys specified that don't exist in the map are now included in the vector as nil. This issue is easily addressed by adding a call to the remove function.

The implementation that includes removing nils can be found below.
user=> (defn select-values [map ks]
(remove nil? (reduce #(conj %1 (map %2)) [] ks)))
#'user/select-values
user=> (select-values {:a 1 :b 2} [:a])
(1)
user=> (select-values {:a 1 :b 2} [:a :b])
(1 2)
user=> (select-values {:a 1 :b 2} [:a :b :c])
(1 2)
user=> (select-values {:a 1 :b 2} [])
()
user=> (select-values {:a 1 :b 2} nil)
()
There is no "correct" implementation for select-values. If you don't care about ordering and nil is a reasonable return value: the first implementation is the correct choice due to it's concise definition. If you do care about ordering and performance: the second implementation might be the right choice. If you want something that follows the principle of least surprise: the third implementation is probably the right choice. You'll have to decide what's best for your context. In fact, here's a few more implementations that might be better based on your context.
user=> (defn select-values [m ks] 
(map m ks))
#'user/select-values
user=> (select-values {:a 1 :b 2} [:a])
(1)
user=> (select-values {:a 1 :b 2} [:a :b :c])
(1 2 nil)
user=> (defn select-values [m ks]
(reduce #(if-let [v (m %2)] (conj %1 v) %1) [] ks))
#'user/select-values
user=> (select-values {:a 1 :b 2} [:a])
[1]
user=> (select-values {:a 1 :b 2} [:a :b :c])
[1 2]
Pulling values from a map is helpful, but it's generally not the end goal. If you find yourself pulling values from a map, it's likely that you're going to want to apply a function to the extracted values. With that in mind, I generally define an apply-values function that returns the result of applying a function to the values returned from specified keys.

A good example of this is returning the total for a line item represented as a map. Given a map that specifies a line item costing $5 and having a quantity of 4, you can use (* price quantity) to determine the total price for the line item.

Using our previously defined select-values function we can do the work ourselves, as the example below shows.
user=> (let [[price quantity] (select-values {:price 5 :quantity 4 :upc 1123} [:price :quantity])]                          
(* price quantity))
20
The example above works perfectly well; however, applying a function to the values of a map seems like a fairly generic operation that can easily be extracted to it's own function (the apply-values function). The example below shows the definition and usage of my definition of apply-values.
user=> (defn apply-values [map f & ks]          
(apply f (select-values map ks)))
#'user/apply-values
user=> (apply-values {:price 5 :quantity 4 :upc 1123} * :price :quantity)
20
I find select-keys, select-values, & apply-values to be helpful when writing Clojure applications. If you find you need these functions, feel free to use them in your own code. However, you'll probably want to check the comments - I'm sure someone with more Clojure experience than I have will provide superior implementations.

Monday, August 30, 2010

Clojure: Using Sets and Maps as Functions

Clojure sets and maps are functions.

Since they are functions, you don't need functions to get values out of them. You can use the map or set as the example below shows.
(#{1 2} 1)
> 1

({:a 2 :b 3} :a)
> 2
That's nice, but it's not exactly game changing. However, when you use sets or maps with high order functions you can get a lot of power with a little code.

For example, the following code removes all of the elements of a vector if the element is also in the set.
(def banned #{"Steve" "Michael"})
(def guest-list ["Brian" "Josh" "Steve"])

(remove banned guest-list)
> ("Brian" "Josh")
I'm a big fan of using sets in the way described above, but I don't often find myself using maps in the same way. The following code works, but I rarely use maps as predicates.
(def banned {"Steve" [] "Michael" []})
(def guest-list ["Brian" "Josh" "Steve"])

(remove banned guest-list)
> ("Brian" "Josh")
However, yesterday I needed to compare two maps and get the list of ids in the second map where the quantities didn't match the quantities in the first map. I started by using filter and defining a function that checks if the quantities are not equal. The following code shows solving the problem with that approach.
; key/value pairs representing order-id and order-quantity
(def map1 {1 44 2 33})
(def map2 {1 55 2 33})

(defn not=quantities [[id qty]] (not= (map1 id) qty))
(keys (filter not=quantities map2))
> (1)
However, since you can use maps as filter functions you can also solve the problem by merging the maps with not= and filtering by the result. The following code shows an example of merging and using the result as the predicate.
; key/value pairs representing order-id and order-quantity
(def map1 {1 44 2 33})
(def map2 {1 55 2 33})

(filter (merge-with not= map1 map2) (keys map2))
> (1)
I don't often find myself using maps as predicates, but in certain cases it's exactly what I need.