CODEWITHSUNDEEP
haskell
softshipper
softshipper

Reputation: 34099

Get wrong result by substituting through value

I have following function:

meh :: (Functor m, Monad m) => [a] -> (a -> m b) -> m [b]
meh [] _ = return []
meh (x:xs) f = do
  x' <- f x
  fmap ((:) x') (meh xs f)

then I try it out in prelude as follow and I've got:

*ExerciseMonad Control.Monad> meh [3,4,5] (\x -> Just x)
Just [3,4,5]

But I do expect [Just 3, Just 4, Just 5].

To find out, what went wrong, I did substitution:

meh [3,4,5] (\x -> Just x) = Just [3,4,5]

meh (3:[4,5])] (\x -> Just x) =
  Just 3 <- (\3 -> Just 3)
  fmap ((:) (Just 3)) (meh [4,5] (\x -> Just x))

meh (4:[5])] (\x -> Just x) =
  Just 4 <- (\4 -> Just 4)
  fmap ((:) (Just 4)) (meh [5] (\x -> Just x))

meh ([5])] (\x -> Just x) =
  Just 5 <- (\5 -> Just 5]
  fmap ((:) (Just 5)) (meh [] (\x -> Just x))

meh [] _ = return []  


--all the way back
meh ([5])] (\x -> Just x) = fmap ((:) (Just 5)) []
meh (4:[5])] (\x -> Just x) = fmap ((:) (Just 4)) [Just 5] <- result [Just 4, Just 5]
meh (3:[4,5])] (\x -> Just x) = fmap ((:) (Just 3)) [Just 4, Just 5] <- result [Just 4, Just 5]
meh [3,4,5] (\x -> Just x) = [Just 3,Just 4, Just 5]

As you can see, the substitution does not match to the right result:

Just [3,4,5] != [Just 3,Just 4, Just 5]

My question, what did I wrong with the substitution? That I've got the wrong result?

Upvotes: 1

Views: 49

Answers (2)

Netwave
Netwave

Reputation: 42756

As I commented before your type signature is wrong: If you check the type for [Just 1, Just 2, ...] would be like [m b] not m [].

Also, you cant simplify your function to:

meh :: (Functor m, Monad m) => [a] -> (a -> m b) -> [m b]
meh l f = fmap f l

Here you have a life example

Your substitution is wrong on this step:

x' <- f x

Since you are working inside a monad you are binding (with <-) to x' the Value inside the monad (Just in this case) so 'x'' will be 3 (4, 5, ...) not Just 3

Upvotes: 0

Igor Drozdov
Igor Drozdov

Reputation: 15045

According to the type, everything works fine

meh :: (Functor m, Monad m) => [a] -> (a -> m b) -> m [b]

If you're expecting [Just 3, Just 4, Just 5] you might need something like:

meh :: (Functor m, Monad m) => [a] -> (a -> m b) -> [m b]

Or just

meh :: (Functor m) => [a] -> (a -> m b) -> [m b]

Because you don't need the monad instance if you're not going to join values.

meh' :: (Functor m, Monad m) => [a] -> (a -> m b) -> [m b]
meh' [] _ = []
meh' (x:xs) f =
  (f x) : (meh' xs f)

Calling meh' [3,4,5] Just returns [Just 3, Just 4, Just 5]

Calling meh [3,4,5] Just returns Just [3,4,5]

Talking about a substitution (starting from the empty list):

meh [] _ = Just [], because meh [] _ = return [] returns an empty list wrapped into a monadic structure (in this case Maybe monad)

meh (5:[]) (\x -> Just x) = do
  x' <- (\x -> Just x) 5
  fmap ((:) x') (meh [] (\x -> Just x))

In this step x' <- (x -> Just x) 5 binds x' to 5. That's why meh [5] Just transforms into fmap ((:) 5) (Just []) that equals Just [5], rather than fmap ((:) (Just 5)) [] which indeed equals [Just 5]

Upvotes: 2

Related Questions