Re: Non-tail recursion (Clojure way to hierarchies)
Thanks James. If any one else is as new to functional stuff as me then I found this in Paul Graham's book which enables me to reason logically about the matter (hopefully) A good compiler can compile a tail call into a goto, and so can compile a tail recursive function into a loop. In typical machine language code, when control arrives for the first time at the segment of instructions representing len (a local fn) there is information on the stack saying what to do upon returning. Because nothing remains to be done after the recursive call, this information remains valid for the second call as well On Jun 15, 11:28 pm, James Reeves jree...@weavejester.com wrote: On 15 June 2010 22:56, Quzanti quza...@googlemail.com wrote: Thanks Mike. So does is the only kind of recursion optimisation tail recursion? Can you only eliminate stack calls in tail calls? No, you can also eliminate stack calls using lazy-seq or trampolines. If you provide some example code of what you are currently doing, it would be easier to gauge what is the most suitable approach. You might not even need to bother eliminating stack calls, if you know you're never going to recurse very far. Having some sort of hint about this in the recur documentation might be helpful? Well, the docs do say recur in other than a tail position is an error, though that does assume the reader knows what the tail position of a function is. - James -- 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: Non-tail recursion (Clojure way to hierarchies)
I've looked at tree-seq and can say that is not suitable for non-tail children tasks. For example how can i attach subtotal row to bottom of each level. Any ideas? On 13 июн, 16:35, Andrzej ndrwr...@googlemail.com wrote: On Sun, Jun 13, 2010 at 7:35 PM, Oleg oleg.richa...@gmail.com wrote: Currently i'm just calling function, but there is a danger of StackOverflow. I can't use recur, because it's not last statement. As i can understand recur is good to build long sequences, but in my case i'm building hierarchy. Two potential solutions: 1. Build a lazy hierarchy, i.e. instead of returning a nested structure, return a function that produces it. It might be better to use a built-in function tree-seq though (check the implementation of file-seq and xml-seq). 2. If everything else fails use a trampolinehttp://groups.google.com/group/clojure/browse_frm/thread/6257cbc4454b... Cheers, Andrzej -- 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: Non-tail recursion (Clojure way to hierarchies)
On Tue, 15 Jun 2010 03:24:08 -0700 (PDT) Quzanti quza...@googlemail.com wrote: You can use recur to build a hierarchy. What do you mean by you can't use it as it is not the last statement? Exactly that. recur in some sense terminates the current call, and hence is required to be the last statement in the call. I have used recur in all sorts of places in the fn, without noticing any restrictions, and built hierarchies. The restriction is temporal, not spatial. You can put the recur statement anywhere you want, but there must be no other function waiting on it's return value. Or, if it weren't a special form, then it's value would be the value of the function. So this is legal, with the recur as the last function both temporally and spatially: (defn counter [n result] (if (zero? n) result (recur (dec n) (conj result n And moving the recur spatially still works: (defn counter2 [n result] (if ( n 0) (recur (dec n) (conj result n)) result)) But if we invert the conj and recur, so that conj uses the result of the recur, it breaks at compile time, even if the recur is spatially the last statement in the function: (defn busted-counter [n] (if (zero? n) [] (conj (recur (dec n)) n))) You can, of course, write this as a conventionally recursive function: (defn recursive-counter [n] (if (zero? n) [] (conj (recursive-counter (dec n)) n))) But this version *isn't* tail recursive - it'll use up n levels of stack. Personally, I like recur. Telling the language I believe this is a tail recursive call means it can tell me I was wrong at compile time, rather than after it runs out of stack out run time. I hope it stays around after we get TCE. mike -- Mike Meyer m...@mired.org http://www.mired.org/consulting.html Independent Network/Unix/Perforce consultant, email for more information. O ascii ribbon campaign - stop html mail - www.asciiribbon.org -- 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: Non-tail recursion (Clojure way to hierarchies)
On Sun, Jun 13, 2010 at 8:39 AM, Oleg oleg.richa...@gmail.com wrote:
Thank you, but could you provide me a little code snippet which will
iterate through collection and assoc children key for each row.
On 13 июн, 16:35, Andrzej ndrwr...@googlemail.com wrote:
On Sun, Jun 13, 2010 at 7:35 PM, Oleg oleg.richa...@gmail.com wrote:
Currently i'm just calling function, but there is a danger of
StackOverflow. I can't use recur, because it's not last statement. As
i can understand recur is good to build long sequences, but in my case
i'm building hierarchy.
Two potential solutions:
1. Build a lazy hierarchy, i.e. instead of returning a nested
structure, return a function that produces it. It might be better to
use a built-in function tree-seq though (check the implementation of
file-seq and xml-seq).
I think a lazy hierarchy is the way to go, but tree-seq is a way
to walk a tree, not build one.
For a real example of a lazy hierarchy, you can look at
clojure.contrib.lazy-xml, which builds a lazy tree of XML nodes.
But it may be hard to learn from without getting lost in SAX API
craziness, so here's an attempt at a simpler example:
First, a function to return some children for a given parent:
(defn children [parent]
(vec (map + (repeat (* 10 parent)) (range 10
(children 42)
;= [420 421 422 423 424 425 426 427 428 429]
Note this is a vector and thus non-lazy, just as in your problem
description.
Now we want a function that returns a tree node for a given item.
For this example a node will be just a map with an :item and
a lazy sequence of :kids:
(defn node [item]
{:item item
:kids (map node (children item))})
The fact that 'map' is lazy is critical here. If we force that
map when creating a node, our first call to 'node' will force the
whole tree and could have unbounded recursion. But 'map' is lazy
so we know that a single call to node will be O(1). Only when we
actually realize the :kids seq will 'children' be called.
We can now build a tree and look something up in it:
(- (node 0) :kids (nth 3) :kids (nth 5) :kids (nth 8) :item)
;= 358
So this is an infinitely deep tree that we can navigate without
any actual recursion, just as we can walk an infinite lazy seq
without recursion, and thus there's no threat that the stack will
overflow:
(:item (reduce #(nth (:kids %1) %2)
(node 0)
(take 5000 (cycle (range 10)
;= 123456789012345678...67890123456789
Note that since these trees are infinitely deep, a depth-first
walk like tree-seq does is probably not very useful:
(take 8 (map :item (tree-seq :kids :kids (node 1
;= (1 10 100 1000 1 10 100 1000)
Hope that helps!
--Chouser
http://joyofclojure.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: Non-tail recursion (Clojure way to hierarchies)
Thanks Mike. So does is the only kind of recursion optimisation tail recursion? Can you only eliminate stack calls in tail calls? Having some sort of hint about this in the recur documentation might be helpful? On Jun 15, 2:32 pm, Mike Meyer mwm-keyword-googlegroups. 620...@mired.org wrote: On Tue, 15 Jun 2010 03:24:08 -0700 (PDT) Quzanti quza...@googlemail.com wrote: You can use recur to build a hierarchy. What do you mean by you can't use it as it is not the last statement? Exactly that. recur in some sense terminates the current call, and hence is required to be the last statement in the call. I have used recur in all sorts of places in the fn, without noticing any restrictions, and built hierarchies. The restriction is temporal, not spatial. You can put the recur statement anywhere you want, but there must be no other function waiting on it's return value. Or, if it weren't a special form, then it's value would be the value of the function. So this is legal, with the recur as the last function both temporally and spatially: (defn counter [n result] (if (zero? n) result (recur (dec n) (conj result n And moving the recur spatially still works: (defn counter2 [n result] (if ( n 0) (recur (dec n) (conj result n)) result)) But if we invert the conj and recur, so that conj uses the result of the recur, it breaks at compile time, even if the recur is spatially the last statement in the function: (defn busted-counter [n] (if (zero? n) [] (conj (recur (dec n)) n))) You can, of course, write this as a conventionally recursive function: (defn recursive-counter [n] (if (zero? n) [] (conj (recursive-counter (dec n)) n))) But this version *isn't* tail recursive - it'll use up n levels of stack. Personally, I like recur. Telling the language I believe this is a tail recursive call means it can tell me I was wrong at compile time, rather than after it runs out of stack out run time. I hope it stays around after we get TCE. mike -- Mike Meyer m...@mired.org http://www.mired.org/consulting.html Independent Network/Unix/Perforce consultant, email for more information. O ascii ribbon campaign - stop html mail -www.asciiribbon.org -- 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: Non-tail recursion (Clojure way to hierarchies)
On 15 June 2010 22:56, Quzanti quza...@googlemail.com wrote: Thanks Mike. So does is the only kind of recursion optimisation tail recursion? Can you only eliminate stack calls in tail calls? No, you can also eliminate stack calls using lazy-seq or trampolines. If you provide some example code of what you are currently doing, it would be easier to gauge what is the most suitable approach. You might not even need to bother eliminating stack calls, if you know you're never going to recurse very far. Having some sort of hint about this in the recur documentation might be helpful? Well, the docs do say recur in other than a tail position is an error, though that does assume the reader knows what the tail position of a function is. - James -- 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: Non-tail recursion (Clojure way to hierarchies)
On Tue, Jun 15, 2010 at 3:28 PM, James Reeves jree...@weavejester.com wrote: Well, the docs do say recur in other than a tail position is an error, though that does assume the reader knows what the tail position of a function is. see, for example, @tailrec in scala. -- 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
Non-tail recursion (Clojure way to hierarchies)
Hello Guys! Here is the task: Assume that we have function called `fetch-from-source`, which used to fetch vector of maps from the data source. I want to make iteration on every fetched row (element of vector) and ask `fetch-from-source` again to add 'children' key to that row. And so on, until given depth. So i want to use map function on collection from some function `expand- groups`, which will call the same function `expand-groups` on every collection element to assign children on it. Keep in mind, that the map function is not last in my function, because i have to append one more row to mapped collection. Currently i'm just calling function, but there is a danger of StackOverflow. I can't use recur, because it's not last statement. As i can understand recur is good to build long sequences, but in my case i'm building hierarchy. What do you think guys? Is there are clojure-rish way to solve that problem? Cheers, Oleg -- 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: Non-tail recursion (Clojure way to hierarchies)
On Sun, Jun 13, 2010 at 7:35 PM, Oleg oleg.richa...@gmail.com wrote: Currently i'm just calling function, but there is a danger of StackOverflow. I can't use recur, because it's not last statement. As i can understand recur is good to build long sequences, but in my case i'm building hierarchy. Two potential solutions: 1. Build a lazy hierarchy, i.e. instead of returning a nested structure, return a function that produces it. It might be better to use a built-in function tree-seq though (check the implementation of file-seq and xml-seq). 2. If everything else fails use a trampoline http://groups.google.com/group/clojure/browse_frm/thread/6257cbc4454bcb85/7d5fd827cd549080#7d5fd827cd549080 Cheers, Andrzej -- 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: Non-tail recursion (Clojure way to hierarchies)
Thank you, but could you provide me a little code snippet which will iterate through collection and assoc children key for each row. On 13 июн, 16:35, Andrzej ndrwr...@googlemail.com wrote: On Sun, Jun 13, 2010 at 7:35 PM, Oleg oleg.richa...@gmail.com wrote: Currently i'm just calling function, but there is a danger of StackOverflow. I can't use recur, because it's not last statement. As i can understand recur is good to build long sequences, but in my case i'm building hierarchy. Two potential solutions: 1. Build a lazy hierarchy, i.e. instead of returning a nested structure, return a function that produces it. It might be better to use a built-in function tree-seq though (check the implementation of file-seq and xml-seq). 2. If everything else fails use a trampolinehttp://groups.google.com/group/clojure/browse_frm/thread/6257cbc4454b... Cheers, Andrzej -- 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
