Comments on: The Cofree Comonad and the Expression Problem http://comonad.com/reader/2008/the-cofree-comonad-and-the-expression-problem/ types, (co)monads, substructural logic Sat, 29 Dec 2012 15:18:06 -0800 http://wordpress.org/?v=2.8.4 hourly 1 By: Richard Wallace http://comonad.com/reader/2008/the-cofree-comonad-and-the-expression-problem/comment-page-1/#comment-104596 Richard Wallace Tue, 24 Apr 2012 01:11:23 +0000 http://comonad.com/reader/2008/the-cofree-comonad-and-the-expression-problem/#comment-104596 I've really enjoyed studying and trying to understand this, but one thing has still got me hung up that I just can't seem to get past. I've been trying, as an exercise, to get the addition example from Swierstra’s paper working in terms of Free and Cofree. I translated Expr to Free successfully and am able to right an eval function eval :: (Eval f, Functor f) => Free f Int -> Int that works using cataFree. I've also taken the next step and eliminated the Eval type-class and written runArith and runVal functions that I can then compose in the way outlined in the comment above. But I just can't seem to take that mental leap to translate it using Cofree. I think my problem is in determining what the dual of Addition and Val should be. An example of that would be greatly appreciated and hopefully shine light the last bits that are still eluding me. Thanks. I’ve really enjoyed studying and trying to understand this, but one thing has still got me hung up that I just can’t seem to get past.

I’ve been trying, as an exercise, to get the addition example from Swierstra’s paper working in terms of Free and Cofree. I translated Expr to Free successfully and am able to right an eval function

eval :: (Eval f, Functor f) => Free f Int -> Int

that works using cataFree. I’ve also taken the next step and eliminated the Eval type-class and written runArith and runVal functions that I can then compose in the way outlined in the comment above.

But I just can’t seem to take that mental leap to translate it using Cofree. I think my problem is in determining what the dual of Addition and Val should be.

An example of that would be greatly appreciated and hopefully shine light the last bits that are still eluding me.

