9

I often find myself wanting to use Head and Tail methods on IEnumerables, which don't exist as part of Linq. While I could easily write my own I wonder whether they have been purposefully left out. For example,

var finalCondition = new Sql("WHERE @0 = @1", conditions.Head().Key, conditions.Head().Value);
foreach (var condition in conditions.Tail())
{
  finalCondition.Append("AND @0 = @1", condition.Key, condition.Value);
}

So, what is the best practice regarding this with Linq? Is the fact that I keep finding uses for this a sign that I am not doing something recommended? If not then why was this common functional paradigm not implemented in Linq?

Jim Jeffries
  • 9,841
  • 15
  • 62
  • 103
  • 4
    First() and Last() or FirstOrDefault() – Serve Laurijssen Oct 25 '13 at 08:58
  • Oliver Sturm's book [_Functional Programming in C#_](http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0470744588.html) has a lot of downloadable source code. If I recall correctly this also contains extension methods for head and tail. – Gert Arnold Oct 25 '13 at 09:04
  • 1
    @GertArnold I have implemntations of them, question is more about whether this is considered best practice. – Jim Jeffries Oct 25 '13 at 09:06
  • I understand, that's why I don't consider this an answer :). But the book also elaborates on the practical use of functional programming techniques and specific restrictions in C#. It might take you further. (It's a while ago I read it). – Gert Arnold Oct 25 '13 at 09:12
  • 4
    @ServéLaurijssen, the tail of a list is not `Last()`. The tail is the list without its first element. See [here](https://msdn.microsoft.com/en-us/library/ee370479.aspx), [here](http://docs.racket-lang.org/reference/pairs.html#%28def._%28%28quote._~23~25kernel%29._list-tail%29%29), [here](http://sml-family.org/Basis/list.html#SIG:LIST.tl:VAL), and [here](http://www.erlang.org/doc/man/lists.html#nthtail-2). – kdbanman Dec 10 '15 at 20:19

4 Answers4

17

Technically, your Head would be .First() and your Tail would be .Skip(1). But maybe you can find a better solution? Like using .Aggregate() on your IEnumerable?

nvoigt
  • 75,013
  • 26
  • 93
  • 142
  • 2
    @MatthewWatson No, `tail` is not the last element. – sloth Oct 25 '13 at 09:18
  • 3
    @MatthewWatson Yes. The thing with the head/tail story is that you don't call head *before* tail, it's rather a concept to split a list. nvoigt is right in saying that OP's code is equivalent to calling first/skip(1), and it's not a good example of the use of head/tail. – sloth Oct 25 '13 at 09:25
  • `.Skip(1)` isn't _technically_ the same as `tail` because it still evaluates the first item and then discards it, e.g. `list.Select(mapper).Skip(1)` will run `mapper(list([0]))` – pmoleri Aug 24 '16 at 21:06
  • 1
    Well, while `.Skip(1)` does indeed evaluate the first element, the fact that `mapper(list([0]))` is run in your example is due to not doing it in the correct order. Doing `list.Skip(1).Select(mapper)` will not run `mapper` on the first element. – nvoigt Aug 25 '16 at 03:52
8

Given the interface of IEnumerable<T>, performance can not always be ensured.

You note that most functional programming languages implement tail and head. However it should be noted that these languages are acting on in memory constructs.

IEnumerable<T> does not have any such constraints, and thus it cannot be assumed that this would be efficient.

A common functional pattern for example would be to recursively work on the Head of a collection and then recurse on the Tail of the call...

If you did this with Entity Framework for instance, you would send the following (meta) call to the SQL server, tight looped.

Select * from
(
    Select * from
    (
         Select * from
         (...)
         Skip 1
    )
    Skip 1
);

Which would be highly inefficient.

EDIT:

Come to think about it. Another reason, is that C#/VB.Net doesn't support tail recursion, and thus, this pattern can easily cause a StackOverflow.

Aron
  • 15,464
  • 3
  • 31
  • 64
  • 2
    This answer is incorrect and irrelevant. It should not be accepted. An `IEnumerable` tail is easily accessible by [`.Skip(1)`](https://msdn.microsoft.com/library/bb358985(v=vs.100).aspx), and there are no performance surprises whether the structure is in memory or not. `IEnumerable` classes are *designed* to move one element at a time, and that's all `Skip(1)` does. Performance surprises only come when you need to count an `IEnumerable`, or skip to an element in an arbitrary "index". – kdbanman Dec 10 '15 at 20:27
  • @kdbanman skip and Enumerator.GetNext() are different things. – Aron Dec 10 '15 at 20:28
  • 1
    Generally, yes you're right. The worst case for Skip(N) is to call GetNext() internally N times. [That's not necessary in all cases](http://stackoverflow.com/a/20003312/3367144), but let's pretend it is. It's still not a problem here even in that worst case. **Skip(1) returns the tail, which is what OP asked for, and Skip(1) only makes a single deferred call to GetNext().** – kdbanman Dec 10 '15 at 20:45
  • [Here](http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,90ccdbd47b57182e) is the actual .NET implementation of the `Skip<>` extension method on `IEnumerable`. It's easy to see my point. Skip(1) only makes a single deferred call to MoveNext(), which is the bool returning version of GetNext(). – kdbanman Dec 10 '15 at 20:52
  • Hold on a second. In what sense does C#/VB.Net not support tail recursion? I may be missing something here, but the tail call optimization has been part of .NET for quite awhile (perhaps since 1.0?). To quote David Broman: "[Both the source->IL and IL->native compilers understand the tail call optimization](https://blogs.msdn.microsoft.com/davbr/2007/06/20/enter-leave-tailcall-hooks-part-2-tall-tales-of-tail-calls/)". I can specifically recall at least one debugging session where I thought "how'd I get to this stack frame from with that return address? Oh, yeah - tail call elision") – unbob Mar 06 '18 at 12:52
  • @unbob Tail recursion had been a part of the CLR for a long time. It's just that the compilers for C# and VB.net do not support it (not sure now, since I haven't followed .net for years) – Aron Mar 06 '18 at 15:57
1

Because the "Head & Tail" concept is used in functional programming for pattern matching and recursive calls. Since C # does not support pattern matching, then there is no need to implement head() and tail () methods.

let rec sum = function
  | [] -> 0
  | h::t -> h + sum t

As for your case - you should use Aggregate method.

Dzmitry Martavoi
  • 6,867
  • 6
  • 38
  • 59
  • C# now supports (limited) [pattern matching](https://learn.microsoft.com/en-us/dotnet/csharp/fundamentals/functional/pattern-matching) and [deconstruction](https://learn.microsoft.com/en-us/dotnet/csharp/fundamentals/functional/deconstruct). Agreed that Aggregate is a fit for the OP, but depending on context, the IEnumerable overload of [String.Join](https://learn.microsoft.com/en-us/dotnet/api/system.string.join?view=net-7.0) and [string interpolation](https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/tokens/interpolated) may fit, too – unbob Aug 08 '23 at 23:23
0

I'm not suggesting the use of this in production code, but I was trying to explain a Haskell snippet to some friends who know C# and found that I could kinda, sorta get there by mixing IEnumerable<T> and IEnumerator<T> (which you can, because IEnumerable always gives you GetEnumerator() and you can convert IEnumerator to IEnumerable using a iterator (yield return). The iterator gives you the benefit of simulated laziness (in some contexts, if used correctly).

IEnumerable<int> sieve(IEnumerable<int> l)
{
    var (p, xs) = getHeadAndTail(l);
    yield return p;
    foreach (var n in sieve(xs.Where(i => i % p > 0)))
        yield return n;
}

(T, IEnumerable<T>) getHeadAndTail<T>(IEnumerable<T> l)
{
    var e = l.GetEnumerator();
    e.MoveNext();
    var head = e.Current;
    return (head, tailGetter());

    IEnumerable<T> tailGetter()
    {
        while (e.MoveNext())
            yield return e.Current;
    }
}

(to purists - in the original context, those are both local functions, so they start with a lower case letter)

I suspect there's a way to do this without (explicitly) introducing IEnumerator (probably still involving iterators), but I haven't yet stumbled on it.

(While poking around today, I just discovered that IEnumerator<T> implements IDisposable, while IEnumerator does not. Geez, the stuff ya never notice)

unbob
  • 331
  • 3
  • 7