I assume by concrete type, you mean the actual run-time manifested type of an object. If that's true, you're slightly wrong. Most linq methods have parallel definitions for IQueryable<T>. (For those that don't, IQueryable<T> also extends IEnumerable<T>, so that's always a fallback.)
In practice this means that not all linq methods return IEnumerable<T>. x.Where(...) may return a statically typed IEnumerable<T> or an IQueryable<T> depending on whether x was IQueryable<T>.
Edit: I don't think linq would even actually improve by having this kind of fancy stuff. I don't want .Where() called on an array to return another array. I want a lazy IEnumerable<T> almost every time. I might want to consume only the first 10 elements from the filtered result. Allocating a whole 100000 array could be a tremendous waste of time.
> I don't want .Where() called on an array to return another array. I want a lazy IEnumerable<T> almost every time.
Yes, good point. There is a lot of space to explore in collections API designs, and the LINQ design is just one of them that makes its own tradeoffs (e.g., only have to implement "GetEnumerator()" to get a watered-down monadic experience). Contrast that with the well-meaning but convoluted and buggy Scala collections API (very difficult for novices to create a custom collection due to CanBuildFrom and other tricky stuff).
Paul Phillips came up with a pretty neat collections API [1, 2] that provides a nice feature set, including high-performance and typesafe views when you don't really want to wastefully create a temporary collection just to interact with the first 10 elements.
Thanks - you are right about the IQueryable/IEnumerable distinction - it's been a long time since I worked with C#. I think it is somewhat unfortunate that IQueryable is a subtype of IEnumerable because the semantics are so different and one can be so easily coerced into the other.
For an alternative example of limitations induced by lack of higher-kinded type abstraction, imagine implementing an Option/Maybe type [1] in C# and piggybacking on LINQ. Under the LINQ API, if you try to do anything with an instance of your Option/Maybe, its static type gets obliterated into an IEnumerable, which destroys the semantics. (The fact that the thing is an Option/Maybe and not, say, a list of things, is important for reasoning about, building, and abstracting over things.)
Rather than a tragedy, I think linq is quite brilliant. As for writing a linq-query compatible option implementation, I think you're wrong. I've written one. You can play with it here. https://dotnetfiddle.net/2hzRtE No IEnumerable<> to be seen.
Incidentally, I think I might have just now understood what a monad even is. All those years of reading blog posts are finally starting to pay off!
Nice Maybe implementation! The thing that you miss out on with that particular style of implementation, though, is that you don't get certain higher-order functions for free. For example, if you were to endow your Maybe implementation with a "GetEnumerator" method, then you would get all of the other LINQ methods for free (at the expense for losing your "Maybe"-ness as its static type is transmogrified into a vanilla IEnumerable). With higher-kinded types, you could potentially gain a whole host of methods for free that would, in contrast to LINQ, return a Maybe<T> instead of just an IEnumerable<T>, but you would still just need to provide a small handful of manually-implemented methods (e.g., Select, SelectMany, Where, etc.).
> Under the LINQ API, if you try to do anything with an instance of your Option/Maybe, its static type gets obliterated into an IEnumerable, which destroys the semantics.
This isn't true. It's only true if you derive your Option type from IEnumerable, but you can provide your own implementation of Select, SelectMany, and Where to maintain the Option type - this is my implementation [1], with SelectMany returning Option [2]. Granted, it doesn't make it a higher-kinded type, but you don't have to use IEnumerable to use LINQ.
I must not have been clear about what I meant. What I mean is that, if you do it your way and just implement Select and SelectMany, that's all you get - you don't get any of these 143 methods [1] for free.
Higher-kinded type support would improve the ability to abstract over these kinds of things and allow API designers to get more for free without repeating oneself time and time again.
> What I mean is that, if you do it your way and just implement Select and SelectMany, that's all you get - you don't get any of these 143 methods [1] for fre
I agree with your initial statement about LINQ, it is indeed true that implementing Select only allows your type to work with the LINQ grammar, it doesn't magically make an instance of a functor type-class.
But I do disagree that implementing Select and SelectMany should by default give you access to the 143 methods. For example Aggregate (Fold) can't be implemented in terms of Select and SelectMany. There should be a Foldable type-class (interface), a Monad type-class, a Functor type-class, etc. And if you want your new type (say Option) to be a member of those type-classes then you should provide an instance (like Haskell) that implements the interface of the type-class.
That's what I'm in the process of doing with the language-ext project, because it is possible (and I guess even MS missed that opportunity when they developed LINQ, because it seems that not only is it possible, it is fast and efficient with no special rules in the compiler for Select, SelectMany, Where).
In practice this means that not all linq methods return IEnumerable<T>. x.Where(...) may return a statically typed IEnumerable<T> or an IQueryable<T> depending on whether x was IQueryable<T>.
Edit: I don't think linq would even actually improve by having this kind of fancy stuff. I don't want .Where() called on an array to return another array. I want a lazy IEnumerable<T> almost every time. I might want to consume only the first 10 elements from the filtered result. Allocating a whole 100000 array could be a tremendous waste of time.