Thanks.

]]> By: fetisch spiele http://comonad.com/reader/2008/the-cofree-comonad-and-the-expression-problem/comment-page-1/#comment-60990 fetisch spiele Wed, 22 Jun 2011 17:04:40 +0000 http://comonad.com/reader/2008/the-cofree-comonad-and-the-expression-problem/#comment-60990 Its like you learn my mind! You seem to know so much about this, like you wrote the guide in it or something. I think that you just could do with some p.c. to power the message house a little bit, however instead of that, this is fantastic blog. An excellent read. I will certainly be back. Its like you learn my mind! You seem to know so much about this, like you wrote the guide in it or something. I think that you just could do with some p.c. to power the message house a little bit, however instead of that, this is fantastic blog. An excellent read. I will certainly be back.

]]> By: The Comonad.Reader » Zapping Adjunctions http://comonad.com/reader/2008/the-cofree-comonad-and-the-expression-problem/comment-page-1/#comment-1614 The Comonad.Reader » Zapping Adjunctions Thu, 05 Jun 2008 19:29:20 +0000 http://comonad.com/reader/2008/the-cofree-comonad-and-the-expression-problem/#comment-1614 [...] In an earlier post about the cofree comonad and the expression problem, I used a typeclass defining a form of duality that enables you to let two functors annihilate each other, letting one select the path whenever the other offered up multiple options. To have a shared set of conventions with the material in Zipping and Unzipping Functors, I have since remodeled that class slightly: [...] [...] In an earlier post about the cofree comonad and the expression problem, I used a typeclass defining a form of duality that enables you to let two functors annihilate each other, letting one select the path whenever the other offered up multiple options. To have a shared set of conventions with the material in Zipping and Unzipping Functors, I have since remodeled that class slightly: [...]

]]> By: The Comonad.Reader » Zipping and Unzipping Functors http://comonad.com/reader/2008/the-cofree-comonad-and-the-expression-problem/comment-page-1/#comment-1154 The Comonad.Reader » Zipping and Unzipping Functors Mon, 05 May 2008 03:01:27 +0000 http://comonad.com/reader/2008/the-cofree-comonad-and-the-expression-problem/#comment-1154 [...] Here we set aside the restriction that we only be able to Zip a comonad, and simply require that if the functor in question is a comonad, then it is a "symmetric semi-monoidal comonad", which is to say that zipping and then extracting yields the same result as extracting from each separately. You may note a lot of similarity in the above to the definition for Control.Functor.Zap the Dual functor from the other day. [...] [...] Here we set aside the restriction that we only be able to Zip a comonad, and simply require that if the functor in question is a comonad, then it is a “symmetric semi-monoidal comonad”, which is to say that zipping and then extracting yields the same result as extracting from each separately. You may note a lot of similarity in the above to the definition for Control.Functor.Zap the Dual functor from the other day. [...]

]]> By: Dave Menendez http://comonad.com/reader/2008/the-cofree-comonad-and-the-expression-problem/comment-page-1/#comment-1126 Dave Menendez Sat, 03 May 2008 07:01:15 +0000 http://comonad.com/reader/2008/the-cofree-comonad-and-the-expression-problem/#comment-1126 Here's the URI: http://okmij.org/ftp/Haskell/generics.html#PolyVariant Here’s the URI: http://okmij.org/ftp/Haskell/generics.html#PolyVariant

]]> By: Dave Menendez http://comonad.com/reader/2008/the-cofree-comonad-and-the-expression-problem/comment-page-1/#comment-1125 Dave Menendez Sat, 03 May 2008 07:00:39 +0000 http://comonad.com/reader/2008/the-cofree-comonad-and-the-expression-problem/#comment-1125 It's only two years old, but Oleg describes how to handle polymorphic variants using a record of functions in . He doesn't have the neat Dual class, though. It’s only two years old, but Oleg describes how to handle polymorphic variants using a record of functions in . He doesn’t have the neat Dual class, though.

]]> By: Edward Kmett http://comonad.com/reader/2008/the-cofree-comonad-and-the-expression-problem/comment-page-1/#comment-1102 Edward Kmett Thu, 01 May 2008 15:36:33 +0000 http://comonad.com/reader/2008/the-cofree-comonad-and-the-expression-problem/#comment-1102 Here is a quick take on the Incr/Recall example. [Edit: typechecked, added to source code, and a couple typos corrected] data Incr t = Incr Int t data Recall t = Recall (Int -> t) instance Functor Incr where fmap f (Incr i t) = Incr i (f t) instance Functor Recall where fmap f (Recall g) = Recall (f . g) (/+/) :: (Functor f, Functor g) => (f a -> a) -> (g a -> a) -> ((f :+: g) a -> a) (f /+/ g) (Inl a) = f a (f /+/ g) (Inr b) = g b newtype Mem = Mem Int type RunAlg f a = f (Mem -> (a,Mem)) -> Mem -> (a,Mem) incrRun :: RunAlg Incr a incrRun (Incr k r) (Mem i) = r (Mem (i + k)) recallRun :: RunAlg Recall a recallRun (Recall r) (Mem i) = r i (Mem i) run :: Functor f => RunAlg f a -> Free f a -> Mem -> (a, Mem) run = cataFree (,) runMyExpr :: Free (Incr :+: Recall) a -> Mem -> (a, Mem) runMyExpr = run (incrRun /+/ recallRun) Here is a quick take on the Incr/Recall example.

[Edit: typechecked, added to source code, and a couple typos corrected]

data Incr t = Incr Int t
data Recall t = Recall (Int -> t)

instance Functor Incr where
fmap f (Incr i t) = Incr i (f t)

instance Functor Recall where
fmap f (Recall g) = Recall (f . g)

(/+/) :: (Functor f, Functor g) => (f a -> a) -> (g a -> a) -> ((f :+: g) a -> a)
(f /+/ g) (Inl a) = f a
(f /+/ g) (Inr b) = g b

newtype Mem = Mem Int
type RunAlg f a = f (Mem -> (a,Mem)) -> Mem -> (a,Mem)

incrRun :: RunAlg Incr a
incrRun (Incr k r) (Mem i) = r (Mem (i + k))

recallRun :: RunAlg Recall a
recallRun (Recall r) (Mem i) = r i (Mem i)

run :: Functor f => RunAlg f a -> Free f a -> Mem -> (a, Mem)
run = cataFree (,)

runMyExpr :: Free (Incr :+: Recall) a -> Mem -> (a, Mem)
runMyExpr = run (incrRun /+/ recallRun)

]]> By: Grant B http://comonad.com/reader/2008/the-cofree-comonad-and-the-expression-problem/comment-page-1/#comment-1098 Grant B Thu, 01 May 2008 09:45:13 +0000 http://comonad.com/reader/2008/the-cofree-comonad-and-the-expression-problem/#comment-1098 I'm interested in your variant approach to the expression problem, but I have a hard time comparing yours to Swierstra's. I tried working on the translation exercise you suggested but that led me nowhere. Could you please present at least one worked example taken from the original paper? I’m interested in your variant approach to the expression problem, but I have a hard time comparing yours to Swierstra’s. I tried working on the translation exercise you suggested but that led me nowhere. Could you please present at least one worked example taken from the original paper?

]]>