11

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(...).

6 Answers 6

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;
    }
}           
9
  • 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. Apr 15, 2009 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. Apr 15, 2009 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. Apr 15, 2009 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. Apr 15, 2009 at 19:38
  • Ah, gotcha. Those pesky ! are so easy to miss. Apr 15, 2009 at 19:39
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;
            }
        }
    }
}
3
  • 1
    When using GetEnumerator(), you should Dispose() the iterator Apr 15, 2009 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. Jul 9, 2014 at 23:27
  • @ChrisMoschini Handy to have a label to slap on the concept! Jul 31, 2017 at 15:17
2

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;
    }
}
0

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);
-1

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 ]
[  ]
[  ]
[  ]
[  ]
[  ]
[  ]
-3

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;
}
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.