Re: Remove-first function
I expanded on this theme in a blog post: http://programming-puzzler.blogspot.com/2010/07/translating-code-from-python-and-scheme.html -- 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: Remove-first function
On Sat, Jul 24, 2010 at 9:07 AM, Gary Fredericks wrote: > (defn remove-first > [syb lst] > (let [[before after] > (loop [b [] a lst] > (if (empty? lst) > [b a] > (if (= syb (first a)) > [b (rest a)] > (recur (cons (first a) b) (rest a)] > (concat (reverse before) after))) > > user=> (remove-first 4 '(1 5 3 4 2 6 674 4 2)) > (1 5 3 2 6 674 4 2) > > I'm interested if somebody comes up with something more efficient, i.e. that > doesn't require the reversal. If you change (cons (first a) b) to (conj b (first a), then no reversal will be required. -- 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: Remove-first function
Well obviously if you can get something to be tail-recursive you won't have the stack overflows, and the thing in your code that prevents tail recursion is having to cons the result of the recursive call. So let's try this: (defn remove-first [syb lst] (let [[before after] (loop [b [] a lst] (if (empty? lst) [b a] (if (= syb (first a)) [b (rest a)] (recur (cons (first a) b) (rest a)] (concat (reverse before) after))) user=> (remove-first 4 '(1 5 3 4 2 6 674 4 2)) (1 5 3 2 6 674 4 2) I'm interested if somebody comes up with something more efficient, i.e. that doesn't require the reversal. Gary On Sat, Jul 24, 2010 at 11:41 AM, nickikt wrote: > Hallo all, > > I'm working trough Essentials of Programming Languages. I'm trying to > right a function like this one: > > (defn scheme-remove-first [syb lst] > (if (empty? lst) >'() >(if (= (first lst) syb) > (rest lst) > (cons (first lst) (scheme-remove-first syb (rest lst)) > > in a idiomatic clojure way (this is just a scheme to clojure 1:1 > version). I don't like that this function produces stack overflows. > > I tried some stuff but I it (almost) semantically correct working but > I didn't like my code. Can anyone come up with a good version? > > -- > 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 -- Gary Fredericks (660)-623-1095 fredericksg...@gmail.com www.gfredericks.com -- 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: Remove-first function
@Randy Hudson Really like that solution. @Mark Engelberg Thanks for the explanation On Jul 25, 4:33 am, ataggart wrote: > To add one small addendum to Mark's excellent comment, if you use lazy- > seq then you don't need to worry about the nil from when > > On Jul 24, 12:01 pm, Mark Engelberg wrote: > > > > > On Sat, Jul 24, 2010 at 11:45 AM, Mark Engelberg > > > wrote: > > > The simplest translation is to wrap a lazy-seq around the last line to > > > avoid the stack overflows. > > > Just to clarify, there are at least three reasonable places to place > > the call to lazy-seq. You can put lazy-seq around the full body of > > the function. You can place it around the cons. You can place it > > around the recursive call to scheme-remove-first. Each choice results > > in slightly different laziness behavior, i.e., when various elements > > are computed, but the overall semantics of the sequence remains the > > same and stack overflows will be avoided. Placing the lazy-seq around > > the recursive function call will cause scheme-remove-first to compute > > the first element right away, and delay the rest. Placing the > > lazy-seq around the full body will prevent any computation until it is > > asked for by a consumer. Placing the lazy-seq around the cons results > > in in immediate behavior for the nil and > > removable-item-at-front-of-list case, and delayed behavior otherwise. > > All are acceptable choices, but preferences vary. Probably placing > > lazy-seq around the full body is the most common style you'll see in > > Clojure, although I tend to place it where the laziness is actually > > required (like around the recursive call, or around the cons). > > > You've probably noticed from the other samples posted that many > > Clojurians prefer to use (seq lst) instead of (not (empty? lst)), and > > organize their code around the not-empty case. > > > So (if (empty? lst) empty-case not-empty-case) becomes (if (seq lst) > > not-empty-case empty-case) > > > When the empty case also results in nil, you can replace the if > > structure with a one-armed when, because when automatically returns > > nil in the other case. > > > So (if (seq lst) not-empty-case nil) becomes (when (seq lst) > > not-empty-case). -- 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: Remove-first function
To add one small addendum to Mark's excellent comment, if you use lazy- seq then you don't need to worry about the nil from when On Jul 24, 12:01 pm, Mark Engelberg wrote: > On Sat, Jul 24, 2010 at 11:45 AM, Mark Engelberg > > wrote: > > The simplest translation is to wrap a lazy-seq around the last line to > > avoid the stack overflows. > > Just to clarify, there are at least three reasonable places to place > the call to lazy-seq. You can put lazy-seq around the full body of > the function. You can place it around the cons. You can place it > around the recursive call to scheme-remove-first. Each choice results > in slightly different laziness behavior, i.e., when various elements > are computed, but the overall semantics of the sequence remains the > same and stack overflows will be avoided. Placing the lazy-seq around > the recursive function call will cause scheme-remove-first to compute > the first element right away, and delay the rest. Placing the > lazy-seq around the full body will prevent any computation until it is > asked for by a consumer. Placing the lazy-seq around the cons results > in in immediate behavior for the nil and > removable-item-at-front-of-list case, and delayed behavior otherwise. > All are acceptable choices, but preferences vary. Probably placing > lazy-seq around the full body is the most common style you'll see in > Clojure, although I tend to place it where the laziness is actually > required (like around the recursive call, or around the cons). > > You've probably noticed from the other samples posted that many > Clojurians prefer to use (seq lst) instead of (not (empty? lst)), and > organize their code around the not-empty case. > > So (if (empty? lst) empty-case not-empty-case) becomes (if (seq lst) > not-empty-case empty-case) > > When the empty case also results in nil, you can replace the if > structure with a one-armed when, because when automatically returns > nil in the other case. > > So (if (seq lst) not-empty-case nil) becomes (when (seq lst) not-empty-case). -- 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: Remove-first function
On Sat, Jul 24, 2010 at 11:45 AM, Mark Engelberg wrote: > The simplest translation is to wrap a lazy-seq around the last line to > avoid the stack overflows. Just to clarify, there are at least three reasonable places to place the call to lazy-seq. You can put lazy-seq around the full body of the function. You can place it around the cons. You can place it around the recursive call to scheme-remove-first. Each choice results in slightly different laziness behavior, i.e., when various elements are computed, but the overall semantics of the sequence remains the same and stack overflows will be avoided. Placing the lazy-seq around the recursive function call will cause scheme-remove-first to compute the first element right away, and delay the rest. Placing the lazy-seq around the full body will prevent any computation until it is asked for by a consumer. Placing the lazy-seq around the cons results in in immediate behavior for the nil and removable-item-at-front-of-list case, and delayed behavior otherwise. All are acceptable choices, but preferences vary. Probably placing lazy-seq around the full body is the most common style you'll see in Clojure, although I tend to place it where the laziness is actually required (like around the recursive call, or around the cons). You've probably noticed from the other samples posted that many Clojurians prefer to use (seq lst) instead of (not (empty? lst)), and organize their code around the not-empty case. So (if (empty? lst) empty-case not-empty-case) becomes (if (seq lst) not-empty-case empty-case) When the empty case also results in nil, you can replace the if structure with a one-armed when, because when automatically returns nil in the other case. So (if (seq lst) not-empty-case nil) becomes (when (seq lst) not-empty-case). -- 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: Remove-first function
The simplest translation is to wrap a lazy-seq around the last line to avoid the stack overflows. On Sat, Jul 24, 2010 at 8:41 AM, nickikt wrote: > (defn scheme-remove-first [syb lst] > (if (empty? lst) > '() > (if (= (first lst) syb) > (rest lst) > (cons (first lst) (scheme-remove-first syb (rest lst)) becomes (defn scheme-remove-first [syb lst] (if (empty? lst) '() (if (= (first lst) syb) (rest lst) (lazy-seq (cons (first lst) (scheme-remove-first syb (rest lst))) Also, you can omit the ' in front of the () if you like. -- 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: Remove-first function
Hi, One way to prevent the stack overflows is to wrap it in a lazy seq. For example: (defn remove-first [x coll] (lazy-seq (when (seq coll) (let [[y & ys] coll] (if (= target y) ys (cons y (remove-first x ys))) On Saturday 24 July 2010 11:41:58 nickikt wrote: > Hallo all, > > I'm working trough Essentials of Programming Languages. I'm trying to > right a function like this one: > > (defn scheme-remove-first [syb lst] > (if (empty? lst) > '() > (if (= (first lst) syb) > (rest lst) > (cons (first lst) (scheme-remove-first syb (rest lst)) > > in a idiomatic clojure way (this is just a scheme to clojure 1:1 > version). I don't like that this function produces stack overflows. > > I tried some stuff but I it (almost) semantically correct working but > I didn't like my code. Can anyone come up with a good version? -- 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: Remove-first function
Here's my take: (defn remove-first [x coll] (let [[pre post] (split-with #(not= x %) coll)] (concat (pre (rest post On Jul 24, 11:41 am, nickikt wrote: > Hallo all, > > I'm working trough Essentials of Programming Languages. I'm trying to > right a function like this one: > > (defn scheme-remove-first [syb lst] > (if (empty? lst) > '() > (if (= (first lst) syb) > (rest lst) > (cons (first lst) (scheme-remove-first syb (rest lst)) > > in a idiomatic clojure way (this is just a scheme to clojure 1:1 > version). I don't like that this function produces stack overflows. > > I tried some stuff but I it (almost) semantically correct working but > I didn't like my code. Can anyone come up with a good version? -- 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
Remove-first function
Hallo all, I'm working trough Essentials of Programming Languages. I'm trying to right a function like this one: (defn scheme-remove-first [syb lst] (if (empty? lst) '() (if (= (first lst) syb) (rest lst) (cons (first lst) (scheme-remove-first syb (rest lst)) in a idiomatic clojure way (this is just a scheme to clojure 1:1 version). I don't like that this function produces stack overflows. I tried some stuff but I it (almost) semantically correct working but I didn't like my code. Can anyone come up with a good version? -- 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
