Apply function to subsets of a sequence generated by dropping the head incrementally

user_268581 0
Viewed 34

Intro

Let's say I have the following sequence:

var ls = new[]{10, 20, 30, 40};

I'd like to apply a function to:

  • The entire sequence
  • The entire sequence except the first
  • The entire sequence except the second
  • ...

Implementation

Here's one approach to implementing this:

IEnumerable<U> f_a<T,U>(IEnumerable<T> seq, Func<IEnumerable<T>, U> proc) =>
    Enumerable
        .Range(0, seq.Count())
        .Select(n => seq.Skip(n))
        .Select(proc);

Examples

Example: join the subsets:

enter image description here

Example: sum the subsets:

enter image description here

Example: sum the subsets and show the seq:

enter image description here

(Examples generated in dotnet-interactive in vscode.)

Question

Is there already a built-in function that basically performs f_a above?

If not, would you recommend another approach to implementing f_a?

Does the equivalent of f_a exist in libraries from other languages?

algorithm functional-programming linq c#
1 Answers

I'm not aware that there's anything exactly like that in the .NET base class library, although I'm fairly sure that you could implement it with Aggregate.

In Haskell, the first part of the function is available in the base library as the tails function. It takes a sequence of values and "returns all final segments of the argument, longest first".

Since functional values are composable, there's no reason to make a building block (function) more complicated than that. If you want to apply a function to each of the subsets, you simple map over each of them. In C#, assuming that you have a similar Tails extension method, you can implement the above examples like this:

[Fact]
public void Join()
{
    var ls = new[] { 10, 20, 30, 40 };
    var actual = ls.Tails().Select(seq => string.Join(",", seq));
    Assert.Equal(new[] { "10,20,30,40", "20,30,40", "30,40", "40" }, actual);
}

[Fact]
public void Sum()
{
    var ls = new[] { 10, 20, 30, 40 };
    var actual = ls.Tails().Select(seq => seq.Sum());
    Assert.Equal(new[] { 100, 90, 70, 40 }, actual);
}

[Fact]
public void SubsetAndSum()
{
    var ls = new[] { 10, 20, 30, 40 };
    var actual = ls.Tails().Select(seq => (seq, seq.Sum()));
    Assert.Equal<IEnumerable<(IEnumerable<int> seq, int)>>(
        new[] {
            (new[] { 10, 20, 30, 40 }.AsEnumerable(), 100),
            (new[] { 20, 30, 40 }, 90),
            (new[] { 30, 40 }, 70),
            (new[] { 40 }, 40)
        },
        actual);
}

These examples use xUnit.net.

You can implement Tails as an extension method like sketched in the OP, but I also think that other implementation options are possible.

user_1260140
Related