Suggestion - private, default parameters for recursive methods

[jcouv]

@series0ne commented on Wed Nov 29 2017

Scenario
Consider the following method that implements the Fibonacci algorithm:

public static IEnumerable<int> Fibonacci(int a, int b, int n, List<int> list = null)
{
    list = list?.AddAndReturn(b) ?? new List<int>(new int[] { a, b });
    return list.Count < n ? Fibonacci(b, a + b, n, list) : list;
}

This allows me to pass Fibonacci arguments a and b, an iteration count n, and an optional argument list to append Fibonacci values to (used explicitly within the method).

Example

IEnumerable<int> fibonacciSequence = Fibonacci(0, 1, 20);

Problem
The method leaks an implementation detail (the list) and allows any populated list to be passed in, thus yielding invalid results:

List<int> random = new List(new int[] { 123, 456, 789 });
IEnumerable<int> fibonacciSequence = Fibonacci(0, 1, 20, random);

Solution
A method parameter could allow private modification, provided that:

1. The parameter provides a default argument.
2. The method is recursive.

This would prevent leaking implementation details of the method to the outside, whilst allowing the parameter to be set internally; for example:

public static IEnumerable<int> Fibonacci(int a, int b, int n, private List<int> list = null)
{
    list = list?.AddAndReturn(b) ?? new List<int>(new int[] { a, b });
    return list.Count < n ? Fibonacci(b, a + b, n, list) : list;
}

As illustrated from the example above, the list argument can be set explicitly from inside the method, however the following would raise a compilation error:

Fibonacci(0, 1, 20, random);
// Error: parameter is inaccessible.

Workaround
As of C# 7.0, it's possible to use a local method, however this just wraps the current method inside another method that does not expose the list parameter:

public static IEnumerable<int> Fibonacci(int a, int b, int n)
{
    IEnumerable<int> Fibonacci(int a1, int b1, int n1, List<int> list)
    {
        list = list?.AddAndReturn(b1) ?? new List<int>(new int[] { a1, b1 });
        return list.Count < n1 ? Fibonacci(b1, a1 + b1, n1, list) : list;
    }
    
    return Fibonacci(a, b, n, null);
}

I don't particularly like the workaround, because it requires duplicated, but different parameter names, and it just seems a bit...hacky.

---

@HaloFour commented on Wed Nov 29 2017

Language proposals belong on the CSharpLang repository.

---

@series0ne commented on Wed Nov 29 2017

@HaloFour can this be migrated?

[yaakov-h]

The traditional way I've seen this dealt with is with two methods - a public kickoff method, and a private recursive method.

public static IEnumerable<int> Fibonacci(int a, int b, int n)
    => FibonacciCore(a, b, n, null);
    
static IEnumerable<int> FibonacciCore(int a, int b, int n, List<int> list)
{
    list = list?.AddAndReturn(b) ?? new List<int>(new int[] { a, b });
    return list.Count < n ? FibonacciCore(b, a + b, n, list) : list;
}

Does this really warrant simplification through a language change?

[iam3yal]

@yaakov-h and now that we have local functions it can be slightly better:

public static IEnumerable<int> Fibonacci(int aa, int bb, int nn) 
{
	IEnumerable<int> FibonacciCore(int a, int b, int n, List<int> list)
	{
		list = list?.AddAndReturn(b) ?? new List<int>(new int[] { a, b });
		return list.Count < n ? FibonacciCore(b, a + b, n, list) : list;
	}

	return FibonacciCore(aa, bb, nn, null);
}

p.s. Just read the whole OP and noticed that the poster already posted it. :D

[iam3yal]

Just an idea, to solve the duplication problem it might be possible to come up with something like this:

public static IEnumerable<int> Fibonacci(int a, int b, int n) 
{
	IEnumerable<int> FibonacciCore(... t, List<int> list)
	{
		list = list?.AddAndReturn(t.b) ?? new List<int>(new int[] { t.a, t.b });
		return list.Count < t.n ? FibonacciCore((t.b, t.a + t.b, t.n), list) : list;
	}

	return FibonacciCore(..., null);
}

The ... operator means pass all the parameters of the main method to the local function as a tuple.

Would be equivalent to the following code:

