Extension method for Enumerable.Intersperse?

Question

I learned the intersperse function from Haskell, and have been looking for an implementation in c#.

Intersperse takes 2 arguments, an IEnumerable<T> source and a T element. It returns an IEnumerable with element inserted between every element of source.

One possible use-case is to put an arbitrary integer in between a list of integers, for example:

// returns: {1, 0, 2, 0, 3}
(List<int>() {1, 2, 3}).Intersperse(0);

This is a general case of string.Join(...).

Joel Coehoorn · Accepted Answer · 2022-01-03T15:02:23.903

15

Something the others have missed: if you only want it in between items, and not also in front or behind, you need to do an extra check:

public static IEnumerable<T> Intersperse<T>(this IEnumerable<T> source, T element)
{
    bool first = true;
    foreach (T value in source)
    {
        if (!first) yield return element;
        yield return value;
        first = false;
    }
}

or

public static IEnumerable<T> Intersperse<T>(this IEnumerable<T> source, T element)
{
    var e = source.GetEnumerator(); 
    bool b = e.MoveNext();
    if (b) yield return e.Current;

    while (e.MoveNext())
    {
        yield return element;
        yield return e.Current;
    }
}

edited Jan 03 '22 at 15:02

answered Apr 15 '09 at 19:32

Joel Coehoorn

399,467
113
570
794

Your point makes sense, but I'm confused by your answer. It seems in your example that the interspersed item will come first, which I don't think is right. – Daniel Pratt Apr 15 '09 at 19:37
I like yours better anyway, Marc. It doesn't need a negation for the if block on only sets the flag once. – Joel Coehoorn Apr 15 '09 at 19:37
@Daniel: The first time through the loop it's not output at all, so a the first enumerated value is returned ahead of the first interspersed item. – Joel Coehoorn Apr 15 '09 at 19:38
@Daniel Pratt - no, the code looks fine to me. Joel's used the opposite meaning of "item" and "value" to me, but the code is right. – Marc Gravell Apr 15 '09 at 19:38
Ah, gotcha. Those pesky ! are so easy to miss. – Daniel Pratt Apr 15 '09 at 19:39
Updated my post with some less confusing names. – Joel Coehoorn Apr 15 '09 at 19:40
Is taking the conditional out of the loop any better, as in my solution? – Daniel Apr 15 '09 at 19:46
6 of 1... I like this better because it avoid repeating the "yield return i.Current;", and it's shorter. But it's probably just a matter of preference. – Joel Coehoorn Apr 15 '09 at 19:48
I'm choosing this answer because it was the first correct implementation. You all rock! This got answers faster than I could say "caramba!". – Daniel Apr 15 '09 at 19:49

score 7 · Answer 2 · edited Jul 09 '14 at 23:18

7

I've coded up a solution that is lazy, in the spirit of Linq solutions! Other solutions I came up with involved traversing the entire list before returning data, and then returning the resulting list.

Some of the other answers have an if check on every iteration of the loop.

public static IEnumerable<T> Intersperse<T>(this IEnumerable<T> source, T element)
{
    using (var enumerator = source.GetEnumerator()) {
        if (enumerator.MoveNext()) {
            yield return enumerator.Current;
            while (enumerator.MoveNext()) {
                yield return element;
                yield return enumerator.Current;
            }
        }
    }
}

edited Jul 09 '14 at 23:18

allonhadaya

1,297
7
19

answered Apr 15 '09 at 19:32

Daniel

1,613
2
14
25

1

When using GetEnumerator(), you should Dispose() the iterator – Marc Gravell Apr 15 '09 at 19:34
3

It's nice to eliminate branching in case the collection is large. By the way this is a classic "Fence Post Problem," where you need n+1 or n-1 things. `String.Join()` is the most common way C#ers come in contact with these. – Chris Moschini Jul 09 '14 at 23:27
@ChrisMoschini Handy to have a label to slap on the concept! – anton.burger Jul 31 '17 at 15:17

score 2 · Answer 3 · answered Apr 15 '09 at 19:32

It would be pretty easy to write:

public static IEnumerable<T> Intersperse<T>(this IEnumerable<T> source, T value) {
    bool first = true;
    foreach(T item in source) {
         if(first) { first = false; }
         else { yield return value; }
         yield return item;
    }
}

score 0 · Answer 4 · answered Mar 28 '20 at 11:27

Here is an example with more control over inserting the additional item:


public delegate T IntersperseFunc<T>(T prev, T next, int index);
public delegate T InterspersePrevNextFunc<T>(T prev, T next);
public delegate T IntersperseIndexFunc<out T>(int index);

public static IEnumerable<T> Intersperse<T>(this IEnumerable<T> source, IntersperseFunc<T> elementFunc)
{
    if (source == null) throw new ArgumentNullException(nameof(source));
    using (var enumerator = source.GetEnumerator())
    {
        if (enumerator.MoveNext())
        {
            var index = 0;
            var prev = enumerator.Current;
            yield return prev;
            while (enumerator.MoveNext())
            {
                var next = enumerator.Current;
                yield return elementFunc(prev, next, index++);
                yield return next;
                prev = next;
            }
        }
    }
}

public static IEnumerable<T> Intersperse<T>(this IEnumerable<T> source, InterspersePrevNextFunc<T> elementFunc)
    => Intersperse(source, (prev, next, index) => elementFunc(prev, next));

public static IEnumerable<T> Intersperse<T>(this IEnumerable<T> source, IntersperseIndexFunc<T> elementFunc)
    => Intersperse(source, (prev, next, index) => elementFunc(index));

