Quiz. write a function r(f,x,n) that returns a list [f(x), f(f(x)), ...], length n.

write in your fav lang.

f is function (e.g. f(x) = x+1), x is a number, n is a number ≥ 1. we want [f(x), f(f(x)), ...]

#haskell #javascript #golang

edit: clarified detail.

write in your fav lang.

f is function (e.g. f(x) = x+1), x is a number, n is a number ≥ 1. we want [f(x), f(f(x)), ...]

#haskell #javascript #golang

edit: clarified detail.

Shared publicly

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+1+Refurio Anachro thanks. 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.

For lurkers, a function f is recursive if its definition uses ("calls") f, and it's tail-recursive if it never looks at the result from such a call. In javascript we can make sure that a function f is tail-recursive by always writing "return f(...)" in f's definition. Ocaml has no return keyword, so you need to check if your call is at one of your function's exit points for yourself.51w - 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.

Iterative solution:

#!/bin/python

import sys

def f(x):

return x + 1

def r(x,f,n):

l = []

l.append(x)

for i in range(n):

x = f(x)

l.append(x)

return l

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...