Re: Types in Mathematica thread

*To*: mathgroup at smc.vnet.net*Subject*: [mg62997] Re: Types in Mathematica thread*From*: Jon Harrop <usenet at jdh30.plus.com>*Date*: Sat, 10 Dec 2005 06:03:12 -0500 (EST)*References*: <dmp9na$hi2$1@smc.vnet.net> <200512060504.AAA02828@smc.vnet.net> <dn5ohr$nle$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Daniel Lichtblau wrote: > Jon Harrop wrote: >> f[{}] := 0 >> f[{h_, t___}] := 1 + f[{t}] > > This is exactly is it should be. The pattern is reforming a List of > length one less at every step of the match. In the current implementation, yes. That makes the current implementation have asymptotically more complex pattern matching than is theoretically necessary for an infinite number of patterns, many of which are useful. >> However, this may get fixed in the future. > > My colleagues often pleasantly surprise me, but I rather doubt the > complexity of this can be improved. You just need to lazily evaluate the matched sublists ("t" in this case). This can be done by implementing a new kind of list that is internally a reference to a subarray of an existing list. Extracting subarrays (as in my example) is then O(1) instead of O(n). The only tricky part is making sure that semantics are unchanged, e.g. referring to all child sublists and forcing them to be copied explicitly if the parent is mutated. I've had a play around with this and I think there is a lot of scope for a radical departure in the internal representation of Mathematica's lists, using immutable balanced binary trees instead of mutable arrays. This is exactly the kind of improvement that could be made much more easily if Mathematica were coded in a functional language. It would be interesting to play around with a toy implementation, to get a better idea of which optimisations were most beneficial on real Mathematica programs. > When you note "conventional implementation" you may have in mind > complexity that would apply if the inderlying structure were a Lisp-like > linked list. But a Mathematica List is more akin to what traditionally > is viewed as an array or vector or table, that is, something with a > fixed number of "contiguous" elements (which may or may not actually map > to contiguous entities in storage). This optimisation applies to any suitable internal representation, including arrays. For example, it will also equivalently improve the asymptotic complexity of the following pattern: f[t___, h_] which wouldn't happen if the underlying data structure was a singly-linked list. >> The fact that Mathematica distinguishes between up- and down-values is >> really incidental (a historical artefact). So I think you're >> over-analysing it. > > I don't see this as artifact. It is important that UpValues behave > differently in various aspects from DownValues. Maybe I'm > misunderstanding what you mean by an incidental distinction. It's been a while since I looked but I can see no objective reason to expose the distinction. I think the distinction between up- and down-values could be removed were it not for backward compatibility. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/products/ocaml_for_scientists/chapter1.html

**Follow-Ups**:**Re: Re: Types in Mathematica thread***From:*Daniel Lichtblau <danl@wolfram.com>

**References**:**Re: Types in Mathematica thread***From:*Jon Harrop <usenet@jdh30.plus.com>

**Re: Solve Limitations**

**Re: Types in Mathematica thread**

**Re: Re: Types in Mathematica thread**

**Re: Re: Types in Mathematica thread**