CODEWITHSUNDEEP
listhaskellmonads
V0lvox337
V0lvox337

Reputation: 122

How to implement a function using bind (>>=)

I wrote a filter function:

f :: (a -> Bool) -> [a] -> [a]
f p xs = case xs of
         [] -> []
         x : xs' -> if p x
                    then x : f p xs'
                    else f p xs'

To understand bind, I want to implement this using bind. What I was thinking about:

f p xs = xs >>= (\x xs -> if p x then x : f p xs else f p xs)

But I get this error:

* Couldn't match expected type `[a]' with actual type `[a] -> [a]'
    * The lambda expression `\ x xs -> ...' has two arguments,
      but its type `a -> [a]' has only one
      In the second argument of `(>>=)', namely
        `(\ x xs -> if p x then x : f p xs else f p xs)'
      In the expression:
        xs >>= (\ x xs -> if p x then x : f p xs else f p xs)
    * Relevant bindings include
        xs :: [a] (bound at <interactive>:104:5)
        p :: a -> Bool (bound at <interactive>:104:3)
        f :: (a -> Bool) -> [a] -> [a] (bound at <interactive>:104:1)

Successfully did it using foldr:

f p xs = foldr (\x xs -> if p x then x : f p xs else f p xs) [] xs

What's going wrong?

Upvotes: 3

Views: 112

Answers (2)

Will Ness
Will Ness

Reputation: 71065

To understand bind, first implement the no-op:

id_list xs   =  concat [ [x]       | x <- xs ]  =  [ y | x <- xs, y <- [x      ] ]

Now for the filter, augment it as

filter p xs  =  concat [ [x | p x] | x <- xs ]  =  [ y | x <- xs, y <- [x | p x] ]

How is this code using bind, you ask? If we're using MonadComprehensions, it does.

The explicit do-notation re-write is straightforward:

id_list xs   =  do { x <- xs ; y <- [ x      ] ; return y }
filter p xs  =  do { x <- xs ; y <- [ x | p x] ; return y }

And of course, for lists,

[x]       ==  return x
[x | p x] ==  if p x then return x else mzero
mzero     ==  []
concat    ==  join

This brings us back to an explicitly recursive way to code filter as

filter p []     =  []
filter p (x:xs) =  [x | p x] ++ filter p xs

With bind, we think in terms of transforming each element of the list individually, into the list of results (none, one, or several) for that one input element. Your foldr-based code breaks this.

So, the code itself is just

filter_bind p xs  =  xs  >>=  (\x -> [x | p x])

because we have

xs >>= f  ==  join (fmap f xs) 
          ==  concat (map f xs) 
          ==  concat [ f x | x <- xs ]
          ==  foldr (++) []
                     [ f x | x <- xs ]

with the last snippet corresponding to the explicitly recursive definition above.

See also

Upvotes: 2

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476584

To understand bind, i want to implement this as bind.

There is no bind here. The bind is added in case of a do expression. The above is not a do-expression, so there is no bind here.

You can however write this with bind, like:

f p xs = xs >>= \x -> if p x then [x] else []

but this is not a literal mapping of the original function, we simply make use of the instance Monad [] implementation here. Nevertheless, your f is just filter :: (a -> Bool) -> [a] -> [a] here.

Upvotes: 4

Related Questions