jaror, I finally found a decent definition of free alternatives:
newtype Free f a = Free { alts :: [Free' f a] } deriving Functor instance Applicative (Free f) where pure = Free . pure . Pure Free ps <*> q0 = asum $ map (`apL` q0) ps where apL (Pure f) q = f <$> q apL (Free' x p) q = Free $ pure $ Free' x $ flip <$> p <*> q instance Alternative (Free f) where empty = Free empty Free ps <|> Free qs = Free (ps <|> qs) data Free' f a = Pure a | forall x. Free' (f x) (Free f (x -> a)) deriving instance Functor (Free' f)