LINQ SelectMany is bind?

Question

SelectMany will traverse an object tree:

class Agency { List<Employees> Staff }

IEnumerable<Agency> Agencies

IEnumerable<Employee> =  
from anAgency in Agencies  
from anEmployee in anAgency.Staff. 
select anEmployee; 

Usually, i would always pick an Agency first, and use the internal instance of Staff to get the employees. But in the case of a government shutdown, I just want to list EVERYBODY to see who can cover.

In this rare case which is inappropriate for my object model, i can use SelectMany to arbitrarily traverse the tree.

What do you call this traversal? a cross join?  It isn't because the joining is already implicit in the composition of the Staff in the Agency object.

Is it bind? I don't know anything about bind.

Has it no other name than Select, Many ?!

Answer 1

SelectMany in C# corresponds to bind in Haskell (>>=) or flatMap in Scala. The signature of >>= in Haskell is:

(>>=) :: Monad m => m a -> (a -> m b) -> m b

so bind is an operation used to construct one monadic value from another.

In the case of C# m in the above signature is IEnumerable, IObservable, IQueryable etc. For IEnumerable, SelectMany is therefore

IEnumerable<A> -> (A -> IEnumerable<B>) -> IEnumerable<B>

or in C#

public static IEnumerable<B> SelectMany<A, B>(this IEnumerable<A> first, Func<A, IEnumerable<B>> selector)

The meaning of bind depends on the monad type, for IEnumerable, each element in the input sequence is used to create a new sequence, and the resulting sequence of sequences is flattened to produce the output sequence.

There is another formulation of bind which may make this more clear. While monads are often described in terms of their implementation of bind, monads must also support two other operations, map and join.

map corresponds to Select in C# and looks like:

map :: Monad m => (a -> b) -> (ma -> m b)

so it is a 'structure preserving' way of lifting a regular function over a monadic value.

join has the type

join :: Monad m => m m a -> m a

so join is used to flatten nested monadic values. In C# this would look like

public static IEnumerable<A> Join<A>(this IEnumerable<IEnumerable<A>> nested)

bind can be implemented in terms of map and join as

m >>= f = join (map f m)

so to answer the original question, SelectMany corresponds to bind or flatMap in other languages. Bind is not just flattening, but can be seen as a transformation followed by a flattening of nested monadic values (e.g. sequences in the case of IEnumerable<T>). join for IEnumerable<T> does not exist in the current linq extensions.

Answer 2

Out of .NET world it's often called "flattening", if that's what you're asking. It flattens a two-dimensional result set into a single dimension.