CODEWITHSUNDEEP
haskellapplicativefree-monad
Marko Grdinić
Marko Grdinić

Reputation: 4062

Why can't the compiler deduce the Functor type in the Free Applicative examples?

module Main where

data Toy b next =
    Output b next
  | Bell next
  | Done

data FixE f e = Fix (f (FixE f e)) | Throw e

-- The working monadic function
catch :: (Functor f) => FixE f e1 -> (e1 -> FixE f e2) -> FixE f e2
catch (Fix x) f = Fix (fmap (`catch` f) x)
catch (Throw e) f = f e

-- Type error
applicate_fixe :: (Functor f) => FixE f (e1 -> e2) -> FixE f e1 -> FixE f e2
applicate_fixe a b = a `catch` (`fmap` b)

-- Type error
applicate_fixe' :: (Functor f) => FixE f (e1 -> e2) -> FixE f e1 -> FixE f e2
applicate_fixe' (Throw f) b = fmap f b
applicate_fixe' (Fix f) b = Fix (fmap (`applicate_fixe` b) f)

main :: IO()
main = print "Hello."

C:\!Various_Exercises\Haskell_Exercises\Free_Monad_Stuff\test.hs: 15, 33
Could not deduce (Functor (FixE f)) arising from a use of `fmap'
from the context (Functor f)
  bound by the type signature for
             applicate_fixe :: Functor f =>
                               FixE f (e1 -> e2) -> FixE f e1 -> FixE f e2
  at test.hs:14:19-76
In the second argument of `catch', namely `(`fmap` b)'
In the expression: a `catch` (`fmap` b)
In an equation for `applicate_fixe':
    applicate_fixe a b = a `catch` (`fmap` b)
C:\!Various_Exercises\Haskell_Exercises\Free_Monad_Stuff\test.hs: 18, 31
Could not deduce (Functor (FixE f)) arising from a use of `fmap'
from the context (Functor f)
  bound by the type signature for
             applicate_fixe' :: Functor f =>
                                FixE f (e1 -> e2) -> FixE f e1 -> FixE f e2
  at test.hs:17:20-77
In the expression: fmap f b
In an equation for applicate_fixe':
    applicate_fixe' (Throw f) b = fmap f b

I am going off this tutorial trying to figure out the Free Monad and as an exercise I am trying to do the Applicative function as well. To be honest, I am not sure what those errors are supposed to mean.

Also I am not sure what the type signature for the data FixE f e = Fix (f (FixE f e)) | Throw e is supposed to be exactly. At first I thought f (FixE f e) is supposed to be a tuple, but it does seem like it is one argument, therefore the (FixE f e) part is actually a type argument to the first f. But if that is the case shouldn't the f inside FixE f e also require a type argument as well?

Edit:

applicate_fixe :: (Functor f) => FixE f (e1 -> e2) -> FixE f e1 -> FixE f e2
applicate_fixe (Fix f) b = Fix (fmap (`applicate_fixe` b) f) -- Works as the f argument in fmap is a functor
applicate_fixe (Throw f) (Fix b) = fmap f b -- The b is of type f (FixE f e1) so it is clearly a functor and yet the type system rejects it.

Before anything, I do not understand this last part. Also what exactly should have an instance of functor defined? f should already has that constraint in the above definition.

Edit2: Maybe you means that FixE should have a Functor instance.

instance Functor f => Functor (FixE f) where
  fmap f (Fix x) = fmap f x -- Type error
  fmap f (Throw e) = Throw (f e)

Here is my best shot, but it complains that the type f is too rigid in the first line.

Upvotes: 0

Views: 264

Answers (1)

Marko Grdinić
Marko Grdinić

Reputation: 4062

module Main where

data Toy b next =
    Output b next
  | Bell next
  | Done

instance Functor f => Functor (FixE f) where
  fmap f (Fix x) = Fix (fmap (fmap f) x)
  fmap f (Throw e) = Throw (f e)

data FixE f e = Fix (f (FixE f e)) | Throw e

-- Monadic function
catch :: (Functor f) => FixE f e1 -> (e1 -> FixE f e2) -> FixE f e2
catch (Fix x) f = Fix (fmap (`catch` f) x)
catch (Throw e) f = f e

-- Applicative function
applicativeFixE :: (Functor f) => FixE f (e1 -> e2) -> FixE f e1 -> FixE f e2
applicativeFixE (Fix f) b = Fix (fmap (`applicativeFixE` b) f)
applicativeFixE (Throw f) b = fmap f b

main :: IO()
main = print "Hello."

Based on the comments I managed to implement the applicative function. I am not completely sure why the above works yet versus some of the alternative I've tried, but it type checks.

Thanks everyone.

Upvotes: 1

Related Questions