LINQ is an implementation though (LINQ-to-Objects even more so). Specific (ie. not the theoretical/abstract concept) implementations of query operators can be slow because of generating more computation than is actually needed to produce the result. Also even the theoretical performance of a query operator depends on the underlying collection, doing a search or filter on a sorted list for instance, it can benefit from performant concrete algorithms that take advantage of order (eg. binary search). But only if the implementation chooses to do so..
That's true, but that's the confusion. If someone said, functions are slow, you'd ask WTF do you think that, and if they said, because the standard library functions are not the best for what I want, then you'd say, ok, there are tradeoffs made, but you are free to implement your own function that deals with your particular needs. My point, again, is LINQ is sold like it's a concrete implementation, but the abstract concept is what matters, and is really relevant. We can optimize the hell out of LINQ implementations - and what we are really doing is using monads to compose code. MS screwed up a bit by making LINQ about implementation, and not adequately explaining the most abstract nature. Well, I actually don't think they screwed up ... I mean, C9 did a TON to make monads and Rx and all that reach us, but somehow the message was lost.