public static IEnumerable<int> Fibonacci(int a, int b, int n) 
{
	IEnumerable<int> FibonacciCore((int a, int b, int n) t, List<int> list)
	{
		list = list?.AddAndReturn(t.b) ?? new List<int>(new int[] { t.a, t.b });
		return list.Count < t.n ? FibonacciCore((t.b, t.a + t.b, t.n), list) : list;
	}

	return FibonacciCore((a, b, n), null);
}

[bondsbw]

I like the proposed concept, despite the existence of workarounds. It's a much cleaner way to address a fairly common need.

[bondsbw]

Though the syntax would conflict with #804 (parameter properties).

Here's an idea:

public static IEnumerable<int> Fibonacci(int a, int b, int n, local List<int> list = null)
{ ... }

[DavidArno]

If we are into rewriting the example code, then expression-bodied members, for the win:

public static IEnumerable<int> Fibonacci(int a, int b, int n) =>
    FibonacciCore(a, b, n, new List<int>(new int[] { a, b }));

private static IEnumerable<int> FibonacciCore(int a, int b, int n, List<int> list) =>
    list.AddAndReturn(b) is var newList && newList.Count < n 
        ? FibonacciCore(b, a + b, n, newList) 
        : newList;

😆

However, I actually really like this proposal. I often write such public-private method pairs and using private (or local, as @bondsbw suggests) offers a neat solution to this.

Of course, tail recursion optimisation would be nice too here 😉

[MkazemAkhgary]

local functions can already achieve what you want and I think its clean enough. who said you cant use local variables inside enclosed local functions?

public static IEnumerable<int> Fibonacci(int a, int b, int n)
{
    IEnumerable<int> Fibonacci(List<int> list)
    {
        list = list.AddAndReturn(b);
        (a, b) = (b, a + b);
        return list.Count < n ? Fibonacci(list) : list;
    }

    return Fibonacci(new List<int>{ a, b });
}

works perfectly fine. without need to redefine signature.

[MrMatthewLayton]

Hi guys, the OP here. For those of you who've suggested using local functions to solve this problem, did you see my workaround?

From the responses I'm seeing, it seems to have divided opinions, though I concur with @bondsbw that local would likely be better than private.

Does it warrant a language change? - Well, I don't think there'd be any need to change the CLR; something like this could just be checked at compile time, thus it would essentially just be syntactic sugar. But that's not what you asked, right? Does it warrant a language change? - I don't know. I feel like this should be discussed extensively by the community, and decided by @MadsTorgersen and his team.

[iam3yal]

@MkazemAkhgary Didn't know you can do that, it actually works.

[MrMatthewLayton]

@MkazemAkhgary I think I find your workaround the most elegant of them. Perhaps this is enough.

[HaloFour]

I don't like this for the reason that it leaks implementation details into the signature of the method. There's no mechanism within the CLR through which this kind of parameter can be enforced and a compiler check is a weak defense at best. There are many compilers in the ecosystem which would all have to be modified to recognize and enforce the rule. Down-level versions of C# would blissfully ignore the constraint. The only way the compiler could provide any kind of airtight safety would be to silently emit another overload that doesn't accept the "private" members, but that could collide with other explicitly defined overloads.

In my opinion local functions are a suitable workaround. The entire reason local function scope is hoisted is to enable recursive scenarios like this.

[bondsbw]

@HaloFour:

I don't like this for the reason that it leaks implementation details into the signature of the method.

I assumed this wouldn't leak, but would effectively be rewritten into the local function equivalent.

[yaakov-h]

I assumed so as well, but then you have the problem of overloads.

[CyrusNajmabadi]

The workaround doesn't seem hacky to me. It seems like it exactly expresses the intent. There is the actual visible method that people can use. And there is hte internal method that can do what you want. Trying to merge them doesn't seem to buy much.

Indeed, this is how i often do things with methods and local functions. The method exposes what i want, and local functions allow me to have a little internal space where i can do these sorts of machinations.

I'm also skeptical of the problem as stated:

The method leaks an implementation detail (the list) and allows any populated list to be passed in, thus yielding invalid results:

The local function is, by definition, only exposed locally to your method. It seems very overblown to have to protected that local function from your own method. Is there really that big a chance that you'll miscall this? It seems like for that to happen, you'd need a massively complex method to begin with. And, in that case, other refactorings would be more beneficial first before actually adding this language feature.