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)
