В этой небольшой статье я попытался более подробно описать механизм работы
Cont монады из Haskell'я, поскольку в отличном во всех отношениях
пособии по монадам http://www.nomaware.com/monads/html/ им уделено, к сожалению,
слишком мало внимания, хотя, на мой взгляд, среди всех остальных стандартных
монад эта одна из самых сложных для понимания. Я не претендую на глубину знания
этого механизма и не ставлю целью агитацию за использование CPS (continuation
passing style) в Haskell'e или где бы то ни было еще. Просто в указанном выше
пособии, для понимания монадных трансформаторов необходимо понимание Cont монады.
Ответа на вопрос насколько такой стиль программирования эффективен и полезен я
дать (пока) не могу.

Перед тем как перейти к обсуждению Cont монады стоит кратко ознакомиться с тем,
как CPS вычисления могут быть организованы на чистом Haskell'е без использования
монад. Для примера напишем функцию вычисления факториала в continuation passing
style.

fact n = fact_cps n id
    where fact_cps 1 cont = cont 1
          fact_cps n cont = cont (fact_cps (n-1) (\x -> x*n))

Как видим, все просто. Главная функция 'fact' вызывает CPS функцию 'fact_cps'
с параметрами 'n' и 'id', где 'id' — это функция, которая просто возвращает свой
аргумент '(id x = x)'. 'id' в данном случае является continuation'ом. 'fact_cps'
вычисляет свое значение и передает его вместе с новым continuation в continuation,
которое ей передали в параметрах. В этом простом примере никаких существенных
вычислений, правда не проводится и 'fact_cps' сразу передает управление
continuation функции.
Если обозначить функцию '(\x cont -> cont (x*n))' через 'f[n]', то 'fact_n' можно
будет представить следующим образом:

