A Map Function with O(1) Complexity: Redux
There seems to be a fair amount of confusion about how I could claim that a map function could have O(1) complexity. Maybe it might help if I show the psuedo-code:
class List {
 List(Object hd, Object tl) {
 head = hd; tail = tl;
 }
 List Map(Function f) {
 return new MappedList(f, this);
 }
 Object Head() {
 return head;
 }
 List Tail() {
 return tail;
 }
 Object head;
 List tail;
};
class MappedList : List {
 MappedList(Function f, List l) {
 list = l;
 fxn = f;
 }
 List Map(Function f) {
 return new MappedList(Compose(f, fxn), this);
 }
 Object Head() {
 return f(head);
 }
 List Tail() {
 return new MappedList(fxn, list.Tail());
 }
 List list;
 Function fxn;
};
Note that while the map functions for both lists have O(1) complexity, they create new lists for which head and tail access is slightly more expensive. This effect is cumulative. So the complexity of the complexity analysis of the whole program is going to be changed as a result.