9
$\begingroup$

Say I have a the typical Mathematica linked list structure defined like so:

Attributes[Pair] = {HoldAllComplete};

Nil = Pair[];

Cons = Pair[#1, #2]&;

It's well-known that turning a regular List into a linked list is easy:

ToLinkedList[list_List] := Fold[Cons[#2, #1]&, Nil, Reverse@list];

With some caveats that aren't relevant to this problem, converting back to a regular list is even easier:

Pair /: Normal[p_Pair] := List @@ Flatten[p];

We can use this to make a "constructor":

LinkedList[args___] := ToLinkedList@{args};

Right now, the output looks pretty terrible

In[43]:= ToLinkedList@{1, 2, 3}
Out[43]= Pair[1, Pair[2, Pair[3, Pair[]]]]

It would be really nice if we could have output that looks like LinkedList[1, 2, 3] instead. Attempts to do simple things with Format have provided me with no joy. For instance this looks great:

Format[p : Pair[_, _]] := 
 Row[{"LinkedList", "[", Row[p // Normal, ","], "]"}, BaseStyle -> "Output"];
Format[Nil] := Row[{"Nil"}, BaseStyle -> "Output"]

In[45]:= LinkedList[1, 2, 3]
Out[45]= LinkedLits[1, 2, 3]

But it completely falls apart when you try to copy and paste. Indeed, I had to type the stuff after Out by hand, because when I tried to paste into the text area, what actually showed up was:

Row[{"LinkedList", "[", Row[{1, 2, 3}, ","], "]"}, 
 BaseStyle -> "Output"]

This was not really what I wanted. Cutting and pasting inside a notebook appears to work OK, but when I try to evaluate a pasted expression as input, I get awful stuff like this:

MakeExpression::boxfmt: InputForm in MakeExpression[FormBox[RowBox[{Row,[,RowBox[{RowBox[{<<3>>}],,,RowBox[{<<3>>}]}],]}],InputForm],InputForm] is not a box formatting type. A box formatting type is any member of $BoxForms. >>

I know I could use MakeBoxes to do what I want, but that only works for StandardForm or TraditionalForm, and this seems like a perfectly sensible textual representation. I have a feeling I'm using Format completely wrong, but I'm not sure what using it right looks like.

EDIT in response to rcollyer: I have tried the Notation` package, but it's box-oriented, and I can't figure out how to flatten out the Pair structures for outputting inside the LinkedList.

EDIT again in response to ruebenko: you're right; it's been fixed.

EDIT to fix an arguable bug in the implementation of Normal for Pairs, discovered while playing around trying to create a custom format. As it stands right now:

In[49]:= LinkedList[LinkedList[1, 2], LinkedList[3, 4], LinkedList[5, 6]]
Out[49]= LinkedList[1, 2, 3, 4, 5, 6]

I don't want this auto-flattening behavior for Normal in any event, but it's particularly terrible in the case of formatting output because the output is totally wrong. Here's a fix:

FromLinkedList[list_Pair] :=
  NestWhileList[List @@ #[[2]] &, {Null, list}, #[[2]] =!= Nil &][[2 ;;, 1]];

Pair /: Normal[p_Pair] := List @@ FromLinkedList[p]

This is a bit uglier, especially that Null placeholder at the beginning, but it does the right thing:

In[63]:= LinkedList[LinkedList[1, 2], LinkedList[3, 4], LinkedList[5, 6]]
Out[63]= LinkedList[LinkedList[1, 2], LinkedList[3, 4], LinkedList[5, 6]]

It's the best I could come up with; other solutions involved Reap and Sow, which seemed like a real shame when working with a nice functional data structure like this one.

$\endgroup$
2
  • $\begingroup$ Have you tried to use the Notations` package for this? $\endgroup$
    – rcollyer
    Apr 27, 2012 at 15:03
  • $\begingroup$ I think your definition should look like this: ToLinkedList[list_List] := Fold[Cons[#2, #1] &, Nil, Reverse@list]; otherwise I am not sure what you would like to do? $\endgroup$
    – user21
    Apr 27, 2012 at 17:04

2 Answers 2

5
$\begingroup$

I see in your question that you would rather not use MakeBoxes but I think this might be worth a try.

Pair /: MakeBoxes[linkedList : Pair[i_, p_Pair], fmt_] := 
 TagBox[ToBoxes[LinkedList @@ Flatten[linkedList]], 
  InterpretTemplate[Pair[i, p] &], Editable -> False, 
  Selectable -> True, SelectWithContents -> True]

The InterpretTemplate affects how Mathematica will see your expression whereas the TagBox is how you will see it.

This allows for copy and paste and any of the various forms work just fine.

$\endgroup$
3
  • $\begingroup$ Andy, InterpretTemplate does not show up in the docs. Do you have any other pointers on its use? $\endgroup$
    – rcollyer
    Apr 27, 2012 at 15:10
  • $\begingroup$ @rcollyer no more than what I've shown here. It is usually a game of trial and error for me. On that note. I would use it cautiously since undocumented functions may not stick around :) $\endgroup$
    – Andy Ross
    Apr 27, 2012 at 15:12
  • $\begingroup$ I'm generally not a fan of undocumented features for exactly those reasons. But, if it works. $\endgroup$
    – rcollyer
    Apr 27, 2012 at 15:15
5
$\begingroup$

After some further thought and exploration, it seems like this is a perfect use of the newish (version 6 and up) Defer wrapper. Adding the following rules to Pair seems to do exactly what I'm looking for:

Pair /: Format[list : Pair[_, _]] :=
  With[{args = Normal@list},
   Defer[LinkedList[##]] & @@ args];
Pair /: Format[Pair[]] := Defer[Nil];

Then:

In[33]:= Pair[]
Out[33]= Nil

In[34]:= LinkedList["wongle", bongle, "bingle", fringle]
Out[34]= LinkedList["wongle", bongle, "bingle", fringle]

In[35]:= LinkedList["wongle", bongle, "bingle", fringle] // InputForm
Out[34]= Pair["wongle", Pair[bongle, Pair["bingle", Pair[fringle, Pair[]]]]]

This time I was able to cut and paste directly from the Out cells; indeed, a little investigation with "Show Cell Contents" suggests that there isn't anything weird going on in those cells at all.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.