fact_n = put_1 (\a1 -> f[n] a1 (\a2 -> f a2 (\a3 -> .... (\an -> f[1] an id)...)

По сути это просто развернутая запись функции объявленной ранее. Каждая 'f[n]'
принимает в качестве параметров текущее произведение и функцию 'cont', которую
она должна вызвать для продолжения вычислений. 'put_1 cont = cont 1' — эта функция
закидывает начальное значение в цепь вычислений. В 'f[1]' передается в качестве 'cont'
функция 'id', чтобы прервать вычисления Для простоты можно расписать
это определение по отдельным функциям:

g[n] x = f[1] x id = 1*x
g[n-1] x = f[2] x g[n] = g[n] (2*x)
...
g[1] x = f[n] x g[2] = g[2] (n*x)
fact_n = put_1 g[1] = g[1] 1 = g[2] (n*1) = g[3] ((n-1)*n*1) = ... = 1*2*3..*n*1

Как видим, в каждую функцию, поддерживающую CPS приходится передавать параметр 'cont'.
Монады позволяют несколько упростить запись, спрятав этот параметр внутри монады. Это,
естественно, не единственное их преимущество, но обсуждать остальные я здесь не буду,
поскольку эту информацию можно найти в любой книге или статье по монадам.

Рассмотрим определение Cont монады и операций return и bind в Haskell.

newtype Cont r a = Cont { runCont :: ((a -> r) -> r) }
  
instance Monad (Cont r) where 
    return a       = Cont $ \k -> k a
    (Cont c) >>= f = Cont $ \k -> c (\a -> runCont (f a) k)

Символ '$' — это функция аппликации аргумента к функции. 'f $ x = f x'. Благодаря
ей мы можем опускать скобки вокруг аргументов (f (x+10) = f $ x+10).

Итак, мы объявляем новый тип 'Cont' параметризованный двумя типами — 'a' и 'r', где 'a' — это
тип для промежуточного результата, а 'r' — для финального. Как видно из определения в
контейнере 'Cont' содержится функция, единственный аргумент которой другая функция.
С помощью 'runCont' мы можем получить доступ к содержимому монады — 'runCont (Cont f) = f'.
Идейно эта 'f' представляет собой подобие функций 'f[n]' объявленных ранее. В нее передается
функция-continuation, которой она передает промежуточный результат для вычисления финального.
Ниже объявляются две вспомогательные функции, необходимые для того, чтобы тип относился к
классу монад — 'return' и '>>=' (bind). 'return' аналогична функции 'put_1', она создает монаду
'Cont' с функцией, которая просто передает свое значение в 'cont' фунцию. Сравните объявления:

put a cont = cont a -- положить a в continuation
return a = Cont (\k -> k a) = Cont (put a) -- тоже самое, только вычисления отложены
-- до момента подачи на вход continuation и заключены в тип Cont.

Функция '>>=' сложнее для понимания. Она позволяет организовать вычисления подобные тем, что
мы использовали при объявлении функции 'fact_n'. 'c' — это предыдущее continuation, в котором
сохранен предыдущий результат, ждущее на вход функции для продолжения вычислений. 'f' — это
функция, которая принимает на вход некоторый параметр, что-то вычисляет и создает новый
'Cont d' с заключенным в него промежуточным результатом. Задача '>>=' скомбинировать 'c' и 'd' так,
чтобы результат из первого перетекал во второй и создать третье 'Cont i' на основе этих двух.
Из определения '>>=' видно, что

i = \k -> c (\a -> runCont (f a) k)
runCont (f a) = runCont (Cont d) = d
i = \k -> c (\a -> d(a) k) -- d(a) - значит, что d зависит от a

Мы видим, что '>>=' отправляет в 'c' continuation функцию '(\a -> d(a) k)'. Т.е. 'с' передает свой
промежуточный результат прямо в '(f a)'. 'f' проводит вычисления на основе 'a' и возвращает 'Cont d'.
В 'd(a)' мы передаем continuation функцию 'k', которая есть параметр 'i'. Для того чтобы оборвать
цепочку вычислений мы можем, как и прежде, воспользоваться функцией 'id':

i id = c (\a -> d(a) id) = c (\a -> d(a)) = d(c(.))

Теперь мы можем записать функцию 'fact_n' в монадном стиле:

fact_n = runCont ((return 1) >>= f[n] >>= f[n-1] >>= ... >>= f[1]) id
f[n] a = Cont $ \f -> f (a*n)

Если расписать цепочку '>>=' по определению функции мы получим выражение черезвычайно
похожее на выражение для 'fact_n' в безмонадном стиле:

 (runCont (return 1)) (\a1 -> runCont (f[n] a1) (\a2 -> runCont (f[n-1] a2) ...
    ... (\an -> runCont (f[1] an) id)...)

Теперь перепишем в монадном стиле функцию 'fact':

fact n = runCont (fact_mon n) id
    where fact_mon 1 = return 1
          fact_mon n = fact_mon (n-1) >>= \a -> Cont $ \f -> f (a*n)
--                                        >>= \a -> return (a*n)

В данном случае можно создать 'Cont' функцию вручную и можно воспользоваться 'return'.
Как видим, определение функции 'fact' почти не изменилось. С одной стороны нам не нужно
больше передавать явно параметр 'cont', а с другой нужно извлекать результат из монады
и создавать 'Cont' значения. Врочем, использование монад дает нам возможность использовать
монадные трансформаторы и легко объединить 'Cont' монаду с монадами представляющими другие
вычислительные эффекты типа состояния или исключений, поэтому некоторая корявость записи
простительна.

Перейдем теперь к последней самой сложной части — пониманию принципов работы функции
'callCC'. 'callCC' определяется следующим образом:

 instance MonadCont (Cont r) where 
    callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k

С помощью этой функции мы можем организовать немедленный возврат из вычислений, как с
помощью исключений в императивных языках программирования. Параметр 'callCC' — функция 'f' —
это место, где проходят вычисления. У нее есть единственный параметр — функция 'exit'.
Если мы вызовем 'exit' внутри функции 'f' мы немедленно прервем вычисления и вернемся из
'callCC' с промежуточным результатом. Каков принцип работы 'callCC'? Обратите внимание, что
в качестве параметра в 'f' передается вполне определенная функция:

 (\a -> Cont $ \_ -> k a) = exit

Что произойдет, если мы ее вызовем внутри 'f' с параметром 'a'? 'f' вернет в качестве результата
'Cont $ \_ -> k a'. Учитывая определение 'callCC' получим

 callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k =    -- заменяем f
         = Cont $ \k -> runCont (Cont $ \_ -> k a) k =
         = Cont $ \k -> (\_ -> k a) k = Cont $ \k -> k a = return a

Т.е. вызов 'exit a' внутри 'callCC' эквивалентен вызову 'return a' вместо 'callCC'.
Если же 'exit' внутри 'callCC' вызван не будет, вычисления будут проходить как обычно.
'f' вернет некоторое 'Cont c' и общий результат будет равен:

 callCC f = Cont $ \k -> runCont (Cont с) k = Cont $ \k -> c k     -- = k(c(.))

Ставить эксперименты над 'fact' с помощью 'callCC' смысла мало, поэтому рассмотрим
следующую задачу. Пусть нам дан список некоторых значений типа 'a', функция
преобразующая эти значения в значения типа 'b' и функция проверки значения на
правильность 'f: a->Bool'. Если 'f' возвращает 'false', работа программы немедленно прерывается
и возвращается пустой список. Если все элементы списка правильные, то возвращается
список с преобразованными значениями.

 mapp list eval pred = (`runCont` id) $ callCC $ \exit -> mapp_m list
    where mapp_m [] = return []
          mapp_m (x:xs) | pred x = (mapp_m xs) >>= \a -> return ((eval x):a)
                        | otherwise = exit []
mapp [1,2,3] (\x -> x*x) (\x -> True)         -- = [1,4,9]
mapp [1,2,3] (\x -> x*x) (\x -> if (x == 2) then False else True)  -- = []

(`runCont` id) c = runCont c id. Обратите внимание, что с помощью exit мы выскакиваем
сразу из нескольких вложенных вызовов mapp_m. Если бы не callCC нам пришлось бы возвращать
состояние ошибки и каждый раз проверять его.