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

If you wanted a double nesting of `FreeF` wouldn't you need 2 `Pure` in your stack? As it is your function quite obviously (to me) is only a `FreeF String` which is just another name for the type the compiler expects `Free F [Char]` or put differently nesting in`Roll` doesn't add layers of `Free` only `Pure` does that. — cafce25, Aug 10 '23 at 10:28
To obtain a `FreeF (FreeF String)`, you need to start from `Pure x` where `x :: FreeF String`. You only have one `Pure` and that wraps a `String`. You need at least one other `Pure`. — n. m. could be an AI, Aug 10 '23 at 10:28
Sorry, I'm not very proficient in Haskell. Can you give an actual example? — Davi Barreira, Aug 10 '23 at 13:03
As mentioned by n.m, you need to insert yet one more `Pure` constructor to raise your expression to the 2nd level of `Free F`. Note that in that case the expression includes 2 versions of Pure, Roll,... of different types. Like this: `result = Roll (One ( **Pure** (Roll (One (Pure "A")))))` — jpmarinier, Aug 10 '23 at 15:42
Also please note that you can avoid heavy parenthesis nesting by using '$' as the low precedence function call operator. Like this: `result = Roll $ One $ Pure $ Roll $ One $ Pure "A"` — jpmarinier, Aug 10 '23 at 15:47

jpmarinier · Accepted Answer · 2023-08-11T10:27:24.377

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.

score 1 · Answer 2 · answered Aug 11 '23 at 05:24

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

Why this free monad example is failing?

2 Answers2