# What is the most efficient way to map a linked list?

In order to work with lists effectively using common recursive patterns from functional programming, it's often most convenient to worked with the "linked list" representation, that looks like this:

shortLinked = {a, {b, {c, {d, {}}}}};


At the end of the procedure, you can usually flatten it back out. However, it's possible that you may wish to map a function over it, the exact same way you'd use Map on a regular List. We would want a function that does the following:

mapLinked[f, shortLinked] === {f[a], {f[b], {f[c], {f[d], {}}}}}


We also want this to work with heads other than List, exactly like Map, because it's often convenient to use heads other than List to make a linked list:

shortLinkedCons = cons[d, cons[c, cons[b, cons[a, cons[]]]]]



The function should be efficient; it's possible we could be working with lists that have tens of thousands of elements. It's also important that the function works if some of the elements of the list are themselves lists (i.e., have the same head as the linked list cells), so naively Flattening the list and then reconstituting it using Fold is not going to work. That is, the function must satisfy

mapLinked[f, {{6, 7}, {{3, 4, 5}, {{1, 2}, {}}}}] === {f[{6, 7}], {f[{3, 4, 5}], {f[{1, 2}], {}}}}


There are doubtless a lot of ways to solve this problem. What's the fastest?

EDIT to add: It should also avoid going into an infinite loop if the list isn't terminated properly (with {} or some other h[] in the last tail position).

EDIT again: For lists which are very long (tens of thousands of elements), a lot of approaches will bump up against $RecursionLimit or cause the kernel to crash due (presumably) to a stack overflow. - ## 3 Answers ### Implementations Here is an "idiomatic" one: ClearAll[mapRec, reverse]; mapRec[f_, ll_] := Block[{$IterationLimit = Infinity}, reverse@mapRec[{}, f, ll]];
mapRec[accum_, _, {}] := accum;

reverse[ll_] := reverse[{}, ll];
reverse[accum_, {}] := accum;


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]


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];

tail[llLazy[_,tail_]]:=tail;

map[f_,llLazy[h_,tail_]]:=llLazy[f[h],map[f,tail]];
map[f_,llLazy[]]:=llLazy[];

Fold[llLazy[#2,#1]&,llLazy[],Reverse[lst]];

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_,_,_]:=


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];


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. - The map solution crashes my kernel even if I don't display the result; I expect there the stack blows up inside Replace. – Pillsy Apr 8 '14 at 18:15 @Pillsy This happened to me too, and I came to the same conclusion. Then I checked on 10000 elements, and it was fine. Now I checked again on 100000 elements, and saw the crash again. Probably, you are right. Will check again and modify my post. – Leonid Shifrin Apr 8 '14 at 18:18 @Pillsy See my edit for a much faster implementation which goes through flattening - unflattening stage. – Leonid Shifrin Apr 8 '14 at 18:34 I like the lazy approach. However, I found that you can speed up fromLazyLinkedList by about a factor of 2 by replacing NestWhile with a tail-recursive function. If you implement obvious strictToLazy/lazyToStrict functions and implement a strict map in terms of your lazy map, it's only about 50% slower than doing things directly! – Pillsy Apr 9 '14 at 14:51 @Pillsy Nice! I thought a bit about this, but did not follow this direction. Besides these advantages you named, this should also be a more idiomatic code. Care to add this to my post, or would you leave this to me as an exercise? :) – Leonid Shifrin Apr 9 '14 at 14:54 So far, the best I've been able to do uses Reap and Sow to construct an ordinary list while I traverse the linked list with a While loop. At the end, I reconstitute it using Fold in the normal way. It's pretty easy to capture the head of the list. It will fail (throw $Failed) if the list isn't terminated properly, or if it contains a head other than the head of the initial cell.

