# Recursive list contruction

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.

• The big difference between Mathematica and Scheme regarding lists is that while in Scheme they are essentially linked lists, in Mathematica they are arrays. This leads to all sorts of troubles when one tries to directly translate the list-manipulation code (particularly recursive functions) from Scheme to Mathematica. I do recommend to read this post of mine on linked lists in Mathematica - they are the closest analog in Mathematica for Scheme's lists, and they are well-suited to use with recursive code. – Leonid Shifrin Aug 8 '15 at 21:51
• reading, thanks! – Rick R Aug 9 '15 at 0:42

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
(* Return *)


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]
(* {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.

• great, thank you! – Rick R Aug 9 '15 at 0:43
• thanks for that last, I've been wrapping my head around the approach for a bit, and realizing that my original problem statement was incorrect (rember only removes the first occurrence of a_), gave a go to correct this to understand better: rember[a_, l_] := Flatten[r[a, l, {}]]; r[, {}, out] := out; r[a_, {a_, rest___}, out_] := r[a, {}, {out, rest}]; r[a_, {start_, rest___}, out_] := r[a, {rest}, {out, start}] – Rick R Aug 9 '15 at 16:34
• Are there specific names for the two approaches to the problem, or would you say that they are the same approach manifesting differently. It seems like in both cases, questions are being asked. In the approach outlined, the questions are being asked in the function body, whereas in the one you offer, the questions are being asked in the function definition. – Rick R Aug 9 '15 at 16:41
• Your definition doesn't work. Maybe something went wrong during the copying. You can find here another short implementation for your remove first problem. The approach I showed you uses one of the strengths of Mathematica: Pattern matching. This fits your situation better, because for implementing different cases that depend on the structure (like testing for an empty list), pattern matching is better readable than a nested If. Basically, every definition line shows one specific situation that can happen. Very readable once you got used to it. – halirutan Aug 9 '15 at 19:27
• hopefully just copying. Wrapping my head around the Pattern-matching style of mathematica, continuing to apply both methods to the problem set, it's a different and fascinating way to approach the problems. Thanks for your guidance. – Rick R Aug 10 '15 at 6:28