positions

[nchubrich]

Is this function part of the API or any contrib? I couldn't find it:

(defn positions [pred coll]
(loop [coll coll i 0 accum []]
(if (empty? coll) accum
(if (pred (first coll))
(recur (rest coll) (inc i) (conj accum i))
(recur (rest coll) (inc i) accum)))))

[Sean Devlin]

Try clojure.contrib.seq-utils :)

As a learning exercise, I'd recommend re-writing it to be lazy. Your
version is eager because it uses loop. In order to make it lazy,
you'd want to construct a lazy-seq. See the macro w/ the same name.

Another choice is to use built-in functions, like this:

(defn positions [pred coll]
(map second
(filter (comp pred first)
(map vector coll (iterate inc 0)))))

Hope this helps,
Sean

[nchubrich]

Thanks Sean, I'll do the exercise. I don't know how I missed it in
seq-utils.
After months of programming Clojure, I realize how much I still
have to learn.
(Knowledge is power; knowledge of lack of knowledge is power to
power.)

Nick.

[John Harrop]

On Thu, Nov 19, 2009 at 1:23 PM, Sean Devlin <francoi...@gmail.com> wrote:

Try clojure.contrib.seq-utils :)

As a learning exercise, I'd recommend re-writing it to be lazy.  Your
version is eager because it uses loop.  In order to make it lazy,
you'd want to construct a lazy-seq.  See the macro w/ the same name.

Another choice is to use built-in functions, like this:

(defn positions [pred coll]
 (map second
   (filter (comp pred first)
     (map vector coll (iterate inc 0))))) 

(defn indexed [coll]

  (map vector (iterate inc 0) coll))

(defn positions [pred coll]

  (for [[i e] (indexed coll) :when (pred e)] i))

Seems to work:

user=> (positions even? [1 1 2 9 3 4 8 7 6])

(2 5 6 8)

(yes, I know there's already an "indexed" with similar semantics in clojure.contrib.)

[nchubrich]

While we're on the topic, where is something like (subtract [1 2 3 3 4
4 5 6] evens) -> (1 3 3 5)? Doesn't seem to be in seq-utils or API.
Seems like there should be a parallel "multiset" library for colls, to
clojure.set. (I guess there could be two versions of subtract, one
that removes \all, and one that removes only as many as are in the
subtracted set.) Maybe I will write this unless there is already some
such out there.

[ajuc]

Did you mean remove? It's in core.

(user=> (remove even? [1 2 3 3 4 5 6])
(1 3 3 5)


.

[Alex Osborne]

and note that you can use a set as the predicate:

(remove #{2 3 5} [1 2 3 4 5 6 7])
=> (1 4 6 7)

So if you wanted to "subtract" two vectors:

(remove (set [2 3 5]) [1 2 3 4 5 6 7])
=> (1 4 6 7)

Doing it "multiset" style (removing only as many as are in the
subtracted set) might require some more thought though, it might be more
efficient to use a hash map representation for your multiset and then do:

(merge-with - {:a 2, :b 1} {:a 1, :b 1})
=> {:a 0 :b 1}

That doesn't remove "zero" values though, which may or may not be a good
thing depending on exactly how you want to use it.

[nchubrich]

Yeah, remove will work for one kind of 'multiset' operator I am
thinking of. The others might as well preserve as much order as
possible. For instance, (add [1 2 3 4] [1 2 3 4]) could have two
interpretations; you just append, or you add like elements to
positions of like elements, so you get [1 1 2 2 3 3 4 4]. I guess you
could specify that with a flag :append vs. :match.
I'd also have a flag to choose eager evaluation vs. lazy (sometimes
it's nice to preserve the collection type, and you don't need lazy
evaluation for collections.). The "native" multiset type could be the
map type you suggested, and that would be used to determine equality.

[Sean Devlin]

That's why there are two separate functions do do what you suggest

user=>(interleave [1 2 3 4] [1 2 3 4])
(1 1 2 2 3 3 4 4)

user=> (concat [1 2 3 4] [1 2 3 4])
(1 2 3 4 1 2 3 4)

There's also the doall function to override lazyness.

[John Harrop]

On Thu, Nov 19, 2009 at 7:00 PM, Sean Devlin <francoi...@gmail.com> wrote:

That's why there are two separate functions do do what you suggest

user=>(interleave [1 2 3 4] [1 2 3 4])
(1 1 2 2 3 3 4 4)

user=> (concat [1 2 3 4] [1 2 3 4])
(1 2 3 4 1 2 3 4)

Poor choice of example. I think he meant even if he has e.g.

(keep-likes-with-likes-interleave [1 2 3 4 5 6 7] [3 2 7])

he wants

[1 2 2 3 3 4 5 6 7 7]

rather than

(1 3 2 2 3 7)

which is what core interleave gets you.

[Alex Osborne]

This is just (sort (concat [1 2 3 4 5 6 7] [3 2 7])) though.

[John Harrop]

I think he also wants the original order of the first input coll to be preserved, though. Sort wouldn't do that. 

[Alex Osborne]

John Harrop wrote:
> This is just (sort (concat [1 2 3 4 5 6 7] [3 2 7])) though.
>
>
> I think he also wants the original order of the first input coll to be
> preserved, though. Sort wouldn't do that.

Hmmm.. that's a pretty weird set of requirements. Usually a
multiset/bag is unordered. What happens if same elements aren't grouped
together in the first input coll it, it just arbitrarily picks one of
their positions and moves them all together there? :-)

If you're going to go to the trouble of making special multiset
functions you may as well create a new multiset collection type that
does the "right thing" when you conj to it and such. It is also means
you can store things in a way that allows efficient implementation of
the operations, instead of just hoping the library user passes data in
the right order or using slow but safe n^2 or n log n algorithms everywhere.

[John Harrop]

I don't disagree. We'll have to wait for the original poster to clarify his requirements. 

[Alex Burka]

Yesterday I need a similar function (interleave, but don't stop when
the shortest seq ends), so I wrote it. I subsequently refactored the
program and didn't need it anymore, but here it is anyway. It could
probably be written more succinctly, but I followed the implementation
of core/interleave.

(defn interleave-all
"Like interleave, but stops when the longest seq is done, instead of
the shortest."
([c1 c2]
(lazy-seq
(let [s1 (seq c1)
s2 (seq c2)]
(cond
(and s1 s2) ; there are elements left in both
(cons (first s1) (cons (first s2)
(interleave-all (rest s1) (rest s2))))

s1 ; s2 is done
s1

s2 ; s1 is done
s2))))
([c1 c2 & colls]
(lazy-seq
(let [ss (filter identity
(map seq
(conj colls c2 c1)))]
(concat (map first ss)
(apply interleave-all (map rest ss)))))))

Usage (commas are mine):
user=> (interleave-all [1 2 3 4 5] '[a b c d e f g h i])
(1 a, 2 b, 3 c, 4 d, 5 e, f, g, h, i)
user=> (interleave-all [1 2 3 4 5] '[a b c d e f g h i] '[A B])
(1 a A, 2 b B, 3 c 4, d 5, e, f, g, h, i)
It is still lazy:
user=> (take 50 (interleave-all [1 2 3 4 5] '[a b c d e f g h i] '[A B
C D E F G H I J K L] (iterate inc 0)))
(1 a A 0, 2 b B 1, 3 c C 2, 4 d D 3, 5 e E 4, f F 5, g G 6, h H 7, i I
8, J 9, K 10, L 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)

Alex

[nchubrich]

My 'requirements' were not so much for any particular need, but to try
to think up a logical and complete API for dealing with multisets. I
agree that there should be an actual collection type for multisets
(implemented as an underlying map of values to frequencies I presume);
but you might as well also be allowed to pass any kind of collections
and have it do something order-preserving with them. It makes a good
gathering point for sequence functionalities as \well as handling
multisets.

Alex is right that the keep-likes-with-likes option is a little
weird. I'm not sure whether to just conj them next to the first
instance, or try to equally distribute them as much as possible
throughout the instances, leaving any remainders on the initial ones.
Probably the latter. Of course when you have this kind of
questioning, maybe it is not a good fundamental functionality to
add.

(My original spur for this was in merging argument lists in a
permissive argument list macro I'm working on; the idea was you would
get 'rest' type parameters anywhere in the list there is a repetition
of variables under a keyword. Obviously you wouldn't want to have
disparate instances of the same thing here. (My initial thoughts on
this macro are at the bottom of the most recent discussion of keyword
arguments. (How, by the way, do you do "show quoted text"?))

There is a sort of hierarchy of sequences for being sensible for
multiset operations. First we have multisets themselves. Then we
have sequences that are ordered but have no dislocated repetition of
elements. Then we have arbitrary sequences. I'm inclined to want an
API that handles all three.

Maybe someone who does a lot of statistical work would have a better
idea of how this API should work.

Sean, regarding doall, the reason I wanted to have an internal
override is to be able to preserve the collection type of the
arguments. Sometimes it gets a little annoying to cast these back
every time; and when you're dealing with small sequences, laziness is
not really necessary. If you wanted to be \really evil about it, you
could have a bind-able variable *lazy* that sets it one way or the
other.

[nchubrich]

If you think about it, the tower of sequence types is like this:

seq
|
gathered seq
/ \
multiset permutation

\ /
set

The way to do the various options I pointed out is to mix types: the
keep-likes-with-likes would be (union <permutation> <multiset>).
take-away-all would be (difference <gathered-seq> <set>), while take-
away-some would be (difference <gathered seq> <multiset>).

The problem is once you add seq on top, it gets a little defective, as
Alex pointed out. (multiset <seq>) is easy, as is (permutation
<gathered-seq>), but there's no unambiguous way of going from a seq to
a permutation or to a gathered seq. The 'left' side of the tower is
much happier than the right.

It's also hard to sign an interpretation to all the combinations on
the tower; for instance, what is the union of two permutations? This
needs a little TLC from a category theorist...

Nevertheless, this might be a good way of grouping functionalities
into an API. The set API can be extended to all these types, and
branch into additional combination operators as it moves up the tower
(with really an infinite number for seqs....).

[Emeka]

Nick,

 

Remember to re-visit indexed and  index-filter functions of programming Clojure.

 

Regard,

Emeka 

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@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+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

[Emeka]

John,

 

You should have added that you code came from Programming Clojure.

 

Regards,

Emeka

[John Harrop]

On Sun, Nov 22, 2009 at 7:54 AM, Emeka <emeka...@gmail.com> wrote:

John,

 

You should have added that you code came from Programming Clojure.

It didn't. If it's the same as, or closely similar to, code from there, it's entirely coincidental.

In Clojure there's usually several ways to do something, but often only a few elegant ways to do something as short as that, so it's not very surprising. (I checked and my implementation of indexed is virtually identical to the one in clojure.contrib too, as it happens.)

[nchubrich]

Thanks Emeka, I took a look at it. I still say it would be nice to
organize the sequence functions (somehow).