Как выразить продолжения с разделителями только для чистых функций?

Question

Я работал над учебником Олега по продолжениям с разделителями:

newtype Cont r a = Cont{runCont :: (a -> r) -> r}

instance Monad (Cont r) where
  return x = Cont (\k -> k x)
  Cont m >>= f = Cont (\k -> m (\v -> runCont (f v) k))

runC :: Cont r r -> r
runC m = runCont m id

reset :: Cont a a -> Cont r a
reset = return . runC

shift :: ((a -> r) -> Cont r r) -> Cont r a
shift f = Cont (runC . f)

liftM2 (-)
  (reset
    (liftM2 (+) (return 3)
      (shift (\k -> return (5*2))))) -- drop the continuation
        (return 1) -- 9

Поскольку продолжения в основном функции и reset/shift даже не являются частью монады API, мне интересно, как реализовать продолжения с разделителями без newtype и техника монад.

Вот что я придумала до сих пор:

reset :: Cont a a -> Cont r a -- becomes
reset :: ((a -> a) -> a) -> (a -> r) -> r
reset k f = f $ k id

shift :: ((a -> r) -> Cont r r) -> Cont r a -- becomes
shift :: ((a -> r) -> (r -> r) -> r) -> (a -> r) -> r
shift f k = f k id

Я почти уверен, что это неправильно, и если нет, я не знаю, как правильно применять операторы:

(1-) (reset ((3+) (shift (\k -> 5*2)))) -- yields

• Non type-variable argument in the constraint: Num ((a -> a) -> a)
  (Use FlexibleContexts to permit this)
• When checking the inferred type
    t1 :: forall a r.
          (Num ((a -> a) -> a), Num ((a -> r) -> r)) =>
          (a -> r) -> r

Answer 1

Продолжайте идти!

import Prelude hiding (return)

-- reset :: Cont a a -> Cont r a
reset :: ((a -> a) -> a) -> (a -> r) -> r
reset k f = f $ k id

-- shift :: ((a -> r) -> Cont r r) -> Cont r a
shift :: ((a -> r) -> (r -> r) -> r) -> (a -> r) -> r
shift f k = f k id

-- return :: a -> Cont r a
return :: a -> (a -> r) -> r
return a k = k a

-- liftM2 :: (a -> b -> c) -> Cont r a -> Cont r b -> Cont r c
liftM2 :: (a -> b -> c) -> ((a -> r) -> r) -> ((b -> r) -> r) -> (c -> r) -> r
liftM2 f ma mb k = ma $ \a -> mb $ \b -> k (f a b)

example :: Num a => (a -> r) -> r
example = liftM2 (-) (reset (liftM2 (+) (return 3) (shift (\k -> return (5*2))))) (return 1)

Одна проблема с (1-) (reset ((3+) (shift (\k -> 5*2)))) это то, что вы заменяете Cont"s return с idкогда это на самом деле flip id:

λ :t shift (\k -> 5*2)
shift (\k -> 5*2) :: Num ((r -> r) -> r) => (a -> r) -> r
λ :t shift (\k -> ($ 5*2))
shift (\k -> ($ 5*2)) :: Num r => (a -> r) -> r

Обычно, когда ghci говорит: "мы должны иметь возможность рассматривать функции как числа, чтобы этот код работал", это означает, что вы где-то допустили ошибку:)