Re: Re: Types in Mathematica thread

*To*: mathgroup at smc.vnet.net*Subject*: [mg62867] Re: [mg62833] Re: Types in Mathematica thread*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Tue, 6 Dec 2005 23:11:13 -0500 (EST)*References*: <dmp9na$hi2$1@smc.vnet.net> <200512060504.AAA02828@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Jon Harrop wrote: > Kris Carlson wrote: > [...] >>5. Mathematica excels in pattern-matching, > > > Mathematica certainly provides a lot of functionality in its pattern matcher > but pattern matchers in other languages provide many benefits not found in > Mathematica: > > 1. Exhaustiveness checking > 2. Redundancy checking > 3. Well-defined performance > > For example, the conventional implementation of a function to compute the > length of a list has quadratic complexity in Mathematica: > > 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. > 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. 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). > 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. Daniel Lichtblau Wolfram Research

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