tag:blogger.com,1999:blog-7056990295646173627.post9107219843401475775..comments2020-01-23T16:40:31.968+00:00Comments on Learning Clojure: take-while-unstableJohn Lawrence Aspdenhttp://www.blogger.com/profile/02587130870181071109noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-7056990295646173627.post-20855560493107358282011-06-12T08:52:27.386+01:002011-06-12T08:52:27.386+01:00Hmm, if we're talking about sequences like (it...Hmm, if we're talking about sequences like (iterate f x0) then that double-advance technique is very cool.<br /><br />Surely it's O(n) space if you're keeping pointers, because you need to hold the sequence in between? But if the function's not expensive you could keep two separate values and iterate them separately, I think.<br /><br />If the function is expensive then the best scheme may be to keep all the values so far in a b-tree or hash and look up each one to see if we've already been there.<br /><br />Either way there'll be lots of operations per logical step, so I think the factor of 2 is a little optimistic.John Lawrence Aspdenhttps://www.blogger.com/profile/02587130870181071109noreply@blogger.comtag:blogger.com,1999:blog-7056990295646173627.post-7317619568816599992011-06-11T21:57:27.194+01:002011-06-11T21:57:27.194+01:004 2 1 4 2 1 ... has period 3, obviously, assuming ...4 2 1 4 2 1 ... has period 3, obviously, assuming x_n = f(x_{n-1}). So I suppose you were talking about systems where there is some hidden state that could cause the sequence to go haywire later on down the line. I'm just imagining iterating pure, deterministic functions. <br /><br />The computational complexity I'm thinking of is: "if there is a repeat of length n after m steps, how quickly can you detect it?"<br /><br />Advancing two pointers, one twice as fast as the other, and comparing if their values are ever equal, is an O(n) repeat-detector, with constant space complexity. But the constant in front of n is "2". I wonder if there is a better balance between space and time complexity if you have prior information about m and n.taliesinhttps://www.blogger.com/profile/04584738046480528572noreply@blogger.comtag:blogger.com,1999:blog-7056990295646173627.post-38918887191208533622011-01-27T12:04:00.727+00:002011-01-27T12:04:00.727+00:00It's probably got to be order infinity. I mean...It's probably got to be order infinity. I mean, has this sequence started cycling yet? 4 2 1 4 2 1 4 2 1 . . . .<br /><br />If you're just looking for repeats, then (order (* range (log range))) sounds about right. An interesting question for Collatz.<br /><br />Although of course for Collatz itself, all you need to check is whether the thing has come back to below its starting point.<br /><br />Joy of Clojure's jolly good!<br />For maths look to the haskellloons.John Lawrence Aspdenhttps://www.blogger.com/profile/02587130870181071109noreply@blogger.comtag:blogger.com,1999:blog-7056990295646173627.post-78986995817022703472011-01-27T08:25:25.359+00:002011-01-27T08:25:25.359+00:00Mathematica has this same function, except it'...Mathematica has this same function, except it's called FixedPoint (and it has a cousin called FixedPointList). Mathematica actually has a kick ass library of higher order functions, so far the best I've seen of any functional language, though I'm by no means a guru.<br /> <br />But with Collatz you have cycles. A nifty higher order function would be one that efficiently detects cycles and terminates as soon as one is recognized. Would that have to be O(n)? I'm not sure, certainly one can always trade-off time for space by keeping pointers to previous iterates, like a rainbow table does.<br /><br />Do you happen to know of any resources that specialize in enumerating and discussing some of these higher order functions? I feel like that is the next step to being a productive functional language programmer: having memorized tens or hundreds of these higher order functions as well as knowing exactly when and where they can be applied to simplify a problem.Taliesin Beynonhttp://selfishmeme.posterous.comnoreply@blogger.com