Unwanted hold in recursive function

Question

I have a function (let it be called f) that does something useful for me and I want to be able to apply it to the elements of a list regardless of their depth and keep the list structure. For example I want to write

F[{{a,b},{c}}]

and get

{{f(a),f(b)},{f(c)}}

So my idea was to use Thread to move down one level of the list each time. So I wrote

F[mat_] := If[mat[[0]] === List, Thread[F[mat]], f[mat]]

But the result I get

If[Hold[Evaluate[{{a, b}, {c}}[[0]] === List]], 
    Thread[F[{{a, b}, {c}}]], f[{{a, b}, {c}}]]

after of course the recursion depth was reached.

So I actually have 2 question. Is there any way to do that with a built-in mathematica function. How can I avoid getting this hold? Evaluate doesn't work.

EDIT: As pointed by Rojo my problem is solved by adding Listable to the attributes of f. However I would like to know why my code does not work. How can I get rid of the hold?

Answer 1

A simple solution to your problem is indeed to give f the Listable attribute. This threads f automatically over lists when they are given as arguments

SetAttributes[f, {Listable}];
f[{{a, b}, {c, d}}]

(* {{f[a], f[b]}, {f[c], f[d]}} *)

To understand why your approach does not work you would have to study the Mathematica evaluation process carefully. Let's see whether I can explain understandably what goes wrong in your definition of F. First we assume, that you have a very very deeply nested list as argument and therefore your If will go the True path for quite some time. This reduces your definition to

F[mat_] := Thread[F[mat]]

You assumed now that the right part just takes the F and threads it inside the list. With this you would have reduced your nesting by one. This does not happen. The reason is, that Thread has no special evaluation attribute like HoldFirst. Therefore, it uses standard evaluation.

Let us construct a small example, where you see what this means by defining two symbols

func := (Print["func"]; func1);
arg := (Print["arg"]; arg1);

No magic happens here, the only thing you have to know is, that the moment func is evaluated, it first prints "func" and then returns func1. The definition of arg is equivalent. The question is now, what happens if you call

func[arg]

Think before executing it and think after you saw what happened. This reveals a small part of the evaluation process: First, the head which is func is evaluated and after that all (in this case only one) parameters are evaluated. What you get is func1[arg1].

And now think about, what happens in the body of your function F. You call F with {{a,b},{c,d}} and you get

Thread[F[{{a,b},{c,d}}]]

Now this expression is subject to the same evaluation process. This means, first the head Thread is evaluated which stays the same. At this point the arguments are evaluated: Unfortunately, evaluating F[{{a,b},{c,d}}] is the same thing we started with and therefore it undergoes the same evaluation.

This leads to calling F over and over again until it is stopped by the $RecursionLimit. Your F never reaches the point where it is threaded over the list.

If you understood it so far, your first reaction might be: "but I don't want Thread to evaluate its argument". Then tell Thread, that it should hold it. The next is only for demonstration purpose! I'm using your original definition of F

ClearAll[F]

Unprotect[Thread];
SetAttributes[Thread, {HoldFirst, Protected}]

F[mat_] := If[mat[[0]] === List, Thread[F[mat]], f[mat]]
F[{{a, b}, {c, d}}]

(* {{f[a], f[b]}, {f[c], f[d]}} *)

A better way, to keep single arguments from evaluation is to use Unevaluated like shown in the comment of Leonid. With this you don't need to screw with built-in functions. First reset the attributes of Thread

Unprotect[Thread];
Attributes[Thread] = {Protected}

and then you can use the definition

F[mat_] := If[mat[[0]] === List, Thread[Unevaluated@F[mat]], f[mat]]

or you forget about this and stay with the Listable attribute which is shorter and faster in execution.