>>60
foldr can't be done in O(1) memory and O(n) time in any language, because the lists are singly-linked.

I suppose you could do it with O(1) memory if you didn't mind using O(n^2) time. Evaluate the function on elements n-1 and n, then re-search from the beginning of the list for element n-2, then evaluate the function on n-2 and the previous result, re-search for element n-3, and so on.

If you had a way to specify (or better yet, allow the compiler to infer) that a binary function was commutative and associative, then foldr could be implemented the same way as foldl for such functions. I don't know how much use this would be in practice.