Как я могу использовать Reader, используя свободные монады?

Question

Итак, я понял, как реализовать Reader (и ReaderT, не показан) с помощью operational пакета:

{-# LANGUAGE GADTs, ScopedTypeVariables #-} 

import Control.Monad.Operational 

data ReaderI r a where 
    Ask :: ReaderI r r 

type Reader r a = Program (ReaderI r) a 

ask :: Reader r r 
ask = singleton Ask 

runReader :: forall r a. Reader r a -> r -> a 
runReader = interpretWithMonad evalI 
    where evalI :: forall b. ReaderI r b -> (r -> b) 
      evalI Ask = id 

Но я не могу понять, для моей жизни, как сделать это с помощью свободных монад (Я использую пакет Эдварда Кеммета free). Ближайший я получил это, что я понимаю, это обман (что-то о том, как ((->) r) уже монада):

import Control.Monad.Free 

type Reader r a = Free ((->) r) a 

ask :: Reader r r 
ask = Free Pure 

runReader :: Reader r a -> r -> a 
runReader (Pure a) _ = a 
runReader (Free k) r = runReader (k r) r 

-- Or, more simply and tellingly: 
-- 
-- > runReader = retract 

Даже если это не так глуп, как я подозреваю, что это, это не то, что я хочу, потому что я хочу, в основном, иметь возможность проверить Reader как данные ...

Answer 1

Я не думаю, что это можно сделать, за исключением того, что у вас есть. Но я не думаю, что это уникально для читателя. Рассмотрим свободную версию монады писателя

data WriterF m a = WriterF m a deriving (Functor) 

type Writer m = Free (WriterF m) 

очевидно, WriterF изоморфно писателю, но это действительно ведет себя так, как можно было бы ожидать с простой алгебры

algebraWriter :: Monoid m => WriterF m (m,a) -> (m,a) 
algebraWriter (WriterF m1 (m2,a)) = (m1 <> m2,a) 

таким образом

runWriter :: Monoid m => Writer m a -> (m,a) 
runWriter (Pure a) = (mempty,a) 
runWriter (Free x) = algebraWriter . fmap runWriter $ x 

Аналогичным образом, я думаю о бесплатном читателе как

type ReaderF r = (->) r 

type Reader r = Free (ReaderF r) 

Мне это нравится, потому что добавление их дает состояние монаде

type State x = Free ((ReaderF x) :+: (WriterF x)) 

runState :: State x a -> x -> (a,x) 
runState (Pure a) x     = (a,x) 
runState (Free (Inl f)) x    = runState (f x) x 
runState (Free (Inr (WriterF x f))) _ = runState f x 

Обратите внимание, что ваше операционное решение может быть сделано для работы с Free с помощью «свободного функтора», как может что-нибудь, что работает с операционным

data FreeFunctor f x = forall a. FreeFunctor (f a) (a -> x) 

но, что FreeFunctor ReaderI также изоморфна (->).

Answer 2

Ну, я смотрел на это уже 3 часа, и я думаю, что нашел что-то, что мне больше нравится. Поскольку Reader аппликативна является таким же, как Reader монады, мы можем попробовать аппликативную версию operational:

{-# LANGUAGE RankNTypes, GADTs, FlexibleInstances #-} 

import Control.Applicative 

data ProgramA instr a where 
    Pure :: a -> ProgramA r a 
    Ap :: ProgramA r (a -> b) -> ProgramA r a -> ProgramA r b 
    Instr :: instr a -> ProgramA instr a 

infixl `Ap` 

instance Functor (ProgramA instr) where 
    fmap f (Pure a) = Pure (f a) 
    fmap f (ff `Ap` fa) = ((f .) <$> ff) `Ap` fa 
    fmap f instr = Pure f `Ap` instr 

instance Applicative (ProgramA instr) where 
    pure = Pure 
    (<*>) = Ap 

interpretA :: Applicative f => 
       (forall a. instr a -> f a) 
      -> ProgramA instr a 
      -> f a 
interpretA evalI (Pure a) = pure a 
interpretA evalI (ff `Ap` fa) = interpretA evalI ff <*> interpretA evalI fa 
interpretA evalI (Instr i) = evalI i 

data ReaderI r a where 
    Ask :: ReaderI r r 

type Reader r a = ProgramA (ReaderI r) a 

ask :: Reader r r 
ask = Instr Ask 

runReader :: Reader r a -> r -> a 
runReader = interpretA (\Ask -> id) 

instance Monad (ProgramA (ReaderI r)) where 
    return = pure 
    ma >>= f = runReader <$> fmap f ma <*> ask 

Структура ProgramA (ReaderI r) a) может быть осмотрена более прямолинейна, чем любой Program (ReaderI r) a или Free ((->) r) a.