Продолжение абстракции

Question

В общем упражнении о параллелизме на основе этого article.

Мы имеем:

-- a is the result type on which after we continue 
type Continuation a = a-> Action 

type ContinuationPseudoMonad a = Continuation a -> Action 
-- pseudoMonad because it will need Concurrent wrapper Monad: 
-- so as to define bind operation and return operation on it 

data Concurrent a = Concurrent (ContinuationPseudoMonad a) 

так Concurrent a монада мы должны реализовать с его два обязательных законов, возвращения и связываются.

К сожалению, я не нашел адекватных слов для более точного определения объекта ContinuationPseudoMonad ... и если мне не хватает слов, мне не хватает абстракции в моем сознании.

Как вы могли бы назвать это?

Есть ли какое-то слово, означающее Continuation a -> Action вместо моего неловкого смысла ContinuationPseudoMonad?

Действие существо:

data Action = Atom (IO Action) 
      | Fork Action Action 
      | Stop 

Answer 1

Очевидно Concurrent a такая же, как Cont Action a где Cont является продолжением монады. Вот простое объяснение продолжений:

1. Рассмотрим функцию f :: a -> b для некоторых произвольных типов a и b. Мы хотим преобразовать эту функцию в стиль продолжения передачи. Как мы это делаем?
2. Предположим, что у нас есть продолжение k :: b -> r, которое принимает возвращаемое значение f в качестве входа и само возвращает значение произвольного типа r. После этого мы можем конвертировать f в CPS.
3. Позвольте g :: a -> (b -> r) -> r быть функцией версии CPS от f. Обратите внимание, что он принимает дополнительный аргумент (т. Е. Продолжение k) и возвращает результат k, примененный к его выходу b.

Давайте рассмотрим практический пример, где f является функция предиката odd :: Int -> Bool:

odd :: Int -> Bool 
odd n = n `mod` 2 == 1 

Вот та же функция, написанная в продолжении прохождения стиля:

odd' :: Int -> (Bool -> r) -> r 
odd' n k = k (n `mod` 2 == 1) 

(Bool -> r) -> r часть может быть абстрагированы в качестве продолжения монады:

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

odd' :: Int -> Cont r Bool 
odd' n = return (n `mod` 2 == 1) 

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

Обратите внимание, что тип продолжения k: Bool -> r для произвольного типа r. Следовательно, продолжением k может быть любая функция, которая принимает аргумент Bool. Например:

cont :: Bool -> IO() 
cont = print 

main :: IO() 
main = odd' 21 cont 

Однако, в случае Concurrent это r не является произвольным. Он специализировался на Action. На самом деле, мы можем определить Concurrent как тип синоним Cont Action следующим образом:

type Concurrent = Cont Action 

Теперь нам не нужно реализовать экземпляр Monad для Concurrent, потому что это то же самое, как Monad например, для Cont r, как определено выше ,

runConcurrent :: Concurrent a -> ContinuationPseudoMonad a 
runConcurrent (Concurrent g) = g 

instance Monad Concurrent where 
    return a = Concurrent (\k -> k a) 
    m >>= f = Concurrent (\k -> runConcurrent m (\a -> runConcurrent (f a) k)) 

Обратите внимание, что нигде в определении instance Monad Concurrent есть мы использовали Action. Это потому, что Concurrent = Cont Action и пример монады Cont r использует r прозрачно.

Answer 2

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

data Action = Atom (IO Action) 
      | Fork Action Action 
      | Stop 

Action является типомалгебраических данных с тремя конструкторами. Это corecursive тип данных, как он определяется в терминах самого себя.

type Continuation a = a -> Action 

Continuation a является типа псевдонимом для типа функцииa -> Action. Это пример contravariant functor, так как мы могли бы определить функцию

contramap :: (a -> b) -> Continuation b -> Continuation a 
contramap aToB bToAction = aToAction 
    where aToAction = \a -> bToAction (aToB a) 

Примечание разворот - contramap принимает функцию a -> b и создает функцию Continuation b -> Continuation a.

type ContinuationPseudoMonad a = Continuation a -> Action 

ContinuationPseudoMonad a другой тип псевдонима для типа функции, но поскольку Continuation a также тип функции, ContinuationPseudoMonad a представляет собой тип функции высшего порядка, так как он принимает функцию в качестве аргумента.

ContinuationPseudoMonad a также функтор, но это ковариантный функтор, как мы могли бы определить функцию

fmap :: (a -> b) -> ContinuationPseudoMonad a -> ContinuationPseudoMonad b 
fmap aToB aToActionToAction = bToActionToAction 
    where bToActionToAction = \bToAction -> aToActionToAction (\a -> bToAction (aToB a))