# Emulating Sequence with my own function

I just considered if/how one could implement Sequence in Mathematica if it were not predefined. It turned out that the following simple definition has in all my tests exactly the right behaviour:

myseq /: f_[x___, myseq[y___], z___] := f[x, y, z]


Now my question: Does this already correctly reproduce the full behaviour of Sequence, or is there something Sequence does but myseq doesn't which I missed in my tests?

Here's what I tested:

foo[myseq[a, b]]
(*
==> foo[a, b]
*)
Hold[mysec[a,b]]
(*
==> Hold[a, b]
*)
HoldComplete[myseq[a,b]]
(*
HoldComplete[myseq[a, b]]
*)
Hold[f[myseq[a,b]]]
(*
==> Hold[f[myseq[a, b]]]
*)
f[myseq[myseq[a,b],c,d],e,myseq[f,g,myseq[]]]
(*
==> f[a, b, c, d, e, f, g]
*)

-
One situation where myseq fails is for something like {1, 2, 3} /. 2 -> myseq[a, b]. – Heike Jun 18 '12 at 18:57
t = {{a, b}, {c, d}, f}; myseq @@t fails – Dr. belisarius Jun 18 '12 at 18:58
@Heike That is because it doesn't support SequenceHold like Sequnce does. – Szabolcs Jun 18 '12 at 18:58
@Szabolcs I just figured that out. – Heike Jun 18 '12 at 18:58
@belisarius myseq[1,2] does the same. It may also be due to the lack of SequenceHold support. EDIT: it's not. Support can be added with myseq /: f_[x___, myseq[y___], z___] /; FreeQ[Attributes[f], SequenceHold] := f[x, y, z] – Szabolcs Jun 18 '12 at 19:00

Ok, my two cents. The answer seems to be - you can't. There are 3 "magic" symbols which are wired into the core evaluator much deeper than the rest: Evaluate, Unevaluated, and Sequence. You can't fully emulate any of those without essentially writing your own version of Mathematica evaluator on top of the built-in one.

For the record, I first read about it in the book of David Wagner, "Power programming with Mathematica - the Kernel", p.207. Which means - if this is correct, I take the credit, but if it is wrong, he is the one to blame :). But, seriously, there was nothing in my experience to contradict this. You may emulate some aspects of Sequence, but I would be very surprised if you could make a complete emulation (without writing your own evaluator on top of the system one).

Let me also add that, while it is hidden, you do use Sequence in your approach, since the y___ pattern is internally destructured as Sequence. Check this out:

ClearAll[myseq];
myseq /: f_[x___, myseq[y___], z___] := f[x, Head[Unevaluated[y]], z]


and now

f[1, myseq[], 5]

f[1, Sequence, 5]

-
Leonid, I hate to disappoint but I think you're getting a false result in your test. I don't think ___ or ## are implemented using Sequence though they are of course analogous. In my opinion you cannot "catch" the y on the RHS in some intermediate form using Unevaluated. You are instead seeing this: Head@Unevaluated[1, 2, 3] yields Sequence; it is an effect of Unevaluated. – Mr.Wizard Jun 19 '12 at 1:30
@Mr.Wizard I'd have to sit down and experiment a bit to find where exactly, but I've seen __ and## transform into Sequence before. I think they do make use of Sequence at some point during their evaluation. – Szabolcs Jun 19 '12 at 7:02
@Mr.Wizard Well, you may be right, but I feel that Unevaluated should have nothing to do with that, it has a different purpose. OTOH, it is very natural that __ and ## use Sequence internally, since it is the same mechanism behind al of them. Perhaps, a better statement would be that all sequences are using the same underlying mechanism. I also second Szabolcs, I seem to remember cases where Sequence was appearing in the evaluation of __ and ## - related code. Will also try to find those cases. – Leonid Shifrin Jun 19 '12 at 7:53
@Mr.Wizard Ok, check this out: HoldComplete[1, 2, ff[3, 4, 5], 6, 7] /. ff[y__] :> y. – Leonid Shifrin Jun 19 '12 at 11:01
What would you have Head@Unevaluated[1,2] return, or y[x__] := x; y[2, 3] or {1, 2} /. {l__} :> l? Sequence is the standard way in MMA to represent sequences of arguments, and I see no other reasonable alternative. However, where there are alternatives such as in {1, 2} /. {l__} :> HoldComplete[l], l__ is shown to represent the "real" sequence and not a _Sequence expression – Rojo Jun 19 '12 at 15:47

I think an issue that you will never be able to completely solve is one of priorities. Sequence is flattened before upvalues. So, for starters

ClearAll[f];
f /: g[f, _] := 9


So

g[f, myseq[2, 3]]


9

but

g[f, Sequence[2, 3]]


g[f, 2, 3]

-
+1. This is just one manifestation of what I meant by saying that Sequence is deeply wired in the evaluation procedure. – Leonid Shifrin Jun 19 '12 at 15:08

There are functions related to Sequence: BlankSequence, BlankNullSequence and SlotSequence. These can be used to perform operations similar to Sequence but they are not identical.

As pointed out in the comments Sequence obeys the attribute SequenceHold:

SetAttributes[test, SequenceHold]

test[ Sequence[1, 2, 3] ]

test[Sequence[1, 2, 3]]


The others do not:

{1, 2, 3} /. _[x__] :> test[x]

test[##] &[1, 2, 3]

test[1, 2, 3]

test[1, 2, 3]


In fact these operations succeed even if test has HoldAllComplete.

You could emulate this behavior at least in part by modifying your definition to check for SequenceHold:

myseq /: f_[x___, myseq[y___], z___] /;
FreeQ[Attributes @ Unevaluated @ f, SequenceHold] := f[x, y, z]


Unlike the functions above Unevaluated uses Sequence:

test[1, Evaluate@Unevaluated[5, 6], 3]

test[1, Sequence[5, 6], 3]

-