[Date Index] [Thread Index] [Author Index]

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>