PillsymapLinked[f_, l : h_[___]] :=
With[{nil = h[]},
Module[{
ll = l,
step,
failed
},
step[h[hd_, tl_]] := (Sow[f@hd]; tl);
step[_] := Throw[$Failed, failed]; Catch[Fold[ h[#2, #1] &, nil, Reverse@Reap[ While[ll =!= nil, ll = step@ll]][[-1, 1]]], failed, #1 & ]]]  This is fairly fast; using testLinked = Fold[{#2, #1} &, {}, Range[100000]]; ClearAll[f];  it takes about 0.25 seconds (on my machine) to perform PillsymapLinked[f, testLinked];  For comparison, Map[f, Range[100000]];  takes just 0.02 seconds, so the slowdown for manipulating a linked list with top-level Mathematica is about an order of magnitude. EDIT to add: Following Leonid Shifrin's lead, I tried a version using Sow/Reap that replaces the While loop with a recursive step; this speeds things up by an additional 20% or so, to 0.18 second for the 100000 element list. PillsymapLinkedRec[f_, l : h_[___]] := Block[{$IterationLimit = Infinity},
Module[{
step
},

step[h[hd_, tl_]] := (step[Sow[f@hd]; tl]);
step[_] := Null;

Catch[Fold[
h[#2, #1] &,
h[],
Reverse@Reap[step@l][[-1, 1]]]]]]


EDIT again to add: I decided to use tail recursion again, this time to map the leaves of a general tree as in Daniel Lichtblau's Do loop approach in mappedFunction.

Instead of explicitly, imperatively managing a stack, I have a purely functional approach that uses continuation-passing style to make everything tail recursive. It's still pretty slow, but not as slow--I think things are faster because doing things recursively allows all the flow control and restructuring of the tree to be handled by the pattern matching in the recursive call. No need for If tests or indexing into the structure. In order to make the CPS work, I had to turn any levels of the tree with more than two elements into a custom linked list which I then flatten. I have the normal case of a h[car, cdr] pair special-cased for speed (it makes things two or three times faster):

mappedFunctionCPS[f_, tree : h_[___]] :=
Block[{$IterationLimit = Infinity}, Module[{step, cons}, Attributes[cons] = HoldAllComplete; step[leaf : Except[_h | _cons], cont_] := cont[f@leaf]; step[h[], cont_] := cont[h[]]; step[h[car_, cdr_], cont_] := step[cdr, Function[x, step[car, Function[y, cont@h[y, x]]]]]; step[fork_h, cont_] := step[Fold[cons[#2, #1] &, cons[], Reverse@fork], Function[x, cont[h @@ Flatten[x]]]]; step[cons[], cont_] := cont[cons[]]; step[cons[car_, cdr_], cont_] := step[cdr, Function[x, step[car, Function[y, cont@cons[y, x]]]]]; step[tree, Identity]]];  It works: mappedFunctionCPS[f, {a, {b, {c, {d, {}}}}}] (* {f[a], {f[b], {f[c], {f[d], {}}}}} *) shortTree = {{a, b}, c, q, r, {d, e, {}}, {f, {g, {}}}}; mappedFunctionCPS[f, shortTree]; mappedFunctionCPS[f, shortTree] (* {{f[a], f[b]}, f[c], f[q], f[r], {f[d], f[e], {}}, {f[f], {f[g], {}}}} *)  Comparing to the stack version, mappedFunction. mappedFunctionCPS[f, shortTree] === mappedFunction[f, shortTree] (* True *) mappedFunctionCPS[f, testLinked]; // Timing // First (* 0.548233 *) mappedFunction[f, testLinked]; // Timing // First (* 3.854237 *)  - By the way, using untagged exception here does not seem right, since you may be catching an exception thrown by the mapped function, rather than by your mechanism. Generally, I view untagged exceptions as a language defect - they should not be allowed at all. – Leonid Shifrin Apr 8 '14 at 18:43 That's a good point; fixorated. – Pillsy Apr 8 '14 at 19:27 Pretty cool of you to include the CPS version. No time now, but will study later (would up vote again if I could). I once posted something probably along the similar lines, here – Leonid Shifrin Apr 11 '14 at 22:44 Here is an old fashioned approach, using stacks. It is quite general in the sense that it will handle tree structures with more than two children per node. It is also fairly slow; it has the correct (linear) complexity but maybe an order of magnitude more pushing/popping than the length. SetAttributes[push, HoldRest]; SetAttributes[pop, HoldAll]; push[elem_, stack_] := stack = {elem, stack} emptyQ[stack_] := stack === {}; pop[{}] = "nil"; pop[stack_] := Module[{top = stack[[1]]}, stack = stack[[2]]; top] mappedFunction[f_, arg_] := mappedFunction[f, arg, Head[arg]] mappedFunction[f_, arg_, head_] /; Head[arg] =!= head := arg mappedFunction[f_, arg_, head_] := Catch[Module[ {stack = {}, resstack = {}, res, n = Length[arg], elem, posn, m, newelem}, push[{{0, n}, arg}, stack]; Do[push[{{j, n}, arg[[j]]}, stack], {j, n}]; While[! emptyQ[stack], {{posn, m}, elem} = pop[stack]; If[posn === 0, res = elem; Do[elem = pop[resstack]; res[[j]] = elem; , {j, m}]; push[res, resstack]; ,(*else*) If[Head[elem] =!= head, push[f[elem], resstack]; ,(*else*) m = Length[elem]; push[{{0, m}, elem}, stack]; Do[push[{{j, m}, elem[[j]]}, stack], {j, m}]; ]]; ]; res ]]  Examples: shortLinked = {a, {b, {c, {d, {}}}}}; mappedFunction[f, shortLinked] (* Out[271]= {f[a], {f[b], {f[c], {f[d], {}}}}} *) shortLinkedCons = cons[d, cons[c, cons[b, cons[a, cons[]]]]]; mappedFunction[f, shortLinkedCons] (* Out[246]= cons[f[d], cons[f[c], cons[f[b], cons[f[a], cons[]]]]] *)  @Leonid Shifrin's bigger example: toLinkedList[lst_] := Fold[{#2, #1} &, {}, Reverse@lst] llLarge = toLinkedList[Range[10^5]]; mappedFunction[f, llLarge]; // AbsoluteTiming (* Out[315]= {6.207473, Null} *)  Kinda slow. If I find a way to cut back on the push/pop cycle I'll edit to show the improvement. - I was interested in using MapAll to try to replicate this, to look at performance, and for large lists it just doesn't work. It kills the kernel with (I'm guessing) a stack overflow, just like solutions based on ReplaceAll or recursion and $RecursionLimit = Infinity`. – Pillsy Apr 11 '14 at 21:05
As an alternative, I replaced the explicit, imperative stack management with continuation passing style in an edit to my answer. It's about twice as fast. – Pillsy Apr 11 '14 at 21:40
@Pillsy The whole purpose of using an explicit stack is to avoid the recursion stack. Solutions based on MapXXX will be prone to getting into deep recursion, and MapAll is no exception. At first glance I guess it seems like it might be, but when you consider implementation possibilities I think everything points to a deeply nested construction and/or recursion. – Daniel Lichtblau Apr 13 '14 at 18:41
@Pillsy I will say I like your speed improvements. Now I need to take the time to understand them... – Daniel Lichtblau Apr 13 '14 at 18:44