Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Can the continuation monad transformer be given an Alternative instance with some and many?

We can define the continuation monad transformer as

data Cont r m a = Cont {run :: (a -> m r) -> m r}

We can give Cont r m an Alternative instance if m is a member of Alternative via

empty = Cont $ \f -> empty
ca <|> cb = Cont $ \f -> run ca f <|> run cb f

And then allow some and many to take on their default methods. My question is, can we define some and many in terms of m's some and many, instead of the default definitions? The apparently obvious options

some ca = Cont $ \f -> some $ run ca f
many ca = Cont $ \f -> many $ run ca f

obviously do not work (they do not even type check). Is there some other way to use them (if we need m to also be a monad, that's fine)?

For reference, some and many must be the least solution to the equations:

  • some v = (:) <$> v <*> many v
  • many v = some v <|> pure []

Assuming that some :: m a -> m [a] and many :: m a -> [a] satisfy this law, so should some :: Cont r m a -> Cont r m [a] and many :: Cont r m a -> Cont r m [a].

like image 254
PyRulez Avatar asked Nov 28 '17 05:11

PyRulez


People also ask

Is every Monad Transformer a Monad?

All monad transformers are instances of MonadTrans , and so lift is available for them all. There is a variant of lift specific to IO operations, called liftIO , which is the single method of the MonadIO class in Control. Monad. IO.

What is continuation Monad?

The Continuation monad represents computations in continuation-passing style (CPS). In continuation-passing style function result is not returned, but instead is passed to another function, received as a parameter (continuation).


1 Answers

No.

There exists no arrow from

(forall a. f a -> f [a]) ->
(forall r. ((a -> f r) -> f r)) -> (([a] -> f r) -> f r)`

that makes use of its argument in an interesting way.

The only place forall a. f a -> f [a] can be applied is to an f r. These are the results of (a -> f r) -> f r, like in your "obvious options", and ([a] -> f r). This leaves a result of the type f [r]. The only thing that can be done with a forall r. Alternative f => f [r] to produce an f r is index the f [r] with some partial function forall r. [r] -> r from a natural number to some other no-larger natural number.

like image 57
Cirdec Avatar answered Sep 20 '22 15:09

Cirdec