This problem can be broken into two pieces, how you represent the data type and how you compose them together. Data types The styles you listed use only 2 styles of data types, the “normal” style and the continuation passing style. They differ in which objects are chosen as the primitives of the language. In … Read more
(N.B. this combines a bit from both mine and @Gabriel’s comments above.) It’s possible for every inhabitant of the Fixed point of a Functor to be infinite, i.e. let x = (Fix (Id x)) in x === (Fix (Id (Fix (Id …)))) is the only inhabitant of Fix Identity. Free differs immediately from Fix in … Read more
It’s become clear that this answer is wrong. I’m leaving it here to preserve valuable discussion in the comments until someone formulates a correct answer. Consider the power set in Set. If we have a function f : S -> T, we can form f’ : PS S -> PS T by f’ X = … Read more
As mentioned in the comments, it is frequently desirable to have some abstraction between code and database implementation. You can get much of the same abstraction as a free monad by defining a class for your DB Monad (I’ve taken a couple liberties here): class (Monad m) => MonadImageDB m where indexImage :: (ImageId, UTCTime) … Read more
Let’s just recap the definition of the Cofree datatype. data Cofree f a = a :< f (Cofree f a) That’s at least enough to diagnose the problem with the example. When you wrote 1 :< [2, 3] you made a small error that’s reported rather more subtly than is helpful. Here, f = [] … Read more
Note: that you provided yourself no direct access to the current state s in this monad. Pause s is just a free monad over the mutate and yield operations. Implemented directly you get: data Pause s a = Return a | Mutate (s -> s) (Pause s a) | Yield (Pause s a) instance Monad … Read more
Here’s an even simpler answer: A Monad is something that “computes” when monadic context is collapsed by join :: m (m a) -> m a (recalling that >>= can be defined as x >>= y = join (fmap y x)). This is how Monads carry context through a sequential chain of computations: because at each … Read more