Oh, vectors are indeed bad since vector concatenation is a linear time operation. My apologies to Meikel, I simply missed your remark about finger trees. I guess a version that swaps the values "in place" would be the way to go. On 30/12/2010, at 7:34 PM, Mark Engelberg wrote:
> On Wed, Dec 29, 2010 at 11:31 PM, David Nolen <dnolen.li...@gmail.com> wrote: >> The original algorithm is simply wrong for very large inputs, it cannot be >> TCO'ed. Pick a ridiculously large list size and the Scheme/Racket program >> will barf *immediately*. >> David > > Have you tried it? I tried this particular algorithm, in Racket, on > rather large lists. It runs seemingly forever (it is a quadratic > algorithm, of course), but I was unable to make Racket "barf > immediately". In my experience, Racket's more likely to fall over > from trying to create such a large input to begin with (simply because > there's not enough memory to hold a list that large) than it is to > barf from stack size while executing a non-TCO recursive function over > a list. My understanding is that Racket's key to handling non-TCO > recursion so gracefully is that it traps errors from stack overflows, > and swaps the stack out to memory to make room on the stack to > continue. So in essence, you get a stack that is bounded only by your > computer's memory (or whatever memory threshold you've enabled in the > settings). > > What size input is barfing for you? > > -- > 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 -- “There is a strong correlation between being smart and being a nerd, and an even stronger inverse correlation between being a nerd and being popular” (Paul Graham) -- ********************************************************** Andreas Koestler, Software Engineer Leica Geosystems Pty Ltd 270 Gladstone Road, Dutton Park QLD 4102 Main: +61 7 3891 9772 Direct: +61 7 3117 8808 Fax: +61 7 3891 9336 Email: andreas.koest...@leica-geosystems.com ************www.leica-geosystems.com************* when it has to be right, Leica Geosystems Please consider the environment before printing this email. -- 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
