What is the output of the method with nested generic type? like IEnumerable<IEnumerable<int>> Calculate()

Question

In Pascal’s triangle exercise in the exercism.io, the method signature is as below:

using System;
using System.Collections.Generic;

public static class PascalsTriangle
{
    public static IEnumerable<IEnumerable<int>> Calculate(int rows)
    {
        …
    }

}

It is obvious that the Calculate method is a method with nested generic type. I know that the IEnumerable<…> is the generic interface and it indicates the type of the method. And the IEnumerable is a generic interface and it works on the integer value type. But I cannot understand the meaning and purpose of the nested generic type, IEnumerable<IEnumerable>!

Here are my questions:

1. What does it mean exactly?
2. What should the returned type of the Calculate method be?
3. Although the Calculate method is not inherited from the IEnumerable interface, should I implement the IEnumerable.GetEnumerator()?

Answer 1

1. What does it mean exactly?

In order to grasp this, it might help to have an understanding of what IEnumerable<T> is, or what it represents. The definition from the docs is:

Exposes the enumerator, which supports a simple iteration over a collection of a specified type

In your case of IEnumerable<IEnumerable<int>>, the definition could essentially be translated to:

[...] supports a simple iteration over a collection of IEnumerable<int>s that each support a simple iteration over a collection of integers

Which results in the nested iteration behavior that can be represented by a "collection of collections". Pascal's triangle is a good example of this because you have just that:

[ // Outer collection 
[1], // Inner collection 1
[1,1], // Inner collection 2
[1,2,1], // Inner collection 3
... // Inner collection n
] 

An example of this in code would be:

IEnumerable<int> innerCollection1 = new List<int> { 1 };
IEnumerable<int> innerCollection2 = new List<int> { 1, 1 };
IEnumerable<int> innerCollection3 = new List<int> { 1, 2, 1 };
IEnumerable<IEnumerable<int>> outerCollection = new List<IEnumerable<int>>
{
    innerCollection1,
    innerCollection2, 
    innerCollection3
};

And then to get to the actual values inside, you need to iterate over each innerCollection within the outerCollection. For example:

foreach (IEnumerable<int> innerCollection in outerCollection)
{
    foreach (int value in innerCollection)
    {
        Console.Write(value);
        Console.Write(" ");
    }
    Console.WriteLine();
}

Which gives output as:

1
1 1
1 2 1

2. What should the returned type of the Calculate method be?

In C#, you can represent this using anything that implements IEnumerable<int>, for example a list of lists:

new List<List<int>>
{
    new List<int> { 1 },
    new List<int> { 1, 1 },
    new List<int> { 1, 2, 1 },
    // new List<int> { ... },
}

Or an array of arrays:

new int[][]
{
    new int[] { 1 },
    new int[] { 1, 1 },
    new int[] { 1, 2, 1 },
    // new int[] { ... },
}

Or a list of arrays:

new List<int[]>
{
    new int[] { 1 },
    new int[] { 1, 1 },
    new int[] { 1, 2, 1 },
    // new int[] { ... },
}

Or an array of lists:

new List<int>[]
{
    new List<int> { 1 },
    new List<int> { 1, 1 },
    new List<int> { 1, 2, 1 },
    // new List<int> { ... },
}

etc. etc.

3. Although the Calculate method is not inherited from the IEnumerable interface, should I implement the IEnumerable.GetEnumerator()?

You only need to implement IEnumerable.GetEnumerator() in a custom type that implements the IEnumerable interface. In your case, you can just return a type that already implements that interface (pretty much anything in System.Collections.Generic), as seen above. You'll obviously just need to build that instance dynamically given the amount of rows passed to the method, with a naïve example looking something like:

public static IEnumerable<IEnumerable<int>> Calculate(int rows)
{
    List<List<int>> outerList = new List<List<int>>();
    for (int i = 0; i < rows; i++)
    {
        List<int> innerList = new List<int>();
        // logic to build innerList
        outerList.Add(innerList);
    }
    return outerList;
}

Which when called, passing for example 3 as rows, should result in:

List<List<int>> outerList = new List<List<int>>
{
   new List<int> { 1 }, // innerList 1
   new List<int> { 1, 1 }, // innerList 2
   new List<int> { 1, 2, 1 } // innerList 3
}

Answer 2

It is obvious that the Calculate method is a generic method

Calculate is not a generic method. A generic method has angle brackets after the name with one or more "variables" in that are the unknown types you will refer to in the method, which mean they can look like:

MethodName<TypeReference>()
MethodName<TypeReference>(TypeReference param1)
TypeReference MethodName<TypeReference>()
MethodName<TypeReference1, TypeReference2>(TypeReference2 param1, TypeReference1 param2)

What you're doing in the angle brackets is establishing a name alias for the types that will be used at runtime. When an actual type is used, anywhere you used that alias will behave as if you used the actual type:

T MethodName<T>(T param1);

//if you call it with a string, i.e. var v = MethodName<string>("hello");
//it will behave as if you defined it like:
string MethodName(string param1)

//if you call it with an int, it will behave as if you defined it as:
int MethodName(int param1)

I know that the IEnumerable<…> is the generic interface and it indicates the type of the method.

Methods don't have a "type". They may return something that has a type and they may have parameters that are of a particular type, but in and of themselves methods have no type

But I cannot understand the meaning and purpose of the nested generic type, IEnumerable!

Just appreciate that that it's one type inside another, and it can repeat for a long time:

IEnumerable<string>

It's a type. It's not a string, it's something that contains a collection of string and it can be enumerated. IEnumerable is the entire type of the thing. just like string appears inside the angle brackets and string is a type, so too is IEnumerable<string> a type of thing. Because it's a type of thing it can appear inside the angle brackets of something else:

IList<string> //string is a type. It can appear inside angle brackets
IList<IEnumerable<string>> //IEnumerable<string> is a type, it can appear inside angle brackets

VB.NET's syntax might be clearer:

IList(Of String)
IList(Of IEnumerable(Of String))

Here are my questions:

What does it mean exactly?

It's an "x of y of z". If it were IEnumerable<IList<IEnumerable<string>>> it would be a "w of x of y of z". Other answers cover this in superb detail, so I won't

What should the returned type of the Calculate method be?

Something that can be enumerated, that is full of subthings that can be enumerated. And those enumerable subthings have to be collections of int. In your "x of y of z", x and y are collections and z is an int.

Although the Calculate method is not inherited from the IEnumerable interface, should I implement the IEnumerable.GetEnumerator()?

You don't inherit an interface, you implement it. Your class does not implement an IEnumerable because it doesn't seem to need to. If you wanted to provide a GetEnumerator method and be able to say foreach var whatever in myPascalsTriangle then you could implement IEnumerable.

Your method is declared to return some other type that already implements IEnumerable, so you just have to comply with that by providing a type that implements it. You do not have to implement it on this class that contains the method (just like you don't have to implement string every time you want to use a string)

--

The main takeaways from this answer for you should really be in firming up the terminology - I think you might be slightly confused as to classes vs methods vs interfaces vs return types vs implementations. Classes represent things, they implement interfaces which then means they can be guaranteed to have methods with certain names and that return certain types. This then means that they can be treated in a common way.. But there isn't any need for a class to implement an interface just so that it can have a method that returns another type of class that already implements that interface