public static IEnumerable<T> Intersperse<T>(this IEnumerable<T> source, Func<T> elementFunc)
    => Intersperse(source, (prev, next, index) => elementFunc());

public static IEnumerable<T> Intersperse<T>(this IEnumerable<T> source, T element)
    => Intersperse(source, (prev, next, index) => element);

Jason C · Answer 5 · 2021-06-11T21:17:48.070

Here are some other ways to do it. They should all be pretty performant, none require a full pass over the input sequence first. All of them handle empty input and single-item input correctly.

SelectMany

The way I prefer is this:

public static IEnumerable<T> Intersperse <T> (this IEnumerable<T> source, T delimiter) =>
    source.SelectMany((item) => Enumerable.Empty<T>().Append(delimiter).Append(item)).Skip(1);

Or, alternatively:

public static IEnumerable<T> Intersperse <T> (this IEnumerable<T> source, T delimiter) =>
    source.SelectMany((item) => new T[] { delimiter, item }).Skip(1);

They're both equivalent: For each item, create a new sequence { delimiter, item }, and use SelectMany to concatenate those all together. Afterwards, skip over the first delimiter -- it's just an extra. The only reason I prefer those over other options is they can be used inline in a pinch without having to write extra functions.

Here are a few other implementations (note I called them Delimit not Intersperse):

Aggregate

It can be done with Aggregate although I think it is clunky:

public static IEnumerable<T> Delimit2a <T> (this IEnumerable<T> source, T delimiter) =>
    source.Aggregate(Enumerable.Empty<T>(), (delimited, item) => delimited.Append(delimiter).Append(item)).Skip(1);

public static IEnumerable<T> Delimit2b <T> (this IEnumerable<T> source, T delimiter) =>
    source.Aggregate(null as IEnumerable<T>, (delimited, item) => (delimited?.Append(delimiter) ?? Enumerable.Empty<T>()).Append(item)) ?? Enumerable.Empty<T>();

2b is probably not worth considering: it omits the Skip(1) but at the cost of a lot of extra verbosity and branching.

yield return

These are similar to the other yield return based answers but with different approaches to handling the first element (cleaner, in my opinion):

public static IEnumerable<T> Delimit3a <T> (this IEnumerable<T> source, T delimiter) {
    foreach (T item in source.Take(1)) // protects agains empty source
        yield return item;
    foreach (T item in source.Skip(1)) {
        yield return delimiter;
        yield return item;
    }
}

public static IEnumerable<T> Delimit3b <T> (this IEnumerable<T> source, T delimiter) {
    static IEnumerable<U> Helper<U> (IEnumerable<U> source, U delimiter) {
        foreach (U item in source) {
            yield return delimiter;
            yield return item;
        }
    }
    return Helper(source, delimiter).Skip(1);
}

Test Code / Example

There is a runnable example with test code here. The test portion:

public static void Main () {
    foreach (int count in new int[] { 11, 2, 1, 0 }) {
        p( Enumerable.Range(10, count).Delimit1a(-1) );
        p( Enumerable.Range(10, count).Delimit1b(-1) );
        p( Enumerable.Range(10, count).Delimit2a(-1) );
        p( Enumerable.Range(10, count).Delimit2b(-1) );
        p( Enumerable.Range(10, count).Delimit3a(-1) );
        p( Enumerable.Range(10, count).Delimit3b(-1) );
    }
}

static void p <T> (IEnumerable<T> e) =>
    Console.WriteLine($"[ {string.Join(", ", e)} ]");

Outputs the following:

[ 10, -1, 11, -1, 12, -1, 13, -1, 14, -1, 15, -1, 16, -1, 17, -1, 18, -1, 19, -1, 20 ]
[ 10, -1, 11, -1, 12, -1, 13, -1, 14, -1, 15, -1, 16, -1, 17, -1, 18, -1, 19, -1, 20 ]
[ 10, -1, 11, -1, 12, -1, 13, -1, 14, -1, 15, -1, 16, -1, 17, -1, 18, -1, 19, -1, 20 ]
[ 10, -1, 11, -1, 12, -1, 13, -1, 14, -1, 15, -1, 16, -1, 17, -1, 18, -1, 19, -1, 20 ]
[ 10, -1, 11, -1, 12, -1, 13, -1, 14, -1, 15, -1, 16, -1, 17, -1, 18, -1, 19, -1, 20 ]
[ 10, -1, 11, -1, 12, -1, 13, -1, 14, -1, 15, -1, 16, -1, 17, -1, 18, -1, 19, -1, 20 ]
[ 10, -1, 11 ]
[ 10, -1, 11 ]
[ 10, -1, 11 ]
[ 10, -1, 11 ]
[ 10, -1, 11 ]
[ 10, -1, 11 ]
[ 10 ]
[ 10 ]
[ 10 ]
[ 10 ]
[ 10 ]
[ 10 ]
[  ]
[  ]
[  ]
[  ]
[  ]
[  ]

score -3 · Answer 6 · answered Apr 15 '09 at 19:31

If you're wondering how to implement it, I would do so like this:

public static IEnumerable<T> Intersperse<T>(this IEnumerable<T> collection, T value)
{
    foreach(T item in collection)
    {
        yield return item;
        yield return value;
    }

    yield break;
}

Extension method for Enumerable.Intersperse?

6 Answers6

SelectMany

Aggregate

yield return

Test Code / Example

Linked

Related