Re: Flatten alternative
- To: mathgroup at smc.vnet.net
- Subject: [mg105503] Re: [mg105469] Flatten alternative
- From: Leonid Shifrin <lshifr at gmail.com>
- Date: Sat, 5 Dec 2009 05:34:51 -0500 (EST)
- References: <200912040931.EAA06957@smc.vnet.net>
Leslie,
how about this then:
Clear[myFlatten];
With[{join =
Which[#2 === {}, #1,
! ListQ[#2], Append[#1, #2],
{First@#2} === #2, #0[#1, First@#2],
True, Append[#0[#1, Most@#2], Last@#2]] &},
myFlatten[{}] = {};
myFlatten[x_?ListQ] /; {First@x} === x && ! ListQ[First@x] := x;
myFlatten[x_?ListQ] :=
join[myFlatten@First@x, myFlatten@Rest@x];
myFlatten[x_] := {x}];
It's kind of tricky, but uses only the functions you asked about - I even
avoided using Length. For example:
In[1]:= myFlatten[{a,b,{c,{d,{e,f,g[h,{i,j,{k}}]}}}}]
Out[1]= {a,b,c,d,e,f,g[h,{i,j,{k}}]}
In[2]:= myFlatten[{{1,2,3}}]
Out[2]= {1,2,3}
Now, some implementation details: the function uses double recursion. One
recursion is realized by myFlatten itself, and another is realized by
<join>, which is just an alias for a recursive pure function that joins
together two lists. Perhaps the hardest to digest part is how the recursive
pure function <join> works. If I remember correctly, recursive pure
functions are documented but very briefly. You may get a handle on them by
implementing some simple functions like factorial, Fibonacci or the like in
this style. Alternatively, one could implement it without this construct,
but then a new auxilliary head (say <join>) must be introduced. Here is how
the code for <join> can look like then:
Clear[join];
join[x_?ListQ, y_?(! ListQ[#] &)] := Append[x, y];
join[x_, {}] := x;
join[x_?ListQ, y_ /; {First@y} === y] := join[x, First@y];
join[x_?ListQ, y_] := Append[join[x, Most@y], Last@y];
Regards,
Leonid
On Fri, Dec 4, 2009 at 5:37 PM, Leslie Kanthan <jezzybear19 at hotmail.co.uk>wrote:
> myFlattenSubfunction[tlist_] /;
> Depth[tlist] <=
> 1 := tlist
> myFlattenSubfunction[tlist_List] :=
> Sequence @@@
> myFlattenSubfunction /@
> tlist
> myFlatten[tlist_] := myFlattenSubfunction[tlist]
> myFlatten[k]
>
> I did the above, but my problem is it does not use First[], Rest[],
> Prepend[], ListQ[] ... I can see what you mean by your code, I never thought
> of using the replace, but its a function that I am trying to avoid using.
> However whichever way by using only First[], Rest[], Prepend[], ListQ[], the
> code will be enefficent i just want to see how far I can get at disementing
> the nested list.
>
> I would be most pleased if you can show me how I may use First[], Rest[],
> Prepend[], ListQ[] along with the said pattern function. Thanks
>
> ------------------------------
> Date: Fri, 4 Dec 2009 15:53:50 +0300
> Subject: Re: [mg105469] Flatten alternative
> From: lshifr at gmail.com
> To: jezzybear19 at hotmail.co.uk; mathgroup at smc.vnet.net
>
>
> Hi,
>
> How about this:
>
> Clear[myFlatten];
> myFlatten[x_List] :=
> x //. y_ :> Replace[y, {a___, {b___}, c___} :> {a, b, c}, {0}]
>
> My first attempt by the way was a simpler one:
>
> Clear[myFlattenNaive]
> myFlattenNaive[x_List] := x //. {a___, {b___}, c___} :> {a, b, c};
>
> This looks ok, but fails in the following case, for example:
>
> In[1]:= {a,b,{c,{d,{e,f,g[h,{i,j,{k}}]}}}}//myFlattenNaive
>
> Out[1]= {a,b,c,d,e,f,g[h,{i,j,k}]}
>
> The wrong thing is that it flattens lists also inside ofther heads, and
> this is not what Flatten does. The more complex version does not do it:
>
> In[2]:= {a,b,{c,{d,{e,f,g[h,{i,j,{k}}]}}}}//myFlatten
>
> Out[2]= {a,b,c,d,e,f,g[h,{i,j,{k}}]}
>
> The added advantage of the myFlatten solution is that it is easy to add to
> it a level specification as an optional parameter to make myFlatten flatten
> on a specific level, if this is needed.
>
> Needless to say, for deeply nested / complex lists with many sublists on
> the same level, myFlattenwill be grossly inefficient.
>
> Regards,
> Leonid
>
>
>
> On Fri, Dec 4, 2009 at 12:31 PM, Jezzybear <jezzybear19 at hotmail.co.uk>wrote:
>
> I am trying to create a function myflat[list] to mimic the behavior of
> Mathematica's Flatten[]
> function.Example:
> In[1]:= myflat[{{{a}}, {b, c}, {d}}]
> Out[1]= {a, b, c, d}
> In[2]:= myflat[{{}, 1, {{2}}}]
> Out[2]= {1, 2}
> However in writing this function I want to use only Mathematica's
> pattern matching features, the functions
> First[], Rest[], Prepend[], ListQ[]. I am trying to do this using some
> subfunctions like creating one called myjoin
>
>
>
>
> ------------------------------
> Have more than one Hotmail account? Link them together to easily access
> both. <http://clk.atdmt.com/UKM/go/186394591/direct/01/>
>
- References:
- Flatten alternative
- From: Jezzybear <jezzybear19@hotmail.co.uk>
- Flatten alternative