I'm trying to understand how Free monads work in Haskell, and for that I've been trying to make an example work. My code was based on the answer here by Philip JF. Here is the example:
data Free f a = Pure a | Roll (f (Free f a))
--it needs to be a functor
instance Functor f => Functor (Free f) where
fmap f (Pure a) = Pure (f a)
fmap f (Roll x) = Roll (fmap (fmap f) x)
--this is the same thing as (++) basically
concatFree :: Functor f => Free f (Free f a) -> Free f a
concatFree (Pure x) = x
concatFree (Roll y) = Roll (fmap concatFree y)
data F a = One a | Two a a | Two' a a | Three Int a a a
deriving Show
-- Lift F into the Free monad
type FreeF a = Free F a
tree :: FreeF String
tree = Roll (One (Pure "A"))
example1 :: F (FreeF String)
example1 = One (Roll (One (Pure "A")))
The code above works. What I then wanted to do was to come up with a FreeF (f (FreeF a))
in order to apply the concatFree
function to it. Here is where I get into trouble.
result :: FreeF (FreeF String)
result = Roll (One (Roll (One (Pure "A"))))
The code above does not work. For me, it would seem that this construction was correct. What am I missing?
To be more precise, when I try to run this with ghci, I get the error:
FreeMonads3.hs:25:10: error:
• Couldn't match type ‘[Char]’ with ‘Free F String’
Expected type: FreeF (FreeF String)
Actual type: Free F [Char]
• In the expression: Roll (One (Roll (One (Pure "A"))))
In an equation for ‘result’:
result = Roll (One (Roll (One (Pure "A"))))
|
25 | result = Roll (One (Roll (One (Pure "A"))))
In your expression:
result :: FreeF (FreeF String)
result = Roll (One (Roll (One (Pure "A"))))
all instances of the Roll
and One
constructors operate internally within the first level FreeF
type.
As mentioned in the comments, it takes a second Pure
operator to get into the FreeF (FreeF String)
type.
Like this:
result :: FreeF (FreeF String)
result = Roll (One ( Pure (Roll (One (Pure "A")))))
Side note 1:
It is possible to avoid the heavy parenthesis nesting above by leveraging the .
function composition operator and the $
low precedence function call operators provided by Haskell.
Like this:
result1 :: FreeF (FreeF String)
result1 = Roll $ One $ Pure $ Roll $ One $ Pure "A"
or like that:
result2 :: FreeF (FreeF String)
result2 = Roll . One . Pure . Roll . One . Pure $ "A"
Note that above, the two instances of the Roll
constructor have different types. Same for the One
and Pure
constructors.
For example the type of the leftmost Pure
constructor is:
FreeF String -> FreeF (FreeF String)
Side note 2:
To have a proper free monad, you need to ensure that there is a Functor
instance for your F
type constructor. The cheapest way to ensure this is:
{-# LANGUAGE DeriveFunctor #-}
data F a = One a | Two a a | Two' a a | Three Int a a a
deriving (Show, Functor)
However, as a beginner it might be worthwhile to write the relevant code for fmap
manually, as an exercise.