[Haskell-cafe] Re: Different choice operations in a continuation monad

[Heinrich Apfelmus]

Sebastian Fischer wrote:
> Heinrich Apfelmus wrote:
>
>> [...] you can implement your type as
>>
>>   newtype CMaybe a = CMaybe { forall b . (a -> [b]) -> [b] }
> 
> Yes. For me it was interesting to see how far we get by wrapping `Maybe` 
> in `Codensity`: we get more than `Maybe` but not as much as `[]`.

Well, you can implement it with  Maybe  as well, at the price of 
duplicated computations. The idea is that for the implementation of 
orElse , we're not interested in the full list of results, only in 
whether this list is empty or not. This leads to

    eval :: ProgramView Language a -> Maybe a
    eval (Return a   :>>= k) = Just a
    eval (MZero      :>>= k) = Nothing
    eval (MPlus n m  :>>= k) = (eval . view) (n >>= k)
                       `mplus` (eval . view) (m >>= k)
    eval (OrElse n m :>>= k) = case (eval . view) n of
        Nothing -> (eval . view) (m >>= k)
        Just _  -> (eval . view) (n >>= k)

Thanks to lazy evaluation, this is not too inefficient, even.


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com