Re: Why take-last of empty collection is nil?

2011-02-03 Thread Ken Wesson
On Thu, Feb 3, 2011 at 5:22 PM, Alan  wrote:
> You don't need an extra element in the vector to distinguish between
> empty and full. You can store (start, size) instead of (start, end).

I considered that, but it made the arithmetic much messier in various
places. Count gets simpler, obviously, but things like conj now need
to use (start + size + 1) mod capacity and some things get awkward
elsewhere.

My implementation probably saves a few cycles, at a cost of a few
bytes more storage per ring buffer. I suppose either tradeoff is an
acceptable choice for nearly all cases though.

-- 
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


Re: Why take-last of empty collection is nil?

2011-02-03 Thread Alan
You don't need an extra element in the vector to distinguish between
empty and full. You can store (start, size) instead of (start, end).

On Feb 3, 12:57 pm, Ken Wesson  wrote:
> On Thu, Feb 3, 2011 at 2:03 PM, Alan  wrote:
> > Or use a fixed-size vector as a ring, with start and end "pointers",
> > and a couple functions to abstract over the handling thereof. But
> > unless you really really care about performance, this is likely to be
> > overkill, and Ken's suggestion to just use a vector or a seq and
> > accept the O(n) behavior.
>
> A ring buffer. I considered using one to implement a deque, but
> resizing it presented severe technical difficulties so I shelved that
> approach. But for a fixed-size one it's perfect.
>
> Below is a persistent immutable ring buffer implementation using
> deftype. It behaves as a vector that accepts lpeek, lpop, and lconj
> acting on the left as well as peek, pop, and conj acting on the right
> and has a maximum capacity. Adding at either end when it is at
> capacity causes it to drop an element at the other end. The assoc,
> nth, and so forth functions work, but the index of a given element
> changes if elements are dropped or added at the left end; assoc
> accepts index -1 which adds at the left end, as well as index count
> which adds at the right, an extension of how assoc can be used to grow
> a vector at the right.
>
> Create one with (ringbuffer capacity item item item ...), or just
> (ringbuffer capacity) to get an empty one. The empty function produces
> an empty ringbuffer with the same capacity as the argument ringbuffer,
> so the capacity of (empty (ringbuffer 5 1 2 3 4 5)) will be 5.
>
> I've tested it somewhat and it seems to work correctly. Let me know if
> you use it, and especially if you run into any bugs.
>
> Implementation note: internally there is a vector with a size one
> greater than capacity (otherwise, start=end wouldn't distinguish an
> empty from a full one!) and cap is one greater than capacity (it's the
> modulus used for all the pointer arithmetic). The various "mutating"
> methods ensure that removed objects are replaced with nil in the
> vector (in particular, the "gap" between the last and first element is
> always nil) so that things lost from the ring buffer may be promptly
> eligible for garbage collection if nowhere else referenced.
>
> (defprotocol LPop
>   (lpeek [this])
>   (lpop [this])
>   (lconj [this object]))
>
> (defn +mod [a b m]
>   (mod (+ a b) m))
>
> (defn incmod [a m]
>   (+mod a 1 m))
>
> (defn -mod [a b m]
>   (mod (- a b) m))
>
> (defn decmod [a m]
>   (-mod a 1 m))
>
> (deftype RingBuffer [content cap start end]
>   clojure.lang.IObj
>     (withMeta [this m] (RingBuffer. (with-meta content m) cap start end))
>     (meta [this] (meta content))
>   clojure.lang.IPersistentVector
>     (cons [this object]
>       (let [e (incmod end cap)
>              s (if (== start e) (incmod start cap) start)]
>         (RingBuffer.
>           (assoc (assoc content end object) e nil)
>           cap s e)))
>     (count [this] (-mod (+ end cap) start cap))
>     (empty [this] (RingBuffer. (vec (repeat cap nil)) cap 0 0))
>     (equiv [this other] (= (seq this) other))
>     (seq [this]
>       (when-not (== end start)
>         (seq
>           (if (> end start)
>             (subvec content start end)
>             (lazy-cat (subvec content start) (subvec content 0 end))
>     (peek [this]
>       (when-not (== start end)
>         (nth content (decmod end cap
>     (pop [this]
>       (if (== start end)
>         (throw (IllegalStateException. "Can't pop empty ringbuffer"))
>         (let [e (decmod end cap)]
>           (RingBuffer.
>             (assoc content e nil)
>             cap start e
>     (containsKey [this object]
>        (and
>          (integer? object)
>          (>= object 0)
>          (< object (count this
>     (assoc [this key val]
>       (if (integer? key)
>         (if (= key -1)
>           (lconj this val)
>           (if (or (< key 0) (> key (count this)))
>             (throw (IndexOutOfBoundsException.))
>             (let [n (+mod key start cap)]
>               (if (= n end)
>                 (conj this val)
>                 (RingBuffer. (assoc content n val) cap start end)
>         (throw (IllegalArgumentException. "key must be an ingeger"
>     (entryAt [this key]
>       (if (.containsKey this key)
>         (first {key (content (+mod key start cap))})))
>     (valAt [this key]
>       (.valAt this key nil))
>     (valAt [this key not-found]
>       (if (.containsKey this key)
>         (content (+mod key start cap))
>         not-found))
>     (nth [this key]
>       (if (.containsKey this key)
>         (.valAt this key)
>         (throw (IndexOutOfBoundsException.
>     (nth [this key not-found]
>       (.valAt this key not-found))
>     (rseq [this]
>       (if (> end start)
>         (rseq (subvec content start end))
>         (lazy-cat (rseq (subvec content 

Re: Why take-last of empty collection is nil?

2011-02-03 Thread Ken Wesson
On Thu, Feb 3, 2011 at 2:03 PM, Alan  wrote:
> Or use a fixed-size vector as a ring, with start and end "pointers",
> and a couple functions to abstract over the handling thereof. But
> unless you really really care about performance, this is likely to be
> overkill, and Ken's suggestion to just use a vector or a seq and
> accept the O(n) behavior.


A ring buffer. I considered using one to implement a deque, but
resizing it presented severe technical difficulties so I shelved that
approach. But for a fixed-size one it's perfect.

Below is a persistent immutable ring buffer implementation using
deftype. It behaves as a vector that accepts lpeek, lpop, and lconj
acting on the left as well as peek, pop, and conj acting on the right
and has a maximum capacity. Adding at either end when it is at
capacity causes it to drop an element at the other end. The assoc,
nth, and so forth functions work, but the index of a given element
changes if elements are dropped or added at the left end; assoc
accepts index -1 which adds at the left end, as well as index count
which adds at the right, an extension of how assoc can be used to grow
a vector at the right.

Create one with (ringbuffer capacity item item item ...), or just
(ringbuffer capacity) to get an empty one. The empty function produces
an empty ringbuffer with the same capacity as the argument ringbuffer,
so the capacity of (empty (ringbuffer 5 1 2 3 4 5)) will be 5.

I've tested it somewhat and it seems to work correctly. Let me know if
you use it, and especially if you run into any bugs.

Implementation note: internally there is a vector with a size one
greater than capacity (otherwise, start=end wouldn't distinguish an
empty from a full one!) and cap is one greater than capacity (it's the
modulus used for all the pointer arithmetic). The various "mutating"
methods ensure that removed objects are replaced with nil in the
vector (in particular, the "gap" between the last and first element is
always nil) so that things lost from the ring buffer may be promptly
eligible for garbage collection if nowhere else referenced.

(defprotocol LPop
  (lpeek [this])
  (lpop [this])
  (lconj [this object]))

(defn +mod [a b m]
  (mod (+ a b) m))

(defn incmod [a m]
  (+mod a 1 m))

(defn -mod [a b m]
  (mod (- a b) m))

(defn decmod [a m]
  (-mod a 1 m))

(deftype RingBuffer [content cap start end]
  clojure.lang.IObj
(withMeta [this m] (RingBuffer. (with-meta content m) cap start end))
(meta [this] (meta content))
  clojure.lang.IPersistentVector
(cons [this object]
  (let [e (incmod end cap)
 s (if (== start e) (incmod start cap) start)]
(RingBuffer.
  (assoc (assoc content end object) e nil)
  cap s e)))
(count [this] (-mod (+ end cap) start cap))
(empty [this] (RingBuffer. (vec (repeat cap nil)) cap 0 0))
(equiv [this other] (= (seq this) other))
(seq [this]
  (when-not (== end start)
(seq
  (if (> end start)
(subvec content start end)
(lazy-cat (subvec content start) (subvec content 0 end))
(peek [this]
  (when-not (== start end)
(nth content (decmod end cap
(pop [this]
  (if (== start end)
(throw (IllegalStateException. "Can't pop empty ringbuffer"))
(let [e (decmod end cap)]
  (RingBuffer.
(assoc content e nil)
cap start e
(containsKey [this object]
   (and
 (integer? object)
 (>= object 0)
 (< object (count this
(assoc [this key val]
  (if (integer? key)
(if (= key -1)
  (lconj this val)
  (if (or (< key 0) (> key (count this)))
(throw (IndexOutOfBoundsException.))
(let [n (+mod key start cap)]
  (if (= n end)
(conj this val)
(RingBuffer. (assoc content n val) cap start end)
(throw (IllegalArgumentException. "key must be an ingeger"
(entryAt [this key]
  (if (.containsKey this key)
(first {key (content (+mod key start cap))})))
(valAt [this key]
  (.valAt this key nil))
(valAt [this key not-found]
  (if (.containsKey this key)
(content (+mod key start cap))
not-found))
(nth [this key]
  (if (.containsKey this key)
(.valAt this key)
(throw (IndexOutOfBoundsException.
(nth [this key not-found]
  (.valAt this key not-found))
(rseq [this]
  (if (> end start)
(rseq (subvec content start end))
(lazy-cat (rseq (subvec content 0 end)) (rseq (subvec content start)
  LPop
(lpeek [this]
  (when-not (== start end)
(nth content start)))
(lpop [this]
  (if (== start end)
(throw (IllegalStateException. "Can't pop empty ringbuffer"))
(RingBuffer.
  (assoc content start nil)
  cap (incmod start cap) end)))
(lconj [this object]
  (let [s (decmod start cap)
ss

Re: Why take-last of empty collection is nil?

2011-02-03 Thread Alan
Or use a fixed-size vector as a ring, with start and end "pointers",
and a couple functions to abstract over the handling thereof. But
unless you really really care about performance, this is likely to be
overkill, and Ken's suggestion to just use a vector or a seq and
accept the O(n) behavior.

On Feb 3, 10:22 am, Ken Wesson  wrote:
> On Thu, Feb 3, 2011 at 3:11 AM, Petr Gladkikh  wrote:
> > On Thu, Feb 3, 2011 at 1:31 PM, Meikel Brandmeyer  wrote:
> >> Hi,
>
> >> On 3 Feb., 08:04, Petr Gladkikh  wrote:
>
> >>> Should not it be empty colection instead?
> >>> It seems odd to me since it is inconsistent and forces to consider one
> >>> more case (nil or collection).
>
> >> It is consistent. There is a difference between () and nil. () is the
> >> empty list. However there is no "empty sequence." Either there is
> >> something or there is nothing. Why would you have to check for nil?
> >> You can pass nil to any of the sequence library functions without fear
> >> of harm. When you write such a function yourself, there is usually a
> >> single check in the beginning when realising the sequence. Something
> >> like (when-let [s (seq coll)] ...).
>
> >> I never encountered any problems with this. Do you have a concrete
> >> example where this causes trouble for you?
>
> > I have a vector that holds some history. I conj new items to it and to
> > save space I'd like to retain not more than n last items.
> > To do that I used (take-last n history). So: [] -> (take-last n []) ->
> > nil -> (conj nil newItem) -> '(newItem)
>
> > But list conj's at the beginning not at end of sequence as I would
> > like to. Of course I could use () from the beginning (with account for
> > reverse order).
> > But with [] I should do little more.
>
> Depending on your "little more", you might want to wrap the queue
> implementation I posted a while ago with something like
>
> (defn push-max [q item max]
>   (let [q (conj q item)]
>     (if (> (count q) max)
>       (pop q)
>       q)))
>
> This will be efficient (in particular, the count function should be
> efficient on my queue) without any full traversals (unlike take-last).
> The least recent item can be viewed with peek. If you want to view the
> most recent item you could use my deque implementation (amortized O(1)
> operations at both ends, and O(1) count) which lets you peek both
> ends.
>
> But neither will satisfy you if you want to random access in the
> middle. If you want to partially traverse from only one end (either
> youngest or oldest items) my deque will do: it can be partially
> traversed from the left end efficiently with seq, so you'd add new
> items at that end if you wanted to partially traverse youngest items,
> and at the other if you wanted to partially traverse oldest items.
>
> Of course, if the max length is short it won't matter much; you can
> just use a vector and (vec (take-last ...)) and it won't be very
> inefficient, nor would using reverse on a queue or deque to traverse
> from the other end and last to peek the "difficult" end of a queue.

-- 
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


Re: Why take-last of empty collection is nil?

2011-02-03 Thread Ken Wesson
On Thu, Feb 3, 2011 at 3:11 AM, Petr Gladkikh  wrote:
> On Thu, Feb 3, 2011 at 1:31 PM, Meikel Brandmeyer  wrote:
>> Hi,
>>
>> On 3 Feb., 08:04, Petr Gladkikh  wrote:
>>
>>> Should not it be empty colection instead?
>>> It seems odd to me since it is inconsistent and forces to consider one
>>> more case (nil or collection).
>>
>> It is consistent. There is a difference between () and nil. () is the
>> empty list. However there is no "empty sequence." Either there is
>> something or there is nothing. Why would you have to check for nil?
>> You can pass nil to any of the sequence library functions without fear
>> of harm. When you write such a function yourself, there is usually a
>> single check in the beginning when realising the sequence. Something
>> like (when-let [s (seq coll)] ...).
>>
>> I never encountered any problems with this. Do you have a concrete
>> example where this causes trouble for you?
>
> I have a vector that holds some history. I conj new items to it and to
> save space I'd like to retain not more than n last items.
> To do that I used (take-last n history). So: [] -> (take-last n []) ->
> nil -> (conj nil newItem) -> '(newItem)
>
> But list conj's at the beginning not at end of sequence as I would
> like to. Of course I could use () from the beginning (with account for
> reverse order).
> But with [] I should do little more.

Depending on your "little more", you might want to wrap the queue
implementation I posted a while ago with something like

(defn push-max [q item max]
  (let [q (conj q item)]
(if (> (count q) max)
  (pop q)
  q)))

This will be efficient (in particular, the count function should be
efficient on my queue) without any full traversals (unlike take-last).
The least recent item can be viewed with peek. If you want to view the
most recent item you could use my deque implementation (amortized O(1)
operations at both ends, and O(1) count) which lets you peek both
ends.

But neither will satisfy you if you want to random access in the
middle. If you want to partially traverse from only one end (either
youngest or oldest items) my deque will do: it can be partially
traversed from the left end efficiently with seq, so you'd add new
items at that end if you wanted to partially traverse youngest items,
and at the other if you wanted to partially traverse oldest items.

Of course, if the max length is short it won't matter much; you can
just use a vector and (vec (take-last ...)) and it won't be very
inefficient, nor would using reverse on a queue or deque to traverse
from the other end and last to peek the "difficult" end of a queue.

-- 
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


Re: Why take-last of empty collection is nil?

2011-02-03 Thread Bill James
On Feb 3, 1:04 am, Petr Gladkikh  wrote:

>
> And another question. I have written this function
> (defn index-by
>   "Make map (f x) -> x"
>   [f coll]
>   (reduce #(assoc %1 (f %2) %2) {} coll))
>
> I wonder, is there already such function somewhere in Clojure libraries?

Somewhat shorter:

(defn index-by [f coll]
  (zipmap (map f coll) coll))

-- 
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


Re: Why take-last of empty collection is nil?

2011-02-03 Thread Meikel Brandmeyer
Hi,

On 3 Feb., 09:11, Petr Gladkikh  wrote:

> I have a vector that holds some history. I conj new items to it and to
> save space I'd like to retain not more than n last items.
> To do that I used (take-last n history). So: [] -> (take-last n []) ->
> nil -> (conj nil newItem) -> '(newItem)
>
> But list conj's at the beginning not at end of sequence as I would
> like to. Of course I could use () from the beginning (with account for
> reverse order).
> But with [] I should do little more.

There is a misunderstanding here: the sequence functions return - well
- sequences. If you want a vector back, you have to tell Clojure so.

[] -> (take-last n []) -> nil -> (vec nil) -> []
[1 2 3] -> (take-last n [1 2 3]) -> (3) -> (vec (3)) -> [3].

Or use into:

(into (empty input) (take-last n input))

Sincerely
Meikel

-- 
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


Re: Why take-last of empty collection is nil?

2011-02-03 Thread Petr Gladkikh
On Thu, Feb 3, 2011 at 1:31 PM, Meikel Brandmeyer  wrote:
> Hi,
>
> On 3 Feb., 08:04, Petr Gladkikh  wrote:
>
>> Should not it be empty colection instead?
>> It seems odd to me since it is inconsistent and forces to consider one
>> more case (nil or collection).
>
> It is consistent. There is a difference between () and nil. () is the
> empty list. However there is no "empty sequence." Either there is
> something or there is nothing. Why would you have to check for nil?
> You can pass nil to any of the sequence library functions without fear
> of harm. When you write such a function yourself, there is usually a
> single check in the beginning when realising the sequence. Something
> like (when-let [s (seq coll)] ...).
>
> I never encountered any problems with this. Do you have a concrete
> example where this causes trouble for you?

I have a vector that holds some history. I conj new items to it and to
save space I'd like to retain not more than n last items.
To do that I used (take-last n history). So: [] -> (take-last n []) ->
nil -> (conj nil newItem) -> '(newItem)

But list conj's at the beginning not at end of sequence as I would
like to. Of course I could use () from the beginning (with account for
reverse order).
But with [] I should do little more.

-- 
Petr Gladkikh

-- 
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


Re: Why take-last of empty collection is nil?

2011-02-02 Thread Ken Wesson
On Thu, Feb 3, 2011 at 2:31 AM, Meikel Brandmeyer  wrote:
> Hi,
>
> On 3 Feb., 08:04, Petr Gladkikh  wrote:
>
>> Should not it be empty colection instead?
>> It seems odd to me since it is inconsistent and forces to consider one
>> more case (nil or collection).
>
> It is consistent. There is a difference between () and nil. () is the
> empty list. However there is no "empty sequence."

According to Clojure 1.2 itself, there is:

user=> (seq? ())
true

The empty list is both, it seems. :)

However,

user=> (seq ())
nil

so (if-let [s (seq x)] ...) still works to separate empty lists
(indeed, all empty colls) from non-empty ones.

Also of interest is

user=> (seq? nil)
false

The sequence functions accept it nonetheless, and most accept vectors,
sets, and maps as well. In particular:

user=> (nth nil 42)
nil
user=> (nth nil 42 "not found")
"not found"

-- 
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


Re: Why take-last of empty collection is nil?

2011-02-02 Thread Meikel Brandmeyer
Hi,

On 3 Feb., 08:04, Petr Gladkikh  wrote:

> Should not it be empty colection instead?
> It seems odd to me since it is inconsistent and forces to consider one
> more case (nil or collection).

It is consistent. There is a difference between () and nil. () is the
empty list. However there is no "empty sequence." Either there is
something or there is nothing. Why would you have to check for nil?
You can pass nil to any of the sequence library functions without fear
of harm. When you write such a function yourself, there is usually a
single check in the beginning when realising the sequence. Something
like (when-let [s (seq coll)] ...).

I never encountered any problems with this. Do you have a concrete
example where this causes trouble for you?

> And another question. I have written this function
> (defn index-by
>   "Make map (f x) -> x"
>   [f coll]
>   (reduce #(assoc %1 (f %2) %2) {} coll))
>
> I wonder, is there already such function somewhere in Clojure libraries?

You are probably looking for group-by, although it's slightly
different in that it collects all pre-images of a value (f x) in case
your function is not injective.

Sincerely
Meikel

-- 
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


Why take-last of empty collection is nil?

2011-02-02 Thread Petr Gladkikh
Should not it be empty colection instead?
It seems odd to me since it is inconsistent and forces to consider one
more case (nil or collection).

And another question. I have written this function
(defn index-by
  "Make map (f x) -> x"
  [f coll]
  (reduce #(assoc %1 (f %2) %2) {} coll))

I wonder, is there already such function somewhere in Clojure libraries?

-- 
Petr Gladkikh

-- 
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