Zulip Chat Archive
Stream: lean4
Topic: MonadFunctor misunderstanding or bug?
Mohith (Oct 14 2024 at 02:53):
The Lean code abstraction for monad functor looks odd to me. It shows the signature of monadMap as:
monadMap {α : Type u} : ({β : Type u} → m β → m β) → n α → n α
The signature appears inconsistent with the Haskell code mentioned in the documentation. The documentation links to an MFunctor Haskell concept, and a broken link to what I believe is a MonadTransFunctor Haskell concept. Both of those sources suggest a different signature for monadMap:
monadMap {α : Type u} : ({β : Type u} → m β → n β) → m α → n α
(note the swapped occurrence of an m
and an n
)
Is this a bug in the code or a misunderstanding on my end? (I'm still learning the ropes of monadic code with functional programming, so I very well could be misunderstanding something)
Mohith (Oct 15 2024 at 23:31):
FYI, I wrote some code and proofs of what I think aligns with the original concept.
(It was a great exercise!)
import Mathlib.Control.Lawful -- Enables inferInstance : LawfulMonad (OptionT m)
/--
A function for lifting a computation from an inner `Monad` to an outer `Monad`.
Like Haskell's [`MonadTrans`], this is a functorial version of `MonadLift`.
[`MonadTrans`]: https://hackage.haskell.org/package/transformers-0.5.5.0/docs/Control-Monad-Trans-Class.html
-/
class MonadTransformer (t : (Type u → Type v) → Type u → Type w) where
mapMonad (m) [Monad m] : Monad (t m)
transform (m) [Monad m] : MonadLift m (t m)
instance [MonadTransformer t] [Monad m] : Monad (t m) := MonadTransformer.mapMonad m
@[always_inline, inline, simp]
abbrev MonadTransformer.liftOf [MonadTransformer t] (m) [Monad m] : m α → t m α :=
(transform m).monadLift
@[always_inline, inline, simp]
abbrev MonadTransformer.lift [MonadTransformer t] {m} [Monad m] : m α → t m α :=
liftOf m
instance : MonadTransformer (ReaderT ρ) where
mapMonad _ := inferInstance
transform := inferInstance
instance : MonadTransformer (ExceptT ε) where
mapMonad _ := inferInstance
transform _ := inferInstance
instance : MonadTransformer (StateT σ) where
mapMonad _ := inferInstance
transform _ := inferInstance
instance : MonadTransformer OptionT where
mapMonad _ := inferInstance
transform _ := inferInstance
/--
The `MonadTransformer` typeclass only contains the operations of a monad transformer.
`LawfulMonadTransformer` further asserts that these operations satisfy the laws of a monad transformer:
```
liftOf m (pure x) = pure x
liftOf m x >>= liftOf m ∘ f = liftOf m (x >>= f)
```
-/
class LawfulMonadTransformer (t) [MonadTransformer t] : Prop where
monad_functor [Monad m] [LawfulMonad m] : LawfulMonad (t m)
lift_pure [Monad m] [LawfulMonad m] (x : α) :
‹MonadTransformer t›.liftOf m (pure x) = pure x
lift_bind [Monad m] [LawfulMonad m] (x : m α) (f : α → m β) :
‹MonadTransformer t›.lift x >>= MonadTransformer.lift ∘ f = MonadTransformer.lift (x >>= f)
section
attribute [local simp] MonadLift.monadLift Bind.bind
instance : LawfulMonadTransformer (ReaderT ρ) where
monad_functor := inferInstance
lift_pure _ := rfl
lift_bind _ _ := rfl
instance : LawfulMonadTransformer (ExceptT ε) where
monad_functor := inferInstance
lift_pure _ := map_pure _ _
lift_bind _ _ := by
dsimp [ExceptT.lift]
rw [map_bind]
exact bind_map_left _ _ _
instance : LawfulMonadTransformer (StateT σ) where
monad_functor := inferInstance
lift_pure _ := funext fun _ => pure_bind _ _
lift_bind _ _ := by
funext
dsimp [StateT.lift, StateT.bind]
rw [bind_pure_comp, bind_map_left]
rw [bind_pure_comp, map_bind]
congr
funext
exact bind_pure_comp _ _
instance : LawfulMonadTransformer OptionT where
monad_functor := inferInstance
lift_pure _ := pure_bind _ _
lift_bind _ _ := by
dsimp [OptionT.lift, OptionT.bind, OptionT.mk]
rw [bind_pure_comp, bind_map_left]
rw [bind_pure_comp, map_bind]
congr
funext
exact bind_pure_comp _ _
end
/--
The `MonadLift` typeclass only contains the operations of a monad lift.
`LawfulMonadLift` further asserts that these operations satisfy the laws of a monad lift:
```
monadLift (pure x) = pure x
monadLift x >>= monadLift ∘ f = monadLift (x >>= f)
```
-/
class LawfulMonadLift (m : Type u → Type v) (n : Type u → Type w) [Monad m] [Monad n]
[MonadLift m n] : Prop where
lift_pure (x : α) : ‹MonadLift m n›.monadLift (pure x) = pure x
lift_bind (x : m α) (f : α → m β)
: ‹MonadLift m n›.monadLift x >>= monadLift ∘ f = monadLift (x >>= f)
namespace MonadTransformer
scoped instance [MonadTransformer t] [Monad m] : MonadLift m (t m) := MonadTransformer.transform m
scoped instance [MonadTransformer t] [Monad m] [LawfulMonad m] [LawfulMonadTransformer t]
: LawfulMonadLift m (t m) where
lift_pure := LawfulMonadTransformer.lift_pure
lift_bind := LawfulMonadTransformer.lift_bind
end MonadTransformer
Mohith (Oct 16 2024 at 02:14):
I realized a part of my misunderstanding stems from the way the documentation is currently phrased, and also from different conventions used by different authors.
- How it's being used now: A
MonadFunctor
is a morphism in the category of monads, in the sense of being a compatible functor between two objects of the category of monads. (In the documentation, the preposition "in" was used) - What I thought earlier: A
MonadFunctor
is a functor on the category of monads, in the sense of domain and codomain both being the category of Monads
IIUC, the concept of MonadFunctor
is slightly different than the concept of MonadTransformer
that I wrote above:
- The former is about changing a specific monad, perhaps independently of the data. (In the documentation, this appears to be phrased as "lift monad-transforming functions")
- The latter is about "lifting" pure computations into the effectful world, perhaps independently of the monad
I believe the referenced Haskell code intends for a joint concept called MonadTransFunctor
. Such a typeclass would probably extend MonadTransformer, and a lawful such typeclass would probably enforce that each component of the transform
is an instance of MonadFunctor (in the sense it's currently being used in the Lean codebase)
Last updated: May 02 2025 at 03:31 UTC