On Mon, Mar 14, 2011 at 3:49 AM, Ken Wesson <kwess...@gmail.com> wrote:
>> Well, except that count and empty are broken for some reason:
>>
>> user=> (.count (Bag. {} 0))
>> 0
>> user=> (count (Bag. {} 0))
>> 1
>>
>> I don't understand what's causing this, but empty bags are always
>> returning a count of 1 (and false from empty?) although the .count
>> method correctly returns zero. I've traced the problem as far as the
>> Java method clojure.lang.RT/count but no farther at this time.
>
> Argh. This same bug causes union to blow up in the case of (union (bag
> 1) (bag)). It works with (union #{1} #{}), by contrast. It traces back
> to empty? wrongly returning true, and thus to count wrongly returning
> 1 even though .count correctly returns 0.
Simply adding "clojure.lang.Counted", without any methods, to the
protocol list makes it work again. The count function in RT is this
odd little thing:
public static int count(Object o){
if(o instanceof Counted)
return ((Counted) o).count();
return countFrom(Util.ret1(o, o = null));
}
If it's not counted, countFrom is called, and for some reason does not
work on empty Bags even though it apparently works correctly on, among
others, empty LazySeqs:
user=> (instance? clojure.lang.Counted (map + '()))
false
user=> (count (map + '()))
0
Taking the countFrom expression apart, Util.ret1 just seems to return
its first argument. I suppose it's being used to null o before
countFrom does all of its work, to avoid holding onto the head of a
lazy sequence that gets passed in. It's not the source of the problem.
The cause seems to be this in countFrom:
else if(o instanceof IPersistentCollection) {
ISeq s = seq(o);
o = null;
int i = 0;
for(; s != null; s = s.next()) {
if(s instanceof Counted)
return i + s.count();
i++;
}
return i;
}
If "o instanceof IPersistentCollection" then o has a .count method,
yet this doesn't call it. Instead it calls seq, and if seq returns a
non-null, empty seq that loop returns 1 instead of 0. So another fix
that could be made to the original bag would be to call seq on the
return value of mapcat. (Why mapcat is not returning nil for an empty
input seq is itself somewhat mysterious.) I'm not sure whether the
loop above should be considered correct (seq should never return a
non-nil, empty seq) or incorrect (the corner case of seq's return
being empty but not null should be handled). I'm not even sure whether
that loop should exist at all, or should instead call the .count
method of IPersistentCollection (with the default implementation being
the loop above, of course). If the .count method of
IPersistentCollection is not going to be used, on the other hand,
unless the thing is also a Counted, then it should be removed from the
former interface.
Regardless, it looks like (count a-bag) is going to be inefficient
despite the .count method implementation unless the Counted type is
added to the protocol list, and seq should probably be returning nil
for empty bags.
So the version I'd suggest using is:
(deftype Bag [m c]
clojure.lang.IObj
(withMeta [this, mtd]
(Bag. (with-meta m mtd) c))
(meta [this] (meta m))
clojure.lang.IPersistentCollection
(count [this] c)
(empty [this] (Bag. {} 0))
(equiv [this other] (= (seq this) other))
(seq [this]
(seq
(mapcat
(fn [[k v]]
(repeat v k))
m)))
(cons [this obj]
(Bag. (merge-with + m {obj 1}) (inc c)))
SetOps
(disjoin* [this obj]
(if-let [n (m obj)]
(if (= 1 n)
(Bag. (dissoc m obj) (dec c))
(Bag. (assoc m obj (dec n)) (dec c)))
this))
(has* [this obj] (contains? m obj))
(total [this obj] (m obj 0))
(counts [this] m)
clojure.lang.Counted
Object
(toString [this]
(apply str
(interpose " "
(seq this)))))
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
