英文:
Monad and Functor law for Monad and Functor type class in Haskell
问题
I am a somewhat experienced functional programmer, but I have always been confused by the statement “A monad is just a monoid in the category of endofunctors” and the actual implementation of monads/functors in Haskell or other functional languages.
According to the Haskell Wiki,
https://wiki.haskell.org/Functor
class Functor f where
fmap :: (a -> b) -> f a -> f b
(<$) :: a -> f b -> f a
Functor Laws
Functors must preserve identity morphisms
fmap id = id
Functors preserve composition of morphisms
fmap (f . g) == fmap f . fmap g
I understand this well, so no further explanation needed; however, when we use the monad operator that is >>=
, now we have Monad implementation and Monad laws
https://wiki.haskell.org/Monad_laws
Here, I’m not questioning each implementation and rule. What I’m wondering is if we say “every Monad is an endofunctor because a monad is just a monoid in the category of endofunctors,” I expect a monad instance to satisfy the functor law, but in reality, it does not.
Or, although a monad is an endofunctor, the instance has 2 morphisms which are >>=
and fmap
. Do these two morphisms have independent laws?
I understand that the functor laws come from category theory and that a monad satisfies Monoid laws. But again, if a monad is an endofunctor, I don’t understand why it does not satisfy functor laws.
For instance,
main :: IO ()
main = do
print $ [1, 2, 3] >>= \a -> [a] // [2, 4, 6]
This code does not work if I change
print $ [1, 2, 3] >>= id // error "functor law" is not satisfied
英文:
I am a somewhat experienced functional programmer, but I have always been confused by the statement “A monad is just a monoid in the category of endofunctors” and the actual implementation of monads/functors in Haskell or other functional languages.
According to the Haskell Wiki,
https://wiki.haskell.org/Functor
class Functor f where
fmap :: (a -> b) -> f a -> f b
(<$) :: a -> f b -> f a
Functor Laws
Functors must preserve identity morphisms
fmap id = id
Functors preserve composition of morphisms
fmap (f . g) == fmap f . fmap g
I understand this well, so no further explanation needed; however, when we uses the monad operator that is >>=
, now we have Monad implementation and Monad laws
https://wiki.haskell.org/Monad_laws
Here, I’m not questioning each implementation and rule. What I’m wondering is if we say “every Monad is an endofunctor because a monad is just a monoid in the category of endofunctors”, I expect a monad instance to satisfy the functor law, but in reality, it does not.
Or, although a monad is an endofunctor, the instance has 2 morphisms which are >>=
and fmap
. Do these two morphisms have independent laws?
I understand that the functor laws come from category theory and that a monad satisfies Monoid laws. But again, if a monad is an endofunctor, I don’t understand why it does not satisfy functor laws.
For intance,
main :: IO ()
main = do
print $ [1, 2, 3] >>= \a -> [a] // [2, 4, 6]
This code does not work if I change
print $ [1, 2, 3] >>= id // error "functor law" is not satisfied
答案1
得分: 9
以下是您要翻译的内容:
首先,关于monad有两个等价的定义。第一个直接对应于“endofunctors的monoid”:
class Functor m => Monad m where
return :: a -> m a
join :: m (m a) -> m a
在这里,我们明确假设m
是一个endofunctor。Endofunctors的“tensor product”由它们的组合给出。因此,join
是从m
的“square”到m
的箭头;它定义了我们的monoid中的“乘法”。return
是从恒等endofunctor到m
的箭头;它定义了monoidal unit。有关join
和return
的三个monoidal法则分别对应于左/右单位和结合性。
在Haskell中使用的Monad
定义使用bind >>=
而不是join
。使用bind定义的monad自动成为endofunctor,其中fmap
定义如下:
liftM :: Monad m => (a -> b) -> m a -> m b
liftM f ma = ma >>= return . f
第一个定义中的(相对简单的)monoidal法则翻译成以下法则:
return a >>= k = k a
ma >>= return = ma
ma >>= (\x -> k x >>= h) = (ma >>= k) >>= h
liftM
的Functor法则可以从这些法则中推导出。例如,您可以使用以下步骤导出组合法则:
(liftM f . liftM g) ma
= liftM f (ma >>= (return . g))
= (ma >>= (return . g)) >>= return . f
= ma >>= (\x -> ((return (g x)) >>= return . f))
= ma >>= (\x -> return (f (g x)))
= liftM (f . g) ma
希望这有所帮助!
英文:
To begin with, there are two equivalent definitions of a monad. The first corresponds directly to the "monoid of endofunctors":
<pre>class Functor m => Monad m where
return :: a -> m a
join :: m (m a) -> m a</pre>
Here, we explicitly assume that m
is an endofunctor. The monoidal "tensor product" of endofunctors is given by their composition. So join
is an arrow from the "square" of m
to m
; it defines "multiplication" in our monoid. return
is an arrow from the identity endofunctor to m
; it defines monoidal unit. There are three monoidal laws in terms of join
and return
corresponding to the left/right unit and associativity.
The Monad
definition used in Haskell uses bind >>=
instead of join
. A monad defined using bind is automatically an endofunctor, with fmap
defined as:
<pre>liftM :: Monad m => (a -> b) -> m a -> m b
liftM f ma = ma >>= return . f</pre>
The (relatively simple) monoidal laws from the first definition translate into the following laws:
<pre>
return a >>= k = k a
ma >>= return = ma
ma >>= (\x -> k x >>= h) = (ma >>= k) >>= h
</pre>
Functor laws for liftM
follow from these laws. For instance, you can derive the composition law using these steps:
<pre>
(liftM f . liftM g) ma
= liftM f (ma >>= (return . g))
= (ma >>= (return . g)) >>= return . f
= ma >>= (\x -> ((return (g x)) >>= return . f))
= ma >>= (\x -> return (f (g x)))
= liftM (f . g) ma
</pre>
答案2
得分: 8
对于理论目的,通常最好忘记 >>=
,我们不需要它。这些类型类的数学风格定义如下:
class Functor f where
fmap :: (a -> b) -> f a -> f b
class Functor f => Applicative f where -- 也称为 Monoidal
pure :: a -> f a
liftA2 :: (a -> b -> c) -> f a -> f b -> f c -- †
class Applicative m => Monad m where
join :: m (m a) -> m a
(然后你可以继续定义 x>>=f = join (fmap f x)
,但这只是为了方便。)
从这个定义可以清楚地看出,讨论 [1, 2, 3] >>= id
对于确定单子是否是函子的问题是不相关的。单子是否是函子的含义就在类头中:Monad
是 Functor
的子类。因此,任何单子也都具有 fmap
可用,而这个 fmap
仍然需要满足函子法则,不管你现在是否也有那些更高级的方法可用。
†是否 liftA2
还是 <*>
更数学化存在争议。原则上,我们应该讨论具有签名 (a⊗b -> c) -> f a⊗f b -> f c
的函数,但严格来说,这只适用于_关联张量积_。Haskell 元组近似实现了这一点,但只在笨拙的 "((a,b),c)
等同于 (a,(b,c))
" 陈述下才成立。<*>
的好处是柯里化的函数在内部隐藏了这种关联性,但要付出的代价是我们需要处理_指数对象_,这使一切变得更加复杂。无论如何,我总是觉得 liftA2
比 <*>
更容易理解。
英文:
For theory purposes it's usually best to forget about >>=
, we don't need it. The maths-style definition of these type classes looks thus:
class Functor f where
fmap :: (a -> b) -> f a -> f b
class Functor f => Applicative f where -- aka Monoidal
pure :: a -> f a
liftA2 :: (a -> b -> c) -> f a -> f b -> f c -- †
class Applicative m => Monad m where
join :: m (m a) -> m a
(You could then go on to define x>>=f = join (fmap f x)
, but that's just a matter of convenience.)
From this it should be clear that any discussion of [1, 2, 3] >>= id
is pretty irrelevant for the question whether monads are functors. What it means for a monad to be a functor is right there in the class heads: Monad
is a subclass of Functor
. So any monad also has fmap
available, and this fmap
is still what needs to fulfill the functor laws, regardless of the fact that you now also have those fancier methods available.
<hr>
†<sub>It's arguable whether liftA2
or <*>
are more mathematical. In principle we should be talking about the function with the signature (a⊗b -> c) -> f a⊗f b -> f c
, but strictly speaking that only works with an associative tensor product. Haskell tuples approximate this, but only under awkward "((a,b),c)
is isomorphic to (a,(b,c))
" caveats. The nice thing about <*>
is that curried functions have this associativity hidden under the hood, but the price to pay is that we need to deal with exponential objects and it all gets yet a bit more confusing. At any rate, I always found liftA2
to be easier to understand than <*>
.</sub>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论