Re: DeleteRepetitons and "functions" with memory
- To: mathgroup at smc.vnet.net
- Subject: [mg23779] Re: DeleteRepetitons and "functions" with memory
- From: "Allan Hayes" <hay at haystack.demon.co.uk>
- Date: Sat, 10 Jun 2000 02:59:24 -0400 (EDT)
- References: <8hfdb0$hgm@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Ranko,
> People more familiar with "functions" that have memory
> could probably say more about this definition. Then
> perhaps a satisfactory mathematical theory could be worked
> out.
I'll try: The term"functions with memory" does sound mysterious.
It seems to me that the crucial thing is to keep track of what definitions
are held in store.
Clear["`*"]
Consider
DeleteRepetitions[X_] :=
Block[{t}, t[n_] := (t[n] = Sequence[]; n); t /@ X]
Let's trace the evaluation of DeleteRepetitions[{2, 2}]
When DeleteRepetitions[{2,2} is entered Mathematica must evaluate
t[n_] := (t[n] = Sequence[]; n); t/@{2,2}
First to be evaluated is the definition of t
t[n_] := (t[n] = Sequence[]; n)
We now have the following in store
t[n_] := (t[n] = Sequence[]; n)
Then t/@{2,2}is evaluated:
First, t is evaluated at the first 2.
This means evaluating
t[2] = Sequence[]; 2
This gives 2 , but involves two steps: evaluate t[2] = Sequence[] and then
evaluate 2.
Because of the first of these we now have in store
t[2] = Sequence[ ]
t[n_] := (t[n] = Sequence[]; n)
So, when t is evaluated at the second 2, the first of these rules is used
and t[2] evaluates to Sequence[].
Thus, t/@{2,2} evaluates to {2, Sequence[]}, which automatically reduces to
{2}.
--
Allan
---------------------
Allan Hayes
Mathematica Training and Consulting
Leicester UK
www.haystack.demon.co.uk
hay at haystack.demon.co.uk
Voice: +44 (0)116 271 4198
Fax: +44 (0)870 164 0565
"Ranko Bojanic" <rbojanic at columbus.rr.com> wrote in message
news:8hfdb0$hgm at smc.vnet.net...
> The problem of finding a function DeleteRepetitons which
> removes duplicates from a list without sorting the result.
> was raised recently by Preston Nichols.
>
> For example,
> In[1] := DeleteRepetitions[{3,1,2,3,3,2,4,1}]
> Out[1] = {3,1,2,4}
>
> In[2] := DeleteRepetitions[{b,a,b,a,c,a}]
> Out[2] = {b,a,c}
>
> Preston's solution of this problem is
> DeleteRepetitions[X_] :=
> Take[X, #] & /@
> Sort[First /@
> (Position[X, #] & /@
> Union[X])] // Flatten
>
> Alan Hayes communicated a neat solution due to Carl Woll:
> DeleteRepetitions[X_] :=
> Block[{t}, t[n_] := (t[n] = Sequence[]; n); t /@ X]
>
> Several other solutions were communicated by Bob Hanlon.
>
> I would like to try to explain here why and how Woll's
> elegant solution works. First, the "function" f defined
> by
> ClearAll[f]
> f[x_] := (f[x] = nil; x)
>
> has the following property: If a appears for the first
> time as an argument of f, we have
> f[a] = a.
> After that we always get
> f[a] = nil
> (Instead of nil we can put anything: {}, Sequence[],...)
>
> People more familiar with "functions" that have memory
> could probably say more about this definition. Then
> perhaps a satisfactory mathematical theory could be worked
> out.
>
> Before using this "function", we always have to erase
> it for obvious reasons from memory :
>
> In[3] := ClearAll[f]
> f[x_] := (f[x] = nil; x)
> Map[f,{3,1,2,3,3,2,4,1}]
> Out[3]= {3, 1, 2, nil, nil, nil, 4, nil}
>
> So to get the function DeleteRepetitions, we only have to
> remove nil prom this list. This can be done, for instance by
> writing
>
> In[4] := ClearAll[f]
> f[x_] := (f[x] = {}; x)
> Map[f,{3,1,2,3,3,2,4,1}] / /Flatten
> Out[4]= {3, 1, 2, 4}
>
> Here Map[f,{3,1,2,3,3,2,4,1}] produces the list
> {3,1,2,{},{},{},4,{}}
> which is flattened to {3, 1, 2, 4}.
>
> Using Sequence[] we can save this last step:
>
> In[5] := ClearAll[f]
> f[x_] := (f[x] = Sequence[]; x)
> Map[f,{3,1,2,3,3,2,4,1}]
> Out[5]= {3, 1, 2, 4}
>
> The reason for this is that Map[f,{3,1,2,3,3,2,4,1}]
> produces the set
> {3,1,2,Sequence[],Sequence[],Sequence[],4,Sequence[]}
> which flattens itself automatically into {3, 1, 2, 4}.
>