Functions vs. patterns

Functions are more concise and generally faster but patterns are a lot more expressive. When you don't need the expressive power of patterns you should probably use functions. I use down values more to set up the high level structure of my program and functions to implement the algorithms. But often I am lazy and use down values out of habit. When I am in exploratory mode I pretty much don't worry about the difference.

This example from the Mathematica docs shows one way down values are more expressive (dynamic programming):

fib[n_] :=
 Module[{f},
  f[1] = f[2] = 1;
  f[i_] := f[i] = f[i - 1] + f[i - 2];
  f[n]
  ]

The fact that you can add conditions and the like are another way patterns are more expressive:

f[x_?EvenQ] := 1
f[x_?PrimeQ] := 2
f[x_ /; x > 21 && x < 99] := 3
f[x_] := 4

Of course, you add conditional logic to functions and get a similar effect.

It's also a good idea to use functions when they are side-effect free and down values when there are possible side-effects but this is not something Mathematica enforces and is more of one of my philosophical preferences that comes from exposure to functional programming languages.

I am not sure why down values cause problems in CDF's and I would hope this gets fixed or lessened in future versions. It seems overly restrictive.

These two forms may be similar on the surface, but they are very different in terms of the underlying mechanisms invloved. In a sense, Function represents the only true (but leaky) functional abstraction in Mathematica. Functions based on rules are not really functions at all, they are global versions of replacement rules, which look like function calls.

One big difference is in the semantics of parameter-passing. For rules (and therefore functions based on rules), it is more intruding, in the sense that they don't care about the inner scoping constructs, while Function (with named arguments only) will care. Here is an example of what I mean:

Function[{x},Module[{x=2},x]][3]

(*
  ==> 2
*)

while

In[46]:= 
ClearAll[fn,a];
fn[x_]:=Module[{x=2},{Hold[x],x}]
fn[3]

During evaluation of In[46]:= Module::lvset: Local variable specification 
{3=2} contains 3=2, which is an assignment to 3; only assignments to symbols are allowed. >>

Out[48]= Module[{3=2},{Hold[3],3}]

and especially

In[49]:= 
Clear[a];
fn[a]

Out[50]= {Hold[a$840],2}

Another difference I want to mention is that, due to Function with names arguments beaing a leaky abstraction, passing it as an argument to another function is risky. In addition to the mentioned above post by @WReach, which exposes the essence of the problem, see this post for an example of a trouble that one can get into, in a more "realistic" situation.

That said, in many cases one may think of "functions" defined by rules as normal functions. Because of the powerful builtin rule - dispatching mechanism of rule-application, functions based on rules can be overloaded in very powerful ways, which adds expressive power, as noted by @Sal.

Additionally, while this is not often used, one can often use global pattern-based function definitions as local rules, to achieve rather non-trivial things. In this answer, I use this technique to illustrate how one can dynamically generated Mathematica code at run-time, with the ability to test it in the "interpreter" mode. To illusrate the power of this approach here, I will write a (simplistic, sloppy) macro which will remove the Map auto-compilation limitation mentioned by @Mike Honeychurch, at least for simple pattern-based functions:

ClearAll[withGlobalFunctions];
SetAttributes[withGlobalFunctions, HoldAll];
withGlobalFunctions[code_] :=
  With[{rules =   
       Flatten@Cases[ 
         Names["Global`*"], 
         s_ :> ToExpression[s, InputForm, DownValues]]
       },
    ReleaseHold[
       Hold[code] //. {
         HoldPattern[Map[f_Symbol, args__]] :> Map[f[#] &, args], 
         Sequence @@ rules
       }
    ]
];

Now, taking the same setup:

data = RandomReal[{0, 10}, {500000}];

In[114]:= 
Timing[Developer`PackedArrayQ[Map[square,data]]]
Timing[Developer`PackedArrayQ[tmp1=Map[square1,data]]]
Timing[withGlobalFunctions@Developer`PackedArrayQ[tmp2=Map[square2,data]]]

Out[114]= {0.031,True}
Out[115]= {0.015,True}
Out[116]= {0.032,True}

where what happened is that my macro has expanded the call to square2 before Map was used on it. This is quite non-trivial, becuase it was able to expand the cal square2[#] inside a pure function. This is actually the case of a constructive use of the mentioned above leaky functional abstraction - were Function a complete black box, and this would not be possible. Note that the transformation f->f[#]& is not always correct, since it leaks evaluation. I used it here as an example, but if one were to do it for real, more care must be taken.

The first example (using Function) is called a "pure function" or an "anonymous function". It is used (for example) when you do not want to bother to give a special name to your function. You just describe what it does when applied to its arguments. This is very similar to the pure mathematics

$x\mapsto f(x)$

notation. The emphasis here is on the "abstract" functional aspect (i.e. you think at the function as an object in a functional space).

Typical use is with some kind of options (often from built-in functions) as in:

FixedPoint[(# + 2/# )/2 &, 1`20, SameTest -> (Abs[#1 - #2] < 1*^-10 &)]

where you want to create "on the fly" - without giving a special name - a test function, or in

CellPrint[
 ExpressionCell[x, "Input", 
  CellEvaluationFunction -> (Style[ToExpression[#]^2, Red] &)]]

These are examples from the doc center.

As explained in other answers, its use is less user-friendly, so you will use it (much) less often than the regular

square2[x_] := x^2

style of definition.

I think it is generally a matter of preference.

For my purposes I typically use the second form because it is easier to set up multiple definitions given the same number of inputs and cleaner to perform validation on the inputs. I also find the code easier to understand and debug.

Here is a toy example.

f[x_Integer, y_Integer] := x*y
f[x_List, y_List] := Outer[Times, x, y]
f[___]:= $Failed

Which could be almost equivalently but IMO less cleanly written.

g = Function[{x, y}, 
      Switch[{x, y}, 
        {_Integer, _Integer}, x*y
        , 
        {_List, _List}, Outer[Times, x, y]
        , 
        ___, $Failed]
    ]

I'm at a loss at the moment for how to code that BlankNullSequence bit that would allow g[1] to return $Failed as f[1] would.

One place I often do use the "pure function" style (outside of say graphics options) is when programmatically building up functions.

Here is another toy example that will create a function on the fly that takes 2 or more arguments depending on the inputs to h and when applied to the same number of args, multiplies them. Silly, but you get the idea.

h[arg1_, arg2__] := 
  Block[{x, a},
     x = Table[Unique[a], {Length[{arg1, arg2}]}];
     Hold[Function][x, Times @@ x] // ReleaseHold
  ]

I find this sort of thing more difficult (though not impossible) to do with the f[x_]:= approach.

The second form is usually preferred over the first. This is because it is easier to write functions with multiple parameters (rather than #1, #2, ...), it is more straightforward to associate patterns and conditions on the parameters, and to define functions with variable numbers of parameters.