no plus ones
View 11 previous comments
- And here's the fix for the excess x element:
then List.rev t
else it (n-1) f (f x :: f x :: t)
I got there by shifting the argument list and pulling the last element out from the then to the else expression. Everyone: practice equivalence transformations!51w
- Xah Lee+1thanks. I'll comment later. Be sure your code works correctly! It is returning a list, each element is the nth iteration of f, right? because it takes a lot time for me to try to run and read the code.
originally, i find this problem interesting, because it allows programing features to be used.
(it's easy to write the function per spec. But we need to look at efficiency (cpu and memory space), and elegance. The elegance part, language features would shine thru!
and there are many way to code this.
I was looking for how other people deal with keeping the accumulated list, and keeping it outside function arg or global var (or using closure), and or whether people make just 1 definition or 2.
looking at your code, you use the arg to accumulate list, and define a alt function that doesn't. That's interesting. And you use push to add to list. (as opposed some sort of functional map, possibly builtin in the lang, that doesn't need to add to list each time.) (e.g. Mathematica has NestList builtin. Just call NestList[f,x,n])51w
- I have tried my second implementation in the interpreter, you can find the session log in an earlier comment above!
Between # and ;; you see what I typed in, the function's type comes after "val it :", it's a polymorphic function that is agnostic about the type of x as long as it matches f's type. 'a is a named placeholder that fits all constraints it appears in.
At the end there's a string of digits. I called my function with n=5 and addition with one as f. The result shows a bug, 0 should not be in there! See my following comments for the fix.
Ocaml comes with fold/map primitives for lists and its other data structures, but not for counting loops or the case you describe in Mathematica. So I had to write my own. You can always transform for loops to tail recursion:
// a loop in js:
for(var i=0, x=7; i < 10; i+=1)
x = funky(i, x);
// in ocaml:
let rec f (i, x) =
if i < 10
then f (i+1, funky i x)
else (i, x)
in f (0, 7)
Note how initialization, comparison, increment and the funky call appear almost identically. Technically, you don't need to return a pair in the else, but I left it in there in analogy to using List.fold_left to do funky computations while iterating a list:
List.fold_left (fun (i, x) ele –>
i+1, funkier i x ele
Just use a tuple for all loop variables! I think you can already see how to 'break' a loop, 'continue' amounts to simply doing another tail-recursive call.51w
- Constants are best, then nonrecursive, then primitive recursive, then tail-recursive. Use general recursion only if you must! I rarely need it.
Edit: I just inserted primitive recursive above, as you can do all while loops as tail-recursive functions... You really want the primitive ones, but ocaml isn't of much help here. However, it's what you do in Coq: all types need to be grounded. If they aren't, Coq complains.
- This is a dynamic programming problem, a basic one. Essentially, you store previous f(x) and use it as the input to the current f(x) and so on. If you want to solve these kinds of problems, you should try Codeforces: http://codeforces.com/. You might enjoy it.
There will be much more difficult problems.
return x + 1
l = 
for i in range(n):
x = f(x)
n = 100
x = 1
l = r(x,f,n)
for i in range(n):
sys.stdout.write(str(l[i]) + " ")51w
- If you want recursive solution, it can be written esily: simply cache the previous call and return, without recursing further. e.g. f(x) = 2, then f(f(x)) = f(2) = 3 and so on.51w
Add a comment...