Re: Please help! Really simple function not working.
On Tue, Aug 10, 2010 at 11:23 AM, Will M. Farr wrot> > Sorry for the digression; I hope people find it interesting. I found it interesting. -- 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: Please help! Really simple function not working.
Maybe this point about Racket is too off-topic for the list, but: On Aug 10, 2010, at 4:55 AM, Mark Engelberg wrote: > Generally speaking, I find I do not have to worry about "blowing the > stack" in Scheme, and as a result, non-tail-call structural recursion > (such as the algorithm that kicked off this thread) is perfectly > idiomatic in the implementations of Scheme I have used (mostly > Racket). In Clojure, I find stack limitations are a real issue unless > I transform the algorithms into a tail-recursive accumulator style. > For lists, it's usually not hard. For trees, it can be a bit of a > pain. You don't worry about blowing the stack in Racket with recursion because they implement stack copying particularly elegantly: when you are about to blow the stack, the stack is copied to the heap and then blown away. A "handler" procedure is called (i.e. placed on the top of the stack), and then your computation proceeds. When you return your way back to the handler, it recalls the previous stack from the heap, jumps to the bottom of it, and your computation proceeds. In effect, the stack is treated as a limited-size window into the heap, so you will never run out of stack until you run out of heap. It's a neat trick, and could (in principle) be done on the JVM, but probably involves a significant speed trade-off even for code that doesn't take advantage of it. (The only way I can think of doing it is to follow the process outlined in "Continuations from Generalized Stack Inspection" by the PLT Folks, which requires installing an exception handler around each procedure to catch stack-overflow exceptions and "re-build" the current continuation on the heap.) I suspect that Chicken, with its "the Stack is the first generation of a copying generational garbage collector" would also have this "unlimited stack" property, but I don't know about the other Schemes---it's certainly standards complying to blow up when you run out of stack. Sorry for the digression; I hope people find it interesting. Will -- 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: Please help! Really simple function not working.
The table show 20!. I am far from being sure of my point, but in a first approximation: Loading a part of memory that is not cached (which will be the case for big lists) is around 300 cycles. An addition in a register is a few cycles, a jump is a few cycles too, at most, (the prediction will be good here). Of course, it is only guess. And, if you really count the time to get through a line of cache adding one, it might not be negligeable in regard of the time to load cache, but I think it will have an impact. -- 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: Please help! Really simple function not working.
Hi, On Aug 10, 11:34 am, Mark Engelberg wrote: > The table shows that the performance of the accumulator-style version > of factorial is always worse than that of the original factorial > function." I'm a little bit surprised, that people still prefer programs, which are only sometimes not broken, over programs which work always correctly. 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: Please help! Really simple function not working.
On Tue, Aug 10, 2010 at 2:21 AM, Nicolas Oury wrote: > It would probably be up to twice as slow, I would say. > For a list that is continuous in memory and continuations that are > allocated perfectly in memory, > you would need to go through twice the same amount of memory. > (I assume that the main cost here is going through the memory) I don't think this is true. See comment at bottom of http://www.htdp.org/2001-09-22/Book/node163.htm: "People who encounter accumulator-style programming for the first time often get the impression that they are always faster or easier to understand (design) than their recursive counterparts. Both parts are plain wrong. While it is impossible to deal with the full scope of the mistake, let us take a look at a small counterexample. Consider the following table: [Go to link to see table] ... The table shows that the performance of the accumulator-style version of factorial is always worse than that of the original factorial function." -- 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: Please help! Really simple function not working.
2010/8/10 Laurent PETIT > > > 2010/8/10 Nicolas Oury > > On Tue, Aug 10, 2010 at 10:08 AM, Laurent PETIT >> wrote: >> > Naive question from someone who has not really used Scheme in practice : >> > beyond the memory footprint problem (which may or may not be a problem >> > depending on the memory size of an element in the initial list, and also >> > depending on whether you're recurring over a datastructure, or a >> presumably >> > very long lazy seq), isn't there an impact on CPU usage too ? >> >> It would probably be up to twice as slow, I would say. >> For a list that is continuous in memory and continuations that are >> allocated perfectly in memory, >> you would need to go through twice the same amount of memory. >> (I assume that the main cost here is going through the memory) >> > > > Isn't this improbable (your assumption about the main cost) ? Even for the > smallest accumulating computation such as doing an addition or consing > things (which requires memory allocation, etc.), I'm not certain that there > wouldn't be near-to-an-order-of-magnitude between the "going through the > memory" and the "accumulator computation" ? > The more I think about it, the more I tend to consider that it's just the memory footprint of ( size of an intermediate result x number of elements of the coll ) which counts. With the caveat that sometimes saying "if the coll can stay in memory and the size of an intermediate result is negligeable compared to the size of an element of the coll, everything's ok" may not work if we're not really holding the coll in memory, but rather computing a very long lazy seq / lazy tree. -- 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: Please help! Really simple function not working.
2010/8/10 Nicolas Oury > On Tue, Aug 10, 2010 at 10:08 AM, Laurent PETIT > wrote: > > Naive question from someone who has not really used Scheme in practice : > > beyond the memory footprint problem (which may or may not be a problem > > depending on the memory size of an element in the initial list, and also > > depending on whether you're recurring over a datastructure, or a > presumably > > very long lazy seq), isn't there an impact on CPU usage too ? > > It would probably be up to twice as slow, I would say. > For a list that is continuous in memory and continuations that are > allocated perfectly in memory, > you would need to go through twice the same amount of memory. > (I assume that the main cost here is going through the memory) > Isn't this improbable (your assumption about the main cost) ? Even for the smallest accumulating computation such as doing an addition or consing things (which requires memory allocation, etc.), I'm not certain that there wouldn't be near-to-an-order-of-magnitude between the "going through the memory" and the "accumulator computation" ? -- 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: Please help! Really simple function not working.
On Tue, Aug 10, 2010 at 10:08 AM, Laurent PETIT wrote: > Naive question from someone who has not really used Scheme in practice : > beyond the memory footprint problem (which may or may not be a problem > depending on the memory size of an element in the initial list, and also > depending on whether you're recurring over a datastructure, or a presumably > very long lazy seq), isn't there an impact on CPU usage too ? It would probably be up to twice as slow, I would say. For a list that is continuous in memory and continuations that are allocated perfectly in memory, you would need to go through twice the same amount of memory. (I assume that the main cost here is going through the memory) -- 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: Please help! Really simple function not working.
On Tue, Aug 10, 2010 at 9:55 AM, Mark Engelberg wrote: > In Clojure, I find stack limitations are a real issue unless > I transform the algorithms into a tail-recursive accumulator style. > For lists, it's usually not hard. For trees, it can be a bit of a > pain. Try CPS+trampoline It is more or less what scheme does internally... -- 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: Please help! Really simple function not working.
Hello Mark, 2010/8/10 Mark Engelberg > On Tue, Aug 10, 2010 at 1:15 AM, Nicolas Oury > wrote: > > So, in this particular case, Scheme does not warranty no exhaustion > > of resources. > > Yes, but your recursion depth is limited to the length of the list you > are processing. So if you have enough resources to comfortably hold > and manipulate the list in memory, odds are good you have enough > resources to handle the non-tail recursive processing of the list. > > Generally speaking, I find I do not have to worry about "blowing the > stack" in Scheme, and as a result, non-tail-call structural recursion > (such as the algorithm that kicked off this thread) is perfectly > idiomatic in the implementations of Scheme I have used (mostly > Racket). Naive question from someone who has not really used Scheme in practice : beyond the memory footprint problem (which may or may not be a problem depending on the memory size of an element in the initial list, and also depending on whether you're recurring over a datastructure, or a presumably very long lazy seq), isn't there an impact on CPU usage too ? > In Clojure, I find stack limitations are a real issue unless > I transform the algorithms into a tail-recursive accumulator style. > For lists, it's usually not hard. For trees, it can be a bit of a > pain. > oh yes :-) > > Since Clojure has a lot of similarities with Scheme, this is a key > difference that needs to be emphasized to people coming from Scheme or > using a Scheme-based textbook to try to learn Clojure. > > -- > 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 > -- 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: Please help! Really simple function not working.
On Tue, Aug 10, 2010 at 1:15 AM, Nicolas Oury wrote: > So, in this particular case, Scheme does not warranty no exhaustion > of resources. Yes, but your recursion depth is limited to the length of the list you are processing. So if you have enough resources to comfortably hold and manipulate the list in memory, odds are good you have enough resources to handle the non-tail recursive processing of the list. Generally speaking, I find I do not have to worry about "blowing the stack" in Scheme, and as a result, non-tail-call structural recursion (such as the algorithm that kicked off this thread) is perfectly idiomatic in the implementations of Scheme I have used (mostly Racket). In Clojure, I find stack limitations are a real issue unless I transform the algorithms into a tail-recursive accumulator style. For lists, it's usually not hard. For trees, it can be a bit of a pain. Since Clojure has a lot of similarities with Scheme, this is a key difference that needs to be emphasized to people coming from Scheme or using a Scheme-based textbook to try to learn Clojure. -- 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: Please help! Really simple function not working.
On Tue, Aug 10, 2010 at 2:40 AM, Mark Engelberg wrote: > arbitrary-sized lists is a primary goal. The posted code (minus the > call to recur), is an elegant recursive formulation that is idiomatic > in Scheme because Scheme is (typically) implemented in a way that > makes stack limitations (mostly) a non-issue. > > In Clojure, you have to work around stack limitations imposed by Java, > and recursive functions must be "translated" to work on largish lists > in Clojure. There is no one recipe to make that translation, but > there are several common patterns. If the recursive call is in tail I want to add a little bit of information. (I am not a specialist of Scheme but believe what follow to be true) The original function minus recur + a recursive call on the second cond is not tail-recursive. So, in this particular case, Scheme does not warranty no exhaustion of resources. (A lot of Scheme implementation, and SML/NJ I believe, are CPS-compiled and will exhaust heap and not stack but those that are based on Lazy Stack copying would probably exhaust stack). Anyway, this implementation - in any language - would still eat memory, constructing a long stack-allocated (or heap-allocated in most Scheme and SML/NJ) list of continuations to remember "what to do when I have finished". In more fancy term, whether on the stack and on the heap, you need to keep a list of "continuations" to the computation. "When I am at the end of the list, I will add one, and then add one, and then add one " A tail-call has the particularity to have a trivial continuation: "I take the result and return it", so you don't have to actually keep any information. Most functional languages optimise this, but those on the JVM have a hard time doing it, because the way the JVM works. Scheme warranties it. You are not a Scheme implementation if you do not do tail-call optimisation. Clojure does it, for self recursion, when you explicitly ask for it, emitting a compile-time error if it can't. I think it is a good idea, because sometimes you write the function lightly badly and do not realise tail-call optimisation do not happen until a bug in production. There are ways to transform a call in tail-call. Adding an accumulator, using a list passed as argument as a stack, or doing a Continuation passing Style transformation. (http://en.wikipedia.org/wiki/Continuation-passing_style , in a word: to put the future in a closure we pass to the recursive call.) It is harder to transform a program to only self tail-call, but I think CPS+trampoline always do the trick. (Without the restriction to only do self calls, CPS does always the trick) Best regards, Nicolas. -- 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: Please help! Really simple function not working.
2010/8/10 Laurent PETIT > 2010/8/10 Meikel Brandmeyer > >> Hi, >> >> >> On Aug 10, 9:36 am, Laurent PETIT wrote: >> >> > Interesting ! Though it seems like a repetition in this case ... >> >> Indeed. However, eg. with multimethods this a nice-to-know to supply >> some meaningful argument info. >> > > Indeed ! > And with macro generating macros too ! -- 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: Please help! Really simple function not working.
2010/8/10 Meikel Brandmeyer > Hi, > > On Aug 10, 9:36 am, Laurent PETIT wrote: > > > Interesting ! Though it seems like a repetition in this case ... > > Indeed. However, eg. with multimethods this a nice-to-know to supply > some meaningful argument info. > Indeed ! -- 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: Please help! Really simple function not working.
Hi, On Aug 10, 9:36 am, Laurent PETIT wrote: > Interesting ! Though it seems like a repetition in this case ... Indeed. However, eg. with multimethods this a nice-to-know to supply some meaningful argument info. 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: Please help! Really simple function not working.
2010/8/10 Meikel Brandmeyer
> Hi,
>
> On Aug 10, 8:22 am, Laurent PETIT wrote:
>
> > Though here, the version with different arities "exposes as API for the
> > user" the 2-arity version, but it may not make sense for the user of your
> > function to know about this 2-arity version. I personally prefer the
> first
> > approach (with a private helper function via defn-) or the last approach
> > (with an embedded loop).
>
> One can also remove the multiple arities from the contract.
>
> (defn count-zeros
> {:arglists '([coll])}
> ([coll] (count-zeros coll 0))
> ([coll result]
> ...))
>
>
Interesting ! Though it seems like a repetition in this 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: Please help! Really simple function not working.
Hi,
On Aug 10, 8:22 am, Laurent PETIT wrote:
> Though here, the version with different arities "exposes as API for the
> user" the 2-arity version, but it may not make sense for the user of your
> function to know about this 2-arity version. I personally prefer the first
> approach (with a private helper function via defn-) or the last approach
> (with an embedded loop).
One can also remove the multiple arities from the contract.
(defn count-zeros
{:arglists '([coll])}
([coll] (count-zeros coll 0))
([coll result]
...))
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: Please help! Really simple function not working.
2010/8/10 David Sletten > > On Aug 10, 2010, at 2:22 AM, Laurent PETIT wrote: > > > >> You could accomplish pretty much the same thing by defining two versions >> with different arities: >> (defn count-zeros >> ([l] (count-zeros l 0)) >> ([l result] >> (cond (empty? l) result >>(zero? (first l)) (recur (rest l) (inc result)) >>:else (recur (rest l) result >> > > Though here, the version with different arities "exposes as API for the > user" the 2-arity version, but it may not make sense for the user of your > function to know about this 2-arity version. I personally prefer the first > approach (with a private helper function via defn-) or the last approach > (with an embedded loop). > > > Hence "pretty much the same thing". :) > Sure, since the OP is new to clojure, I thought giving this "guideline" could be of help to him, Cheers, -- Laurent > > Have all good days, > David Sletten > > > > > -- > 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 > -- 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: Please help! Really simple function not working.
On Aug 10, 2010, at 2:22 AM, Laurent PETIT wrote: > > > You could accomplish pretty much the same thing by defining two versions with > different arities: > (defn count-zeros > ([l] (count-zeros l 0)) > ([l result] > (cond (empty? l) result >(zero? (first l)) (recur (rest l) (inc result)) >:else (recur (rest l) result > > Though here, the version with different arities "exposes as API for the user" > the 2-arity version, but it may not make sense for the user of your function > to know about this 2-arity version. I personally prefer the first approach > (with a private helper function via defn-) or the last approach (with an > embedded loop). Hence "pretty much the same thing". :) Have all good days, David Sletten -- 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: Please help! Really simple function not working.
Hi, 2010/8/10 David Sletten > Carlos, > > I think this is pretty much what you had in mind: > (defn count-zeros [l] > (cond (empty? l) 0 > (zero? (first l)) (inc (count-zeros (rest l))) > :else (count-zeros (rest l > > (count-zeros '(9 8 6 0 1 2 0 5)) => 2 > (count-zeros '(9 8 6)) => 0 > (count-zeros '()) => 0 > > Of course the above version is not tail-recursive. However, once you're > written a straightforward recursive function it is often easy to see how to > rewrite it (using an accumulator here) to take advantage of Clojure's recur: > (declare count-zeros-aux) > > (defn count-zeros [l] > (count-zeros-aux l 0)) > > (defn- count-zeros-aux [l result] > (cond (empty? l) result > (zero? (first l)) (recur (rest l) (inc result)) > :else (recur (rest l) result))) > > Here the base function presents the same interface to the user, and the > private auxiliary function takes an additional accumulator argument. > > You could accomplish pretty much the same thing by defining two versions > with different arities: > (defn count-zeros > ([l] (count-zeros l 0)) > ([l result] > (cond (empty? l) result >(zero? (first l)) (recur (rest l) (inc result)) >:else (recur (rest l) result > Though here, the version with different arities "exposes as API for the user" the 2-arity version, but it may not make sense for the user of your function to know about this 2-arity version. I personally prefer the first approach (with a private helper function via defn-) or the last approach (with an embedded loop). Cheers, -- Laurent > > Or you could simplify things by using loop: > (defn count-zeros [l] > (loop [num-list l > result 0] > (cond (empty? num-list) result > (zero? (first num-list)) (recur (rest num-list) (inc result)) > :else (recur (rest num-list) result > > Have all good days, > David Sletten > > On Aug 9, 2010, at 8:24 PM, Carlos Torres wrote: > > Hi to everyone, > > I'm trying to create a function that takes a simple list and returns the > number of zeros in the list. > So I'm assuming that they will enter a list containing only numbers. > This is what I have so far, but it only works when the list empty. Can > somebody tell me what I'm missing? > > (defn count-zeros > "Returns the numbers of zero in a simple sequence of numbers" > [list1] > (cond > (empty? list1) 0 > (not (zero? (first list1))) 0 > :else > (recur (+ 1 (count-zeros (rest list1)) > > --Carlos > > -- > 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 > > > > > > > > > -- > 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 > -- 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: Please help! Really simple function not working.
Carlos, I think this is pretty much what you had in mind: (defn count-zeros [l] (cond (empty? l) 0 (zero? (first l)) (inc (count-zeros (rest l))) :else (count-zeros (rest l (count-zeros '(9 8 6 0 1 2 0 5)) => 2 (count-zeros '(9 8 6)) => 0 (count-zeros '()) => 0 Of course the above version is not tail-recursive. However, once you're written a straightforward recursive function it is often easy to see how to rewrite it (using an accumulator here) to take advantage of Clojure's recur: (declare count-zeros-aux) (defn count-zeros [l] (count-zeros-aux l 0)) (defn- count-zeros-aux [l result] (cond (empty? l) result (zero? (first l)) (recur (rest l) (inc result)) :else (recur (rest l) result))) Here the base function presents the same interface to the user, and the private auxiliary function takes an additional accumulator argument. You could accomplish pretty much the same thing by defining two versions with different arities: (defn count-zeros ([l] (count-zeros l 0)) ([l result] (cond (empty? l) result (zero? (first l)) (recur (rest l) (inc result)) :else (recur (rest l) result Or you could simplify things by using loop: (defn count-zeros [l] (loop [num-list l result 0] (cond (empty? num-list) result (zero? (first num-list)) (recur (rest num-list) (inc result)) :else (recur (rest num-list) result Have all good days, David Sletten On Aug 9, 2010, at 8:24 PM, Carlos Torres wrote: > Hi to everyone, > > I'm trying to create a function that takes a simple list and returns the > number of zeros in the list. > So I'm assuming that they will enter a list containing only numbers. > This is what I have so far, but it only works when the list empty. Can > somebody tell me what I'm missing? > > (defn count-zeros > "Returns the numbers of zero in a simple sequence of numbers" > [list1] > (cond > (empty? list1) 0 > (not (zero? (first list1))) 0 > :else > (recur (+ 1 (count-zeros (rest list1)) > > --Carlos > > -- > 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 -- 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: Please help! Really simple function not working.
On Mon, Aug 9, 2010 at 9:00 PM, Phil Hagelberg wrote: > On Mon, Aug 9, 2010 at 5:24 PM, Carlos Torres > wrote: > > (defn count-zeros > > "Returns the numbers of zero in a simple sequence of numbers" > > [list1] > > (cond > > (empty? list1) 0 > > (not (zero? (first list1))) 0 > > :else > > (recur (+ 1 (count-zeros (rest list1)) > > Michael's solution works too, but the problem here is that you're > calling recur in a way that doesn't make sense. You'd want to replace > the call to count-zeros with recur rather than calling both, but it's > not in the tail-position, so it can't be TCO'd. > > Just remove the call to recur and it will work, albeit only for lists > small enough to not blow the stack. > > -Phil > > -- > 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 > I totally forgot about how to use recur. Thanks to all for the fast help and for pointing out my errors, and even suggesting corrections and alternatives. This is by far the best mailing list I've ever participated in. As you can see I'm still learning Clojure, and I've a long way to go to master it. Again thank you all for your help. --Carlos -- 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: Please help! Really simple function not working.
On Mon, Aug 9, 2010 at 6:00 PM, Phil Hagelberg wrote: > Just remove the call to recur and it will work, albeit only for lists > small enough to not blow the stack. I'm assuming from the tone of the original post that the author is trying to generally understand how to write recursive functions in Clojure, rather than use built-ins, and that processing arbitrary-sized lists is a primary goal. The posted code (minus the call to recur), is an elegant recursive formulation that is idiomatic in Scheme because Scheme is (typically) implemented in a way that makes stack limitations (mostly) a non-issue. In Clojure, you have to work around stack limitations imposed by Java, and recursive functions must be "translated" to work on largish lists in Clojure. There is no one recipe to make that translation, but there are several common patterns. If the recursive call is in tail position, you can usually write the function the same way, but replace the self-call with the word "recur". If not in tail position and the function is a list-building function, you may be able to solve the stack problem with a call to lazy-seq -- I touched on this topic in a recent blog post: http://programming-puzzler.blogspot.com/2010/07/translating-code-from-python-and-scheme.html The solution to most recursive problems in Clojure is to build your answer in an accumulator, so you must learn how to design and develop accumulator-style recursive functions. For an in-depth look at this process (in Scheme), I recommend: http://www.htdp.org/2001-11-21/Book/node156.htm For mutually recursive problems, a trampoline may be an option. If none of these options work, you may have to simulate your own call stack (ugh). It can sometimes be frustrating to write code in a language that is built around recursion rather than iteration constructs, and then has such severe limitations on how and when recursion can be safely used, but with practice, the vast majority of code can be easily rewritten in a manner conducive to Clojure. -- 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: Please help! Really simple function not working.
On Mon, Aug 9, 2010 at 5:24 PM, Carlos Torres wrote: > (defn count-zeros > "Returns the numbers of zero in a simple sequence of numbers" > [list1] > (cond > (empty? list1) 0 > (not (zero? (first list1))) 0 > :else > (recur (+ 1 (count-zeros (rest list1)) Michael's solution works too, but the problem here is that you're calling recur in a way that doesn't make sense. You'd want to replace the call to count-zeros with recur rather than calling both, but it's not in the tail-position, so it can't be TCO'd. Just remove the call to recur and it will work, albeit only for lists small enough to not blow the stack. -Phil -- 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: Please help! Really simple function not working.
2010/8/10 Carlos Torres > Hi to everyone, > > I'm trying to create a function that takes a simple list and returns the > number of zeros in the list. > So I'm assuming that they will enter a list containing only numbers. > This is what I have so far, but it only works when the list empty. Can > somebody tell me what I'm missing? > > (defn count-zeros > "Returns the numbers of zero in a simple sequence of numbers" > [list1] > (cond > (empty? list1) 0 > (not (zero? (first list1))) 0 > :else > (recur (+ 1 (count-zeros (rest list1)) > Hi Carlos, your function can be written: (defn count-zeros [l] (reduce #(if (zero? %2) (inc %1) %1) 0 l)) or less cryptic with variable names (defn count-zeros [l] (reduce (fn [nb-zeros elem] (if (zero? elem) (inc nb-zeros) nb-zeros)) 0 l)) But if you really want to write it recursively, then you must understand you cannot recur with the partial sum when your function expects a list. And it does not make sense to recur and call count-zeros at the same time. here is a working version, using recur: (defn count-zeros [list1] (loop [list1 (seq list1) nb-zeros 0] (if list1 (recur (next list1) (if (zero? (first list1)) (inc nb-zeros) nb-zeros)) nb-zeros))) HTH, -- Laurent -- 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: Please help! Really simple function not working.
On Mon, Aug 9, 2010 at 5:24 PM, Carlos Torres wrote: > Hi to everyone, > I'm trying to create a function that takes a simple list and returns the > number of zeros in the list. > So I'm assuming that they will enter a list containing only numbers. > This is what I have so far, but it only works when the list empty. Can > somebody tell me what I'm missing? > (defn count-zeros > "Returns the numbers of zero in a simple sequence of numbers" > [list1] > (cond > (empty? list1) 0 > (not (zero? (first list1))) 0 > :else > (recur (+ 1 (count-zeros (rest list1)) > --Carlos I believe your second codition break the recursion but in general, don't write your own unless you are learning how to write recursive code in clojure. this is textbook filter then count or foldl(i.e. reduce). -- 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: Please help! Really simple function not working.
On Aug 9, 2010, at 7:24 PM, Carlos Torres wrote: > I'm trying to create a function that takes a simple list and returns the > number of zeros in the list. user=> (count (filter zero? [0 1 2 3 0 4 5 6 0 7 8 9])) 3 -- 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
