[RootDynasty]

I agree that worrying about the time complexity of the non-parallel portions of pmap is unlikely to be an issue for most use cases. It's still interesting to think about the tradeoffs though.

Hitting the degenerate case depends on the function you're computing in question. It's quite possible that the tasks will complete in the given order. I think you're giving too much credit to Erlang's task scheduler.

Also I'm not sure how one would even implement a tail recursive map function on a singly linked list. The cons operation can only add elements to the front of the list. I looked up how the map operation is implemented in Erlang. It isn't tail recursive:

https://github.com/erlang/otp/blob/172e812c491680fbb175f56f7...

I'm interested to know how you'd implement a tail-recursive version of map (continuations aren't allowed).

[lostcolony]

Interesting that it's not; I would have expected it to be. Given that, though, it's spawning tasks in list order, then receiving in list order; if the tasks complete in the order you spawned them, the first thing in the queue/arriving is always the item you're receiving on. That's the ideal case; more likely they'd be nearly in the order you spawned them, in which case you'd only have a few items to check through before you found the one you're receiving on.

I'm not saying the task scheduler is perfect, but I'd be really, really weirded out if it gave priority to the final process spawned, and worked its way backwards, which would be necessary for the degenerate case (that is, we spawned off items 1,2,3,4 in that order, but they completed 4,3,2,1. I would expect them to finish in close to 1,2,3,4 order, which would leave it at O(1) on each receive).

I'd implement a tail recursive map as -

  map(F, L) -> map(F, L, []).

  map(_, [], Acc) -> lists:reverse(Acc);
  map(F, [H|T], Acc) -> map(F, T, [F(H) | Acc]).