[Haskell-cafe] Free monoids in Haskell
Dr. Olaf Klinke
o.klinke at dkfz-heidelberg.de
Fri Feb 27 16:43:34 UTC 2015
Dear Dan,
you posted an entry on the Comonad.Reader blog about free monoids in
Haskell. I commented about FM being a monad, and meanwhile verified that
indeed every monoid is an FM-algebra. The proofs are analogous to proving
that the continuation (_ -> r) -> r for fixed r is a monad and that r is
an algebra for it, respectively. Moreover, the FM-algebra stucture is a
monoid homomorphism w.r.t. the monoid instance you gave for (FM a).
I'd like to ask what happens when one omits the Monoid
constraint. That is, what are the elements of
newtype Y a = Y { runY :: forall b. (a -> b) -> b }
(Y a) is like (Control.ForFree.Yoneda Identity a), that is,
elements of (Y a) should be natural transformations from the reader
functor ((->) a) to the identity functor. If that is true, then the Yoneda
lemma tells us that (Y a) is isomorphic to (Identity a), but at least
operationally that seems not to be the case:
u = runY (return undefined)
has different semantics than
u' = runY (Y undefined)
as can be seen by applying both to const (). So return does not map ⊥ to
(Y ⊥). I wonder whether one can exhibit other elements not equal to any
return(x). Of course (Identity a) is actually the lifted a, since
⊥≠I dentiyt ⊥.
Yet this does not serve as an explanation for u vs. u', as both u
and u' are of the form (Y _), but one function evaluates its argument
while the other does not.
Olaf
More information about the Haskell-Cafe
mailing list