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>
- Re: Types in Mathematica thread