Re: Why take-last of empty collection is nil?
On Thu, Feb 3, 2011 at 1:31 PM, Meikel Brandmeyer m...@kotka.de wrote: Hi, On 3 Feb., 08:04, Petr Gladkikh petrg...@gmail.com 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?
Hi, On 3 Feb., 09:11, Petr Gladkikh petrg...@gmail.com 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?
On Feb 3, 1:04 am, Petr Gladkikh petrg...@gmail.com 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?
On Thu, Feb 3, 2011 at 3:11 AM, Petr Gladkikh petrg...@gmail.com wrote: On Thu, Feb 3, 2011 at 1:31 PM, Meikel Brandmeyer m...@kotka.de wrote: Hi, On 3 Feb., 08:04, Petr Gladkikh petrg...@gmail.com 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?
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 kwess...@gmail.com wrote: On Thu, Feb 3, 2011 at 3:11 AM, Petr Gladkikh petrg...@gmail.com wrote: On Thu, Feb 3, 2011 at 1:31 PM, Meikel Brandmeyer m...@kotka.de wrote: Hi, On 3 Feb., 08:04, Petr Gladkikh petrg...@gmail.com 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?
On Thu, Feb 3, 2011 at 2:03 PM, Alan a...@malloys.org 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?
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 kwess...@gmail.com wrote:
On Thu, Feb 3, 2011 at 2:03 PM, Alan a...@malloys.org 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)
Re: Why take-last of empty collection is nil?
On Thu, Feb 3, 2011 at 5:22 PM, Alan a...@malloys.org 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
Why take-last of empty collection is nil?
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
Re: Why take-last of empty collection is nil?
Hi,
On 3 Feb., 08:04, Petr Gladkikh petrg...@gmail.com 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
Re: Why take-last of empty collection is nil?
On Thu, Feb 3, 2011 at 2:31 AM, Meikel Brandmeyer m...@kotka.de wrote: Hi, On 3 Feb., 08:04, Petr Gladkikh petrg...@gmail.com 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
