Monadic programming in C #

Question

In Haskell, we have a filterM function. Source code for it:

 filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a] filterM _ [] = return [] filterM p (x:xs) = do flg <- px ys <- filterM p xs return (if flg then x:ys else ys) 

Translation from the notation:

 filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a] filterM _ [] = return [] filterM p (x:xs) = px >>= \flg -> filterM p xs >>= \ys -> return(if flg then x:ys else ys) 

As far as I understand, >>= in lists in Haskell and SelectMany on IEnumerable in C # is the same operation, so this code should work fine:

  public static IEnumerable<IEnumerable<A>> WhereM<A>(this IEnumerable<A> list, Func<A, IEnumerable<bool>> predicate) { // Like Haskells null if (list.Null()) { return new List<List<A>> {new List<A>()}; } else { var x = list.First(); var xs = list.Tail(); // Like Haskells tail return new List<IEnumerable<A>> { predicate(x).SelectMany(flg => xs.WhereM(predicate).SelectMany(ys => { if (flg) { return (new List<A> {x}).Concat(ys); } else { return ys; } })) }; } } 

But that will not work. Can someone point me to what is wrong here?

Answer 1

My C # is a little rusty, but it looks like your base code is wrong. You return the equivalent of [] (an empty list), while the Haskell version returns [[]] (a list containing an empty list).

The recursive case has the same problem. For example, in the else branch, the Haskell version returns [ys] , while your version returns ys . Remember that return in a monad list makes a single list of items and has nothing to do with the return keyword in C #.

Answer 2

It looks like your C # code is equivalent:

 filterM :: (a -> [Bool]) -> [a] -> [[a]] filterM _ [] = return [] filterM p (x:xs) = return $ px >>= \flg -> filterM p xs >>= \ys -> if flg then x:ys else ys 

those. return is in the wrong place.

I would expect something like this:

  return predicate(x).SelectMany(flg => xs.WhereM(predicate).SelectMany(ys => new List<IEnumerable<A>> { flg ? (new List<A> {x}).Concat(ys) : ys }))