Cross-referencing objects?

[Alan]

I've got a collection of unique objects, and I need to partition them
into sets. That part's easy enough, but I need to have both of the
following be efficient, and preferably easy:
- Given an object, determine what set it's in
- List all the objects in a given set

In an imperative language this would be fairly simple: create some
empty sets, then iterate over all objects; at each step add the object
to a set, and adjust the object's "parent" pointer to point at the set
it's in.

But in a functional, immutable context the circularity involved seems
to make this really inconvenient: if I create the set first then it
can't point to the object, and if I create the object first it can't
point at its set.

I could construct all the objects and have a single "global" map, with
mappings for both set-id=>[objects] and object=>set-id, but this seems
kinda gross and obscures what is actually meant (objects belong to
sets) with implementation (integers/keywords mapping to groups of
objects, and objects mapping to integers).

Likewise, I could use some kind of mutable refs in part of the
process, but (a) that feels like giving up, and (b) since I'll be
modifying these sets recursively and backtracking to "past" states it
would add a tremendous amount of bookkeeping to undo changes.

This seems like a pretty common problem, so I'm sure some clever
Clojure coder out there has already solved it; what am I missing?

[Saul Hazledine]

On Oct 3, 9:32 am, Alan <a...@malloys.org> wrote:
> I've got a collection of unique objects, and I need to partition them
> into sets. That part's easy enough, but I need to have both of the
> following be efficient, and preferably easy:
> - Given an object, determine what set it's in
> - List all the objects in a given set
>

I'm sure you'll get better answers later but this is the pseudo code
for what I would do.

1. Separate your objects into clojure sets. This makes it quick and
easy to list the objects in a given set.
2. To find out which set an object is in, do a get on each set until a
non nil return value is seen using (some #(% obj) [my-sets])

>
> I could construct all the objects and have a single "global" map, with
> mappings for both set-id=>[objects] and object=>set-id, but this seems
> kinda gross and obscures what is actually meant (objects belong to
> sets) with implementation (integers/keywords mapping to groups of
> objects, and objects mapping to integers).
>

3. Only the mapping, object => set, is needed and, as you say, this is
an implementation detail that should be hidden. So memoize step 2 for
performance. You get a global map but it doesn't clutter your code.

Saul

[André Thieme]

Am 03.10.2010 09:32, schrieb Alan:
> I've got a collection of unique objects, and I need to partition them
> into sets. That part's easy enough, but I need to have both of the
> following be efficient, and preferably easy:
> - Given an object, determine what set it's in
> - List all the objects in a given set
>
> In an imperative language this would be fairly simple: create some
> empty sets, then iterate over all objects; at each step add the object
> to a set, and adjust the object's "parent" pointer to point at the set
> it's in.
>
> But in a functional, immutable context the circularity involved seems
> to make this really inconvenient: if I create the set first then it
> can't point to the object, and if I create the object first it can't
> point at its set.

You could use mutable objects:
>
http://download.oracle.com/javase/6/docs/api/java/util/package-summary.html

[Mike Meyer]

On Sun, 3 Oct 2010 00:32:16 -0700 (PDT)
Alan <al...@malloys.org> wrote:

> I've got a collection of unique objects, and I need to partition them
> into sets. That part's easy enough, but I need to have both of the
> following be efficient, and preferably easy:
> - Given an object, determine what set it's in
> - List all the objects in a given set
>

> I could construct all the objects and have a single "global" map, with
> mappings for both set-id=>[objects] and object=>set-id, but this seems
> kinda gross and obscures what is actually meant (objects belong to
> sets) with implementation (integers/keywords mapping to groups of
> objects, and objects mapping to integers).

That's the right idea, but it's overkill. You only need to provide
indirection for one direction, not both. For the other direction, you
can use the items directly. Chance are either objects or sets of them
have a natural "name" you can use for the id.

If the sets have the natural ids, then you should be able to write a
function create-object that creates a map representing an object,
including a :set key that is the id of the set it belongs to. Finally,
given (source) that produces a list vectors of features for each
object, you do:

(def set-map (group-by :set (map create-object (source))))

Given an object, you can get the set with (set-map (:set object)).
Given a set - it is a list of objects.

If the objects have the natural id - that's an exercise for the
reader.

<mike
--
Mike Meyer <m...@mired.org> http://www.mired.org/consulting.html
Independent Network/Unix/Perforce consultant, email for more information.

O< ascii ribbon campaign - stop html mail - www.asciiribbon.org

[David Nolen]

This is a topic that comes up periodically. I've wondered this myself and recently realized that clojure.set does deal with some of these issues.

(ns db

  (:use clojure.set))

(def animals #{{:name "penguin" :type "bird"}

               {:name "dolphin" :type "mammal"}

               {:name "lion" :type "mammal"}

               {:name "ant" :type "insect"}})

;; group the animals into sets

(def by-type (index animals [:type]))

;; get all birds who's first name start with the character 'p'

(select (fn [{[c] :name}] (= c \p))

        (by-type {:type "bird"}))

Is something about this that doesn't work for your problem?

[ka]

@Alan

I'm trying to understand why you find the solution you gave "gross"

> I could construct all the objects and have a single "global" map, with
> mappings for both set-id=>[objects] and object=>set-id, but this seems
> kinda gross and obscures what is actually meant (objects belong to
> sets) with implementation (integers/keywords mapping to groups of
> objects, and objects mapping to integers).

But you say:

> In an imperative language this would be fairly simple: create some
> empty sets, then iterate over all objects; at each step add the object
> to a set, and adjust the object's "parent" pointer to point at the set
> it's in.

Aren't these two same?

add object to a set _v/s_ set-id => #{objects}
adjust the object's "parent" pointer _v/s_ object => set-id

Only differences for me are:
1. In the imperative case you don't have to create a 'set-id'. But
'set-id' would naturally come from the way you're partitioning in the
first place.
2. In the functional case you don't have to create a parent pointer
inside the object (which looks ugly to me - what is object's business
to know where it is lying? Tomorrow if you put the object in a second
set, will you add a parent2 or create a parents array or perhaps a map
of parent-id to parent itself).

Note that I may be totally misplaced or missing several things - just
trying to understand.