Implementations
Here is an "idiomatic" one:
ClearAll[mapRec, reverse];
mapRec[f_, ll_] := Block[{$IterationLimit = Infinity}, reverse@mapRec[{}, f, ll]];
mapRec[accum_, _, {}] := accum;
mapRec[accum_, f_, {head_, tail_}] := mapRec[{f[head], accum}, f, tail];
reverse[ll_] := reverse[{}, ll];
reverse[accum_, {}] := accum;
reverse[accum_, {head_, tail_}] := reverse[{head, accum}, tail];
which is properly tail-recursive, with an obvious generalization to the non-list cons head.
If you allow the transformation to flat list and back (which is, essentially, what you are doing in your code), then we can have a much faster version:
toLinkedList[lst_] := Fold[{#2, #1} &, {}, Reverse@lst]
map[f_,l_]:=toLinkedList @ Map[f, Flatten[l, Infinity]]
again, with an obvious generalization to non-List cons head.
Benchmarks
Benchmarking:
llLarge = toLinkedList[Range[100000]];
mapRec[f, llLarge]; // AbsoluteTiming
(* {0.222687, Null} *)
which is similar timing to what your own approach was showing. Now, the faster one:
map[f, llLarge]; // AbsoluteTiming
(* {0.088695, Null} *)
map[f, llLarge] === mapRec[f, llLarge]
(* True *)
Laziness
It may make sense to use the lazy version of linked lists, since these two combine well in Mathematica. Doing this along the lines of this excellent answer, we may define
ClearAll[llLazy,toLazyLinkedList,head,tail,map];
SetAttributes[llLazy,HoldAllComplete];
head[llLazy[]]:=End;
head[llLazy[h_,_]]:=h;
tail[llLazy[_,tail_]]:=tail;
map[f_,llLazy[h_,tail_]]:=llLazy[f[h],map[f,tail]];
map[f_,llLazy[]]:=llLazy[];
toLazyLinkedList[lst_]:=
Fold[llLazy[#2,#1]&,llLazy[],Reverse[lst]];
fromLazyLinkedList[ll_llLazy] :=
Block[{$IterationLimit = Infinity},
Module[{step, tag},
step[llLazy[]] := Null;
step[llLazy[h_, t_]] := step[Sow[h, tag]; t];
(If[#1 === {}, #1, First[#1]] &)[Reap[step@ll, tag, #2 &][[2]]]]];
From the point of view of linked lists, this is pretty much a usual linked list:
lllLarge = toLazyLinkedList[Range[100000]];
fromLazyLinkedList@lllLarge // Length // AbsoluteTiming
(* {0.102590, 100000} *)
However, Map operation now is lazy:
mapped = map[# + 1 &, lllLarge]; // AbsoluteTiming
(* {9.*10^-6, Null} *)
The overhead of the laziness is not very significant:
fromLazyLinkedList@mapped // Length // AbsoluteTiming
(* {0.218473, 100000} *)
This is about twice slower than our "idiomatic" non-lazy version, and about 5 times slower than the one using conversion to flat lists and back.
My main point here (and the reason why I included this section rather than just a link to WReach's post) is that this lazy list construction plays well with the standard recursive techniques based on a combination of recursion and pattern-matching. As an example, let's implement a version of TakeWhile for such a linked list:
ClearAll[takeWhileLL];
takeWhileLL[ll_llLazy,cond_]:=
Block[{$IterationLimit = Infinity},
takeWhileLL[llLazy[],ll,cond]
];
takeWhileLL[accum_,llLazy[head_,tail_],cond_]/;cond[head]:=
takeWhileLL[llLazy[head,accum],tail,cond];
takeWhileLL[accum_,_,_]:=
Reverse[fromLazyLinkedList[accum]]
This is just the code we'd write for a usual linked list, anyway. It uses the usual combination of recursion and pattern-matching. But the lazy version may be more efficient.
For example,
takeWhileLL[mapped, # < 1000 &] // Length // AbsoluteTiming
(* {0.005817, 998} *)
is now 100 times faster than the full mapping fromLazyLinkedList@mapped, and 20 times faster than the fastest non-lazy map version, because lazy Map does not have to Map unnecessarily.
So, the summary of this section is that laziness can be neatly integrated with the standard linked list construction in Mathematica - essentially, we can get it for free. And, we don't have to change the way we write idiomatic linked list-related code, it just works.
Notes
Note that this straight-forward choice:
ClearAll[mapCrashing];
mapCrashing[f_, l_] := Replace[l, {head_, tail_} :> {f[head], tail}, {0, Infinity}]
looks good but overflows the stack and crashes the kernel for large lists. Presumably, this happens inside Replace, and I wasn't able to find the cure for this approach.
Next, note that trying to display the result for some symbolic f will issue an $RecusrsionLimit error message, and potentially crash the kernel, because it will try to evaluate this for rendering purposes.
The final observation is that there is no way around the fact that linked lists can not benefit from packed arrays / auto-compilation, so all these solutions are bound to be much slower than the analogous code run on packed arrays for compilable mapped functions.
