Zulip Chat Archive
Stream: lean4
Topic: bind for indexed monad is "wrong"
Gary Haussmann (May 31 2022 at 19:54):
I was writing up some code for an indexed monad (m i j a) and was surprised that Lean accepted my definition of an IMonad instance for it. After some tests it seems like the type of IMonad.bind is "wrong" in that it doesn't match the type I would expect. I made an #mwe using the common "you can't open a door twice" example indexed monad:
inductive DoorState where
| DoorOpen
| DoorClosed
open DoorState
-- i is "input" state and o is the "output" state
def DoorMonad (i : DoorState) (o : DoorState) (α : Type) := α
def pureDoor {α : Type} : α → DoorMonad DoorOpen DoorOpen α := id
def bindDoor : DoorMonad i₁ i₂ α → (α → DoorMonad i₂ i₃ β) → DoorMonad i₁ i₃ β := fun m f => f m
instance : Monad (DoorMonad i o) where
pure := pureDoor
bind := bindDoor
def startOpen : DoorMonad DoorOpen DoorOpen Unit := ()
def startClosed : DoorMonad DoorClosed DoorClosed Unit := ()
def closeDoor : α → DoorMonad DoorOpen DoorClosed α := id
def openDoor : α → DoorMonad DoorClosed DoorOpen α := id
-- I would expect all these to have type "DoorMonad DoorOpen DoorClosed Unit"
#check bindDoor startOpen closeDoor -- DoorMonad DoorOpen DoorClosed Unit
#check bind startOpen closeDoor -- DoorMonad DoorOpen DoorOpen Unit
#check startOpen >>= closeDoor -- DoorMonad DoorOpen DoorOpen Unit
-- correct constructions where monad input/outputs match up
#eval bindDoor (bindDoor startClosed openDoor) closeDoor
#eval bind (bind startClosed openDoor) closeDoor
-- these should be errors due to bad type matching (can't open a door twice in a row)
#eval bindDoor (bindDoor startClosed openDoor) openDoor -- fails
#eval bind (bind startClosed openDoor) openDoor -- no error
#eval startClosed >>= openDoor >>= openDoor -- no error
I'm not sure if this is a bug or if I'm incorrectly interpreting the IMonad instance. I figured that I wouldn't be able to define bind for an indexed monad at all, since the type of bindDoor
isn't strictly the same as the type of bind
,
Reid Barton (May 31 2022 at 20:00):
Lean can unfold the definition to see that DoorMonad i o
is definitionally equal to DoorMonad i' o'
for any i
, o
, i'
, o'
, so all these variations will type check.
Reid Barton (May 31 2022 at 20:02):
If you make DoorMonad
a structure
or something then you should get the behavior you expect (the Monad (DoorMonad i o)
instance will be rejected).
Last updated: Dec 20 2023 at 11:08 UTC