CODEWITHSUNDEEP
haskellmonads
K Split X
K Split X

Reputation: 4747

Create a filter function for monads in haskell

Suppose we have a filter function.

filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]

Assume our a -> m Bool function is as such:

p :: Integer -> Maybe Bool
p n | n > 0 = Just True
    | n < 0 = Just False
    | otherwise = Nothing

In the example, m is Maybe.

I want to create the filterM function such that:

filterM p [2,−4,1] = Just [2,1]

filterM p [2,0,−4,1] = Nothing

Essentially this filterM is filter, but for monads.

Here is my implementation of it. It doesn't work, and I have a couple of questions about it.

filterM p [] = pure []
filterM p (x : xs) | p x == Just True = x : (filterM p xs)
                   | p x == Just False = filterM p xs
                   | otherwise = Nothing

Firstly, why doesn't it work. It says Couldn't match type m with Maybe m is a rigid type variable.

  Expected type: m Bool
  Actual type: Maybe Bool

In my function, I hardcoded "Maybe" as m, but how do I make this more generic?

I would use do notation but it doesn't seem like best option since there is recursion.

Upvotes: 2

Views: 1428

Answers (2)

Jon Purdy
Jon Purdy

Reputation: 54999

Your type error comes from specifying a type signature that is polymorphic (m) but an implementation that’s specialised to a particular m (Maybe)—you’ve told the typechecker this function works forall m, but it doesn’t.

In order to generalise this, you need to solve two other minor issues: first, you can’t use a general monadic condition in a guard, only a pure condition. Second, you can’t use the : operator on x and the result of filterM, since : is pure but you’ve given it a monadic argument.

For the monadic version, you can use do notation:

filterM p [] = pure []
filterM p (x : xs) = do
  px <- p x  -- Run the condition
  if px
    then do
      xs' <- filterM p xs  -- Run the recursive action
      pure (x : xs')       -- Build the result
    else filterM p xs

I would use do notation but it doesn’t seem like best option since there is recursion.

It’s perfectly fine to write recursive monadic code, with or without do notation, as you can see here—you just need to be aware of when you’re executing actions versus evaluating expressions.

The otherwise case in your original code is handled implicitly by the monadic bindings; if p x returns Nothing for m ~ Maybe then the whole computation will return Nothing.

If you want to avoid do notation, you can use the monad/functor combinators directly:

filterM p [] = pure []
filterM p (x : xs)
  = p x >>= \ px -> if px
    then (x :) <$> filterM p xs
    else filterM p xs

While <$> (fmap) is nicer here, I would personally prefer to use do over >>= with a lambda.

This can also be simplified somewhat by factoring out the repetition of filterM p and, since p doesn’t change within a call to filterM, just referencing it in a helper function.

filterM p = go
  where
    go [] = pure []
    go (x : xs) = do
      px <- p x

      -- Or: if px then (x :) <$> go xs else go xs
      xs' <- go xs
      pure (if px then x : xs' else xs')

Upvotes: 2

K. A. Buhr
K. A. Buhr

Reputation: 50929

There are two problems. The first is that you've given the type signature:

filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]

and then defined filterM with m specialized to Maybe (because you use Just and Nothing in your definition). When Haskell deduces that m must be Maybe, this results in an error. The type m is "rigid" in the sense that it was supplied by you in a type signature, and rigid types have to stay general; it's a conflict if they become less polymorphic than specified. You can generate a similar error message by writing:

badId :: a -> Int
badId x = x

Clearly, a is Int, and so it's a conflict that the rigid (programmer-specified) type a was determined to match Int during type checking.

However, even if you fix your type signature:

filterM :: (a -> Maybe Bool) -> [a] -> Maybe [a]
filterM p [] = pure []
filterM p (x : xs) | p x == Just True = x : (filterM p xs)
                   | p x == Just False = filterM p xs
                   | otherwise = Nothing

you'll still get an error message. You're mixing up monadic actions and values in your code. In the expression:

x : filterM p xs

you're applying the operator (:) :: b -> [b] -> [b] to the types a and Maybe [a], so it doesn't typecheck ("Couldn't match expected type Maybe [a] with actual type [a].")

You'll need to replace x : filterM p xs with something like:

case filterM p xs of
    Nothing -> Nothing
    Just xs' -> Just (x : xs')

Upvotes: 3

Related Questions