liftM
liftM :: Monad m => (a1 -> r) -> m a1 -> m r
From the type declaration, isn't this just Functor's fmap:
fmap :: Functor f => (a -> b) -> f a -> f b
Just with the context changed to Monad, nothing else different. And for types that obey Functor laws and Monad laws, these two functions are completely equivalent, for example:
> liftM (+1) (Just 1)
Just 2
> fmap (+1) (Just 1)
Just 2
The specific implementation of liftM is as follows:
liftM :: (Monad m) => (a1 -> r) -> m a1 -> m r
liftM f m1 = do { x1 <- m1; return (f x1) }
Equivalent to:
liftM' f m = m >>= \x -> return (f x)
Note that this implementation does not rely on Functor's features; it can be completed solely based on the behaviors that Monad possesses (and if Monad laws are obeyed, it is completely equivalent to fmap, only applying the function to values with context, without doing anything extra). From this perspective, Monad is more powerful than Functor.
Having proven that Monad is more powerful than Functor, what about Applicative?
The most crucial thing for Applicative is this:
(<*>) :: Applicative f => f (a -> b) -> f a -> f b
Actually, it can also be implemented with Monad, called ap:
ap :: Monad m => m (a -> b) -> m a -> m b
Easy to accomplish:
mf `ap'` m = do
f <- mf
x <- m
return (f x)
So, Monad is also more powerful than Applicative. Furthermore, if you want to implement a custom Monad, you can first implement return and >>=, then it's easy to implement Applicative (let <*> = ap, pure = return) and Functor (let fmap = liftM).
We know there's liftA2 (up to liftA3), used to handle "multi-parameter" functions:
liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
liftA3 :: Applicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d
Actually, there are also corresponding liftM2 (up to liftM5):
liftM2 :: Monad m => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM3 :: Monad m => (a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r
For example:
> liftM2 (+) (Just 1) (Just 1)
Just 2
> liftM3 (\x y z -> x + y + z) (Just 1) (Just 2) (Just 3)
Just 6
It's easy to understand from fmap to liftM, and then to liftM5.
join
You may encounter scenarios where the value of a monadic value is still a monadic value, for example:
Just (Just 1)
So how to extract the inner monadic value? You can use the join function:
join :: Monad m => m (m a) -> m a
Let's play with it:
> join (Just (Just 1))
Just 1
> join Nothing
Nothing
> join (Just (Just (Just 1)))
Just (Just 1)
Note that the type requires the inner and outer Monad to be the same (both m), so join (Just [1]) and similar won't work properly.
From the Maybe examples above, join seems to have no practical significance. Let's look at other Monads:
> join [[1, 2], [3], [4, 5]]
[1,2,3,4,5]
> join (writer (writer (1, "a"), "b")) :: Writer String Int
WriterT (Identity (1,"ba"))
It has a bit of the meaning of join (connection). After extracting the inner monadic value, it seems some computation is also performed. Guessing it's like this:
join' mm = do
m <- mm
m
Equivalent to:
join'' mm = mm >>= (\m -> m)
-- i.e.
join'' mm = mm >>= id
So who connects the inner List? Because List's >>= implementation is List Comprehension:
xs >>= f = [y | x <- xs, y <- f x]
So in the List scenario, it's equivalent to:
joinList xss = xss >>= (\xs -> xs)
joinList' xss = [y | x <- xss, y <- id x]
The Writer scenario is similar to List; computations are all completed by >>=, and Maybe not carrying computations is also due to its >>= implementation:
(Just x) >>= k = k x
Nothing >>= _ = Nothing
The k in join is id, so it only extracts the inner Maybe value as-is.
P.S. Also, an interesting thing:
m >>= f = join (fmap f m)
That is, >>= is equivalent to mapping the monadic value (m) with a transformation function (f :: a -> m b), getting a monadic monadic value, then extracting the inner monadic value through join as the final result:
> fmap (\x -> return (x + 1)) (Just 1) :: Maybe (Maybe Int)
Just (Just 2)
> join (Just (Just 2))
> Just 2
> Just 1 >>= (\x -> return (x + 1))
Just 2
Actually, this equivalence relationship provides another way to implement >>=; just implement join. This is especially useful when implementing custom Monad instances. If you don't know how to implement >>= to obey Monad laws, you might try another angle and consider implementing join that flattens nested monadic values.
filterM
Similar to ordinary filter:
filter :: (a -> Bool) -> [a] -> [a]
filterM looks like this:
filterM :: Applicative m => (a -> m Bool) -> [a] -> m [a]
Note that the predicate function (a -> m Bool)'s Bool return value now has context. What's the use of this?
It allows adding context during the filtering process, which will be preserved in the result (m [a]). For example:
> graterThan2 = filterM (\x -> if (x > 2) then writer (True, [show x ++ " reserved"]); else writer (False, [show x ++ " discarded"])) [9, 5, 0, 2, 1, 3] :: Writer [String] [Int]
> fst . runWriter $ graterThan2
[9,5,3]
> mapM_ putStrLn (snd . runWriter $ graterThan2)
9 reserved
5 reserved
0 discarded
2 discarded
1 discarded
3 reserved
While filtering the List, it uses Writer Monad to record operation logs, especially elements that were discarded also have related information recorded (such as 0 discarded), very interesting.
There's also an even more interesting usage:
powerset :: [a] -> [[a]]
powerset = filterM (\x -> [True, False])
Defines a strange function that accepts an array and returns a 2D array. Let's play with it:
> powerset [1, 2, 3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
From its effect, it's a function that computes the power set (the set of all subsets of a set, including the empty set and itself). Consider how filterM achieves this?
The predicate function \x -> [True, False] returns multiple results simultaneously: keep and discard. This is another application of List's non-deterministic context:
[a] represents a computation with many results simultaneously (non-deterministic computation)
Non-deterministic computation can produce multiple results. Therefore, for the powerset scenario, an effective way to compute the power set is: traverse each element in the set, perform two operations (keep it and discard it), and collect the operation results.
Looking at the implementation of filterM:
filterM :: (Applicative m) => (a -> m Bool) -> [a] -> m [a]
filterM p = foldr (\ x -> liftA2 (\ flg -> if flg then (x:) else id) (p x)) (pure [])
(From Control.Monad)
foldr traverses the array, initial value is pure [], accumulator is \ x -> liftA2 (\ flg -> if flg then (x:) else id) (p x), maps the current element using liftA2, returns x: or id depending on the result of p x (if keep, insert current element into result set; if discard, result set remains unchanged).
Looks quite confusing. After completing the parameters, it's actually like this:
\ x ma -> liftA2 (\ flg a -> if flg then (x: a) else id a) (p x) ma
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b accepts a binary function, with parameter order being current element and accumulated result (corresponding to x and ma above, where ma's initial value is pure []). liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c can apply a binary function to two monadic values (分别是 p x and ma), then return a monadic value. Finally, these monadic values are folded by foldr through mappend to get the final result.
P.S. Yes, the implementation of foldr uses foldMap :: Monoid m => (a -> m) -> t a -> m, see Data.Foldable for details.
foldM
The monadic version corresponding to foldl is called foldM:
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
For example:
> foldl (\a x -> a + x) 0 [1..10]
55
P.S. A small detail: the parameter order of accumulator functions for foldl and foldr is opposite; the former is a v, the latter is v a.
If you want to add a computation context to foldl (such as a context that may fail), foldM can handle it easily:
> foldM (\a x -> if (a > 99) then Nothing; else Just (a + x)) 0 [1..10]
Just 55
> foldM (\a x -> if (a > 99) then Nothing; else Just (a + x)) 0 [1..100]
Nothing
This scenario assumes that if the sum exceeds 99, it's considered a large number overflow and computation fails.
Guess the implementation of foldM:
foldM' acc a xs = foldl (\ma v -> ma >>= (\a -> acc a v)) (return a) xs
The key point is maintaining the context of the accumulated value; remove it when participating in computation (feeding to acc), add it back during traversal. The standard (library) answer is like this:
foldM = foldlM
foldlM f z0 xs = foldr f' return xs z0
where f' x k z = f z x >>= k
Wait, what's happening with f z x >>= k?
f is the accumulator function
z0 is the initial value
xs is the Foldable instance
z is the accumulated value
x is the current element
k is? Looks like return, accepts ordinary values, returns values with context
Looking step by step, the type of f' is:
f' :: Monad m => t -> (a -> m b) -> a -> m b
And the type of foldr is:
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
The most elusive is:
(foldr f') :: (Foldable t, Monad m) => (a -> m b) -> t t1 -> a -> m b
What happened in this step?
If you only feed foldr one parameter, it requires a binary function a -> b -> b, and the second parameter and return type should be the same. So you should look at f' from a different angle:
f' :: Monad m => t -> (a -> m b) -> (a -> m b)
At this point, b is equivalent to a -> m b, corresponding to foldr:
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
-- (a -> b -> b) is filled by f', leaving b -> t a -> b, replace b with a -> m b
foldr f' :: Foldable t => (a -> m b) -> t a -> (a -> m b)
-- i.e.
(foldr f') :: (Foldable t, Monad m) => (a -> m b) -> t t1 -> a -> m b
Next, feed it 3 parameters, respectively:
return :: (a -> m b)
xs :: t t1
z0 :: a
Successfully returns m b.
P.S. The reason such clever transformations are possible is due to Haskell's default currying feature; only when parameters are filled does it return a value. So:
f' :: Monad m => t -> (a -> m b) -> a -> m b
-- Equivalent to
f' :: Monad m => t -> (a -> m b) -> (a -> m b)
It's easy to understand: f' :: Monad m => t -> (a -> m b) -> (a -> m b) accepts two parameters and returns a function of a -> m b (previously it accepted 3 parameters and returned an m b value).
Similarly, you can do this:
f :: (Num b, Monad m) => b -> (t -> t1 -> m b) -> t -> t1 -> m b
f a b c d = b c d >>= \v -> return (v + a)
The type corresponding to foldr f is:
foldr f :: (Foldable t, Num b, Monad m) => (t1 -> t2 -> m b) -> t b -> t1 -> t2 -> m b
Play with it:
> foldr f (\x y -> return (x + y)) [1..10] 0 0
55
P.S. Inspired by the standard answer, you can change the parameter order to reduce one layer of lambda:
foldM'' acc a xs = foldr (\v ma -> ma >>= acc v) (return a) xs
Composition
We know functions can be composed:
(.) :: (b -> c) -> (a -> b) -> a -> c
f . g . h is composition from right to left, for example:
> ((+1) . (/2) . (subtract 1)) 7
4.0
Monadic functions are also functions, so naturally they can be composed (actually we've seen this before).
There's something mentioned in Monad laws called Kleisli composition:
-- | Left-to-right Kleisli composition of monads.
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g = \x -> f x >>= g
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
(<=<) = flip (>=>)
<=< is the monadic version of ., with similar effects:
> Just 7 >>= (return . (+1) <=< return . (/2) <=< return . (subtract 1))
Just 4.0
Used to compose a series of Monad m => a -> m a functions, composition order is also from right to left.
No comments yet. Be the first to share your thoughts.