Thanks, Guillaume! So I was wrong. Would you call your definition of map* CPS? I think of your k as the continuation. Is it any faster than reverse first & then do the easy recursive function?
No mutation, no 'reverse'. I think tail-recursion isn't the property you're thinking about, but rather whether such an algorithm can be executed in O(1) space (then only mutation would help, not using 'reverse').
That might be what Christian meant :-D I generally get confused by words like O(1). But I wouldn't think your CPS code was going to be very fast. I'd say that the usual recursive program was using a lot of stack space, as there are so many pending operations. I'd say that your CPS version was just storing this stack space in the body of a lambda, and that's gotta be stored somewhere, right?