Re: using take-while with pred function that has state
On Monday, 3 September 2012 06:26:07 UTC+1, Stephen Compall wrote: (- ss (map tok-fn), (reductions (partial apply merge) #{}), (take-while #(...)), (map #(do %2 %1) ss), last) Use of `atom' for this sort of thing is certainly an antipattern, so consider any alternative that suits you. Much appreciated, this has been most helpful. -- 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: using take-while with pred function that has state
On Monday, 3 September 2012 14:03:42 UTC+1, Dave Sann wrote: (defn take-while-reduce fancy take accumulating a reduced value on taken items this value can then be tested in the take fn Much appreciated. -- 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: using take-while with pred function that has state
On Mon, Sep 3, 2012 at 10:36 PM, Aaron Cohen aa...@assonance.org wrote: It wouldn't even be all that insane if you had 1000 otherwise idle cores sitting around and an expensive enough predicate. Touché (perhaps up to a factor of n). (Though I suspect you need more assumptions given that the specific algorithm has the predicate being called on the 1000n computed elements in reverse order.) But, of course, you might not have all those cores/such an expensive predicate---after all, we keep regular old map around even in the presence of pmap. Even in the parallel case, it seems that what's important isn't that pred be free of side-effects sans phrase, but that the order pred is called on the elements of call not matter. If pred is pure, then the condition is met, but pred can have side-effects while still meeting that condition. -- Ben Wolfson Human kind has used its intelligence to vary the flavour of drinks, which may be sweet, aromatic, fermented or spirit-based. ... Family and social life also offer numerous other occasions to consume drinks for pleasure. [Larousse, Drink entry] -- 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: using take-while with pred function that has state
On Mon, Sep 3, 2012 at 1:58 PM, Stephen Compall stephen.comp...@gmail.com wrote: On Sun, 2012-09-02 at 23:02 -0700, Ben Wolfson wrote: Can you say what this means (the note about take-while being called in coll order)? Does it mean that it's not a guarantee of the API that the predicate passed to take-while be called *successively* on the items in the collection passed in? Yes, that's what it means. Sorry I was not more clear. Stephen, could you elaborate on this? My reading of the side-effect-free restriction was just that the predicate may be called on more elements than end up in the result, perhaps due to chunking or whatever. I'm not sure I see where there's any indication that take-while might call the predicate in a non-linear order - or is just one of those 'guilty by omission' situations? -- Sean A Corfield -- (904) 302-SEAN An Architect's View -- http://corfield.org/ World Singles, LLC. -- http://worldsingles.com/ Perfection is the enemy of the good. -- Gustave Flaubert, French realist novelist (1821-1880) -- 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: using take-while with pred function that has state
On Tue, 2012-09-04 at 09:48 -0700, Sean Corfield wrote: Stephen, could you elaborate on this? Requiring pred to be free of side effects provides many invariants about it to the `take-while' implementation; the legality of out-of-order calling is just one of them. My reading of the side-effect-free restriction was just that the predicate may be called on more elements than end up in the result, perhaps due to chunking or whatever. I don't know what the original intent of the docstring was. Perhaps it was merely written that way because it was shorter; perhaps a precise explanation of how pred would be called was considered too much for doc purposes. It might mean something somewhere in between. I am basing this only on what the docstring says. [1] I can imagine a few alternative `take-while's that could effectively exploit out-of-order calling. [2] But even aside from reordering, I can't even name every potentially useful freedom we have given `take-while' by making pred pure, much less every way of using those freedoms. I cannot say what new ideas may be incorporated into take-while in the future by taking advantage of purity. But I _can_ imagine my frustration, painstakingly tracking down bugs in my own software, induced by nothing but my own failure to follow this documented contract as a take-while caller. or is just one of those 'guilty by omission' situations? If that is what you mean by this, then yes. [1] I can, however, say that the documented invariant was added in Rich Hickey's a8307cc8, back in 2008. [2] Describing such examples would be rather esoteric for this thread, I feel. -- Stephen Compall ^aCollection allSatisfy: [:each | aCondition]: less is better than -- 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: using take-while with pred function that has state
On Tue, Sep 4, 2012 at 2:23 PM, Stephen Compall stephen.comp...@gmail.com wrote: On Tue, 2012-09-04 at 09:48 -0700, Sean Corfield wrote: Stephen, could you elaborate on this? Requiring pred to be free of side effects provides many invariants about it to the `take-while' implementation; the legality of out-of-order calling is just one of them. But that is a hypothetical, yes? You're not suggesting that take-while actually does that, right? It might mean something somewhere in between. I am basing this only on what the docstring says. [1] That commit also added pred must be free of side-effects to `filter` and replaced lazy-cons with lazy-seq (which suggests lazy-seq changed its semantics along the way since (lazy-seq :a [:b]) just yields (:b) these days but clearly needed to behave more like cons back then?). I think calling `pred` out of linear order is a far less likely intended freedom than those of calling `pred` more than once on a given element or calling `pred` on more elements that strictly needed. Either way, it's all a bit of a moot point: the docstring says - for take-while and filter - that the predicate should be free of side-effects and I think that makes it clear that using a predicate with side-effects can legally lead to undesirable behavior (such as being called more times than you might expect). So the OP should consider that possibility in their code. -- Sean A Corfield -- (904) 302-SEAN An Architect's View -- http://corfield.org/ World Singles, LLC. -- http://worldsingles.com/ Perfection is the enemy of the good. -- Gustave Flaubert, French realist novelist (1821-1880) -- 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: using take-while with pred function that has state
On Tue, 2012-09-04 at 15:24 -0700, Sean Corfield wrote: But that is a hypothetical, yes? You're not suggesting that take-while actually does that, right? Right. As of right now. -- Stephen Compall ^aCollection allSatisfy: [:each | aCondition]: less is better than -- 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: using take-while with pred function that has state
On Sun, Sep 2, 2012 at 10:25 PM, Stephen Compall stephen.comp...@gmail.com wrote: On Fri, 2012-08-31 at 05:08 -0700, shaobohou wrote: I have written the following function using take-while and a pred function with an atom to store the set of unique tokens. It works Only because in the current implementation, take-while happens to be called in coll order, which is not a guarantee of the API. Can you say what this means (the note about take-while being called in coll order)? Does it mean that it's not a guarantee of the API that the predicate passed to take-while be called *successively* on the items in the collection passed in? I would have hoped that would be guaranteed---otherwise you might be forcing the computation of elements of a lazy sequence unnecessarily, which could be expensive, even if there are no side-effects, or (potentially, at least) raise an exception that would otherwise not be raised. -- Ben Wolfson Human kind has used its intelligence to vary the flavour of drinks, which may be sweet, aromatic, fermented or spirit-based. ... Family and social life also offer numerous other occasions to consume drinks for pleasure. [Larousse, Drink entry] -- 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: using take-while with pred function that has state
(map #(do %2 %1) c1 c2) is a neat trick I hadn't seen in this context; thanks for showing me! On Sunday, September 2, 2012 10:26:07 PM UTC-7, Stephen Compall wrote: On Fri, 2012-08-31 at 05:08 -0700, shaobohou wrote: I have written the following function using take-while and a pred function with an atom to store the set of unique tokens. It works Only because in the current implementation, take-while happens to be called in coll order, which is not a guarantee of the API. Will this be problem in my implementation if I am calling it from multiple threads? No. And what would be the more idiomatic way of implementing this kind of behaviour? Consider this restructuring: (- ss (map tok-fn), (reductions (partial apply merge) #{}), (take-while #(...)), (map #(do %2 %1) ss), last) Use of `atom' for this sort of thing is certainly an antipattern, so consider any alternative that suits you. -- Stephen Compall ^aCollection allSatisfy: [:each | aCondition]: less is better than -- 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: using take-while with pred function that has state
I have used the following in the past in some utils I have for seqs: (defn take-while-reduce fancy take accumulating a reduced value on taken items this value can then be tested in the take fn e.g (take-while-reduce 0 (fn [v i] (inc v)) (fn [v i] (= v i)) [1 2 3 5 6 7]) = (1 2 3) [initial reduce-fn pred coll] (when-let [s (seq coll)] (let [[f r] coll reduce-value (reduce-fn initial f)] (if (pred reduce-value f) (cons f (take-while-reduce reduce-value reduce-fn pred r)) (comment ;; examples ;; take while value increment (take-while-reduce 0 (fn [v i] (inc v)) (fn [v i] (= v i)) [1 2 3 5 6 7]) ;; acts like a line break (take-while-reduce 0 (fn [v i] (+ v (count i))) (fn [v i] ( v 20)) (ccsu/partition the quick brown fox jumps #\s+)) ) ; ccsu/partition is the old clojure contrib str-utils2 - it's a while since I did this Dave On Friday, 31 August 2012 22:08:03 UTC+10, shaobohou wrote: Hi, I am trying to write a function which takes a list of strings, tokenize each one, and maximise N such that the number of unique tokens in the first N strings is less than some number M. I have written the following function using take-while and a pred function with an atom to store the set of unique tokens. It works and is just as fast as a messier loop/recur version. (defn take-as-many-as-possible-until [ss tok-fn m] (let [items (atom #{})] (- (fn [v] (swap! items (partial apply merge) (tok-fn v)) ( (count @items) m)) (take-while ss However, I have noticed that the take-while documentation says that the pred function should be side-effect free. Will this be problem in my implementation if I am calling it from multiple threads? And what would be the more idiomatic way of implementing this kind of behaviour? Thanks, Shaobo -- 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: using take-while with pred function that has state
I have used the following (from a bunch of utils I have for seqs) in the past to do this kind of thing. You will need to define the reduce-fn and the predicate you need. examples below in the comment. (defn take-while-reduce fancy take accumulating a reduced value on taken items this value can then be tested in the take fn e.g (take-while-reduce 0 (fn [v i] (inc v)) (fn [v i] (= v i)) [1 2 3 5 6 7]) = (1 2 3) [initial reduce-fn pred coll] (when-let [s (seq coll)] (let [[f r] coll reduce-value (reduce-fn initial f)] (if (pred reduce-value f) (cons f (take-while-reduce reduce-value reduce-fn pred r)) (comment ;; examples (take-while-reduce 0 (fn [v i] (inc v)) (fn [v i] (= v i)) [1 2 3 5 6 7]) ;; acts like a line break (take-while-reduce 0 (fn [v i] (+ v (count i))) (fn [v i] ( v 20)) (ccsu/partition the quick brown fox jumps #\s+)) ) ; ccsu is the old clojure contrin str-utils2 On Friday, 31 August 2012 22:08:03 UTC+10, shaobohou wrote: Hi, I am trying to write a function which takes a list of strings, tokenize each one, and maximise N such that the number of unique tokens in the first N strings is less than some number M. I have written the following function using take-while and a pred function with an atom to store the set of unique tokens. It works and is just as fast as a messier loop/recur version. (defn take-as-many-as-possible-until [ss tok-fn m] (let [items (atom #{})] (- (fn [v] (swap! items (partial apply merge) (tok-fn v)) ( (count @items) m)) (take-while ss However, I have noticed that the take-while documentation says that the pred function should be side-effect free. Will this be problem in my implementation if I am calling it from multiple threads? And what would be the more idiomatic way of implementing this kind of behaviour? Thanks, Shaobo -- 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: using take-while with pred function that has state
On Sun, 2012-09-02 at 23:02 -0700, Ben Wolfson wrote: Can you say what this means (the note about take-while being called in coll order)? Does it mean that it's not a guarantee of the API that the predicate passed to take-while be called *successively* on the items in the collection passed in? Yes, that's what it means. Sorry I was not more clear. I would have hoped that would be guaranteed Nevertheless, by declaring pred must be free of side-effects, `take-while' is refusing to make that promise, among many others. otherwise you might be forcing the computation of elements of a lazy sequence unnecessarily, which could be expensive, even if there are no side-effects, or (potentially, at least) raise an exception that would otherwise not be raised. In general, you may not assume that more elements of a lazy sequence than you need will not be computed. I exempt `reductions', `iterate', and any sequences derived from those in my own practice; you may be more or less comfortable with such exemptions. user= (first (map print [1 2 3 4])) 1234nil user= (first (map print '(1 2 3 4))) 1nil There's some misinformation on the web about exactly how this works; I recommend reading the implementations of map, filter, and concat in core.clj to gain a better understanding of seq chunking. -- Stephen Compall ^aCollection allSatisfy: [:each|aCondition]: less is better -- 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: using take-while with pred function that has state
On Mon, 2012-09-03 at 01:12 -0700, Alan Malloy wrote: (map #(do %2 %1) c1 c2) is a neat trick I hadn't seen in this context; thanks for showing me! Perhaps you'd also like to advocate for the inclusion of `first-arg', which has several other uses, in core? :) -- Stephen Compall ^aCollection allSatisfy: [:each|aCondition]: less is better -- 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: using take-while with pred function that has state
On Mon, Sep 3, 2012 at 1:58 PM, Stephen Compall stephen.comp...@gmail.com wrote: I would have hoped that would be guaranteed Nevertheless, by declaring pred must be free of side-effects, `take-while' is refusing to make that promise, among many others. It seems like a leap to go from pred being free of side-effects to refusing to make *that* promise. If the reason that pred must be free of side-effects that take-while is *thereby* free to call pred on the elements of coll in arbitrary order then actually only *some* side-effects need to be banned. (Maybe you want to track how many times pred has been called---that's a side effect but it shouldn't interfere with pred's being called more than strictly necessary for take-while to get the right answer, since, after all, if pred is called more than is strictly necessary, that's exactly what you wanted to know.) And in refusing to make that promise, take-while is also doing *more* than just requiring that pred be free of (some) side-effects, it's also saying that take-while *itself* (i.e., *not* 'first') reserves the right to have the side-effecty function of forcing the computation of *arbitrary* amounts of a lazy sequence. Side note: the concept of *pred*, specifically, being free of side-effects seems underdetermined. Is (fn [f] (even? (f))) free of side-effects? It is iff f is. What if I pass in, not the pure function f, but rather the impure function (memoize f)? (memoize f) isn't *visibly* side-effecty to its caller (the way some Haskell people are willing to sell their souls and say, well, you can use unsafePerformIO as long as *you* know it's safe...), but it isn't side-effect-free sensu stricto. In general, you may not assume that more elements of a lazy sequence than you need will not be computed. I exempt `reductions', `iterate', and any sequences derived from those in my own practice; you may be more or less comfortable with such exemptions. user= (first (map print [1 2 3 4])) 1234nil user= (first (map print '(1 2 3 4))) 1nil I'm aware of seq chunking; it seems tangential to the main concern here. The following two questions are distinct: - will calling first on a lazy seq cause more than just its first element to be computed? - will take-while cause more of a lazy seq to be realized than is present in its output *because it calls pred on arbitrary elements of the seq*? Of course take-while might cause more of a lazy seq to be realized than is present in its output because of seq chunking. But I'd *hope* that it wouldn't exacerbate that by reserving the right to work like, say, this, where n is the largest number of elements of a seq calling first might compute: 1. Realize the first 1000n elements of a seq, retaining them in memory. 2. Call pred on those elements in reverse order. 3. If pred was true for all of them, realize the next 1000n elements, etc., otherwise return a lazy seq of the first stretch of elements for which pred returned true. That admittedly would be insane, but if pred is free of side-effects (and computing the elements of the collection is also free of side-effects) it would be correct. -- Ben Wolfson Human kind has used its intelligence to vary the flavour of drinks, which may be sweet, aromatic, fermented or spirit-based. ... Family and social life also offer numerous other occasions to consume drinks for pleasure. [Larousse, Drink entry] -- 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: using take-while with pred function that has state
On Tue, Sep 4, 2012 at 1:24 AM, Ben Wolfson wolf...@gmail.com wrote: On Mon, Sep 3, 2012 at 1:58 PM, Stephen Compall stephen.comp...@gmail.com wrote: Of course take-while might cause more of a lazy seq to be realized than is present in its output because of seq chunking. But I'd *hope* that it wouldn't exacerbate that by reserving the right to work like, say, this, where n is the largest number of elements of a seq calling first might compute: 1. Realize the first 1000n elements of a seq, retaining them in memory. 2. Call pred on those elements in reverse order. 3. If pred was true for all of them, realize the next 1000n elements, etc., otherwise return a lazy seq of the first stretch of elements for which pred returned true. That admittedly would be insane, but if pred is free of side-effects (and computing the elements of the collection is also free of side-effects) it would be correct. It wouldn't even be all that insane if you had 1000 otherwise idle cores sitting around and an expensive enough predicate. -- 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
using take-while with pred function that has state
Hi, I am trying to write a function which takes a list of strings, tokenize each one, and maximise N such that the number of unique tokens in the first N strings is less than some number M. I have written the following function using take-while and a pred function with an atom to store the set of unique tokens. It works and is just as fast as a messier loop/recur version. (defn take-as-many-as-possible-until [ss tok-fn m] (let [items (atom #{})] (- (fn [v] (swap! items (partial apply merge) (tok-fn v)) ( (count @items) m)) (take-while ss However, I have noticed that the take-while documentation says that the pred function should be side-effect free. Will this be problem in my implementation if I am calling it from multiple threads? And what would be the more idiomatic way of implementing this kind of behaviour? Thanks, Shaobo -- 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: using take-while with pred function that has state
On Fri, 2012-08-31 at 05:08 -0700, shaobohou wrote: I have written the following function using take-while and a pred function with an atom to store the set of unique tokens. It works Only because in the current implementation, take-while happens to be called in coll order, which is not a guarantee of the API. Will this be problem in my implementation if I am calling it from multiple threads? No. And what would be the more idiomatic way of implementing this kind of behaviour? Consider this restructuring: (- ss (map tok-fn), (reductions (partial apply merge) #{}), (take-while #(...)), (map #(do %2 %1) ss), last) Use of `atom' for this sort of thing is certainly an antipattern, so consider any alternative that suits you. -- Stephen Compall ^aCollection allSatisfy: [:each | aCondition]: less is better than -- 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