Recursive list contruction

Question

I am attempting to implement the exercises from The Little Schemer in Mathematica, and running to a bit of a challenge with rember (remove member). Given a list and a value, the function just returns the list with occurrences of value removed.

rember[a_, lat_] :=
 Return[
  If[NullQ[lat],
   Return[lat]
   ,
   If[a == First[lat],
    Return[rember[a, Rest[lat]]],
    Return[Cons[First[lat], rember[a, Rest[lat]]]]
    ] 
   ]
  ]

I created the helper functions NullQ and Cons based on The Little Schemer as well, with NullQ being true/false if a list is Null, and Cons being a wrapper around Prepend:

Cons[a_, lst_] :=
If[x === Null, Return[{a}], Return[Prepend[lst, a]]]


NullQ[x_] := If[ListQ[x],
   If[Length[x] == 0,
    Return[True],
    Return[False]]
   , Return[False]
   ];

The idea in rember is if it's Null, the recursion ends, otherwise it checks the first item of the list, if that's a match it calls remember with the remainder of the list, if it's not a match it prepends that value onto calling rember with the remainder of the list.

I think my logic is correct, but returns are not working correctly. How do I construct this list recursively? I'm sure my code is bad on several levels, thank you in advance for any advice you have.

EDIT: corrected code to not return a serially.

Answer 1

Please read carefully the post that Leonid referred to. Let me anyway give you some tips on your code. First, Return does work differently in Mathematica than you might would expect. You can use Return to return from functions or loops like this one

Do[
  If[x == 5, Return[True]],
  {x, 10}
]

What you did is to nest it which doesn't work like you expect it. Here is a simple example that shows the mistake

abs[x_] := Return[If[x > 0, Return[x], Return[-x]]]
abs[5]
(* Return[5] *)

The question is, why use it at all? It is not required. When you call a function, Mathematica will happily return the last expression. That means, you don't need it at all (your Cons line prepended the wrong element, x === Null in Cons doesn't make sense, ...). Here is a slightly fixed version of your original approach:

Cons[a_, lst_List] := Prepend[lst, a];

NullQ[{}] = True;
NullQ[___] := False;

rember[a_, lat_] := If[NullQ[lat], lat,
  If[a == First[lat], rember[a, Rest[lat]],
   Cons[First[lat], rember[a, Rest[lat]]]]
  ]

rember[5, Range[10]]
(* {1, 2, 3, 4, 6, 7, 8, 9, 10} *)

Let me give you a different method. It uses a nested list structure that is built up inside of a recursive function (don't forget to ClearAll[rember] first):

rember[a_, l_] := Flatten[r[a, l, {}]];
r[_, {}, out_] := out;
r[a_, {a_, rest___}, out_] := r[a, {rest}, out];
r[a_, {start_, rest___}, out_] := r[a, {rest}, {out, start}]

The rember function here acts only as a wrapper to call the core function r that does the job. When the tail recursive function r has done its job, the resulting nested list needs to be flattened.