Why this free monad example is failing?

Question

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"))))

Answer 1

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.

Answer 2

The type of result as you defined it is actually:

result :: FreeF String
result = Roll (One (Roll (One (Pure "A"))))

That's because the type of Roll (specialized to FreeF) is F (FreeF a) -> FreeF a.

To get the desired type, use Pure instead of Roll. Pure has type a -> FreeF a

result :: FreeF (FreeF String)
result = Pure (One (Roll (One (Pure "A"))))