Почему first-class продолжения есть только в scheme?

do
gen <- _next `fmap` iterator list () [1, 2]
gen >>= print
gen >>= print
gen >>= print

А это во что рассахаривается?

gen >>= print это i <- gen; print i; как было в требовании, обычный код IO.

list _ f () (x:xs) = f x xs

Это читерство. Задача получить такой list из стандартного map, а не написать вручную.

И работать, соответственно, должно не только на списках, а на произвольном Map (точнее на всём, для чего определено map)

1. man iterator (map : (a -> b) -> c a -> c b к ним никаким боком).

2. man eliminator (функции if', maybe, either, foldNat, list и т.п. для любого индуктивного типа, для forward iterator-ов нужна более специальная форма, но в то же время обобщённая на различие ссылок на весь контейнер и его часть, т.к. не все контейнеры рекурсивны, есть неиндуктивные массивы и т.п.).

1. Первое определено независимо от второго и работает не только для списков, а для чего угодно, как обычный forward iterator, если нужно в обратную сторону и т.п. — добавляем _prev и т.п.

2. Через второе мы получаем operator* и operator++ (begin и end сами по себе) через подобие eliminator, то есть из Elim для данного типа конструируется forward iterator — можно писать iterator array (begin arr) arr при наличии данной функции array (пара строчек типа list, только уже с использованием c и индексом для i) и т.п. Если нужно конструировать не forward / не через Elim — конструируем иначе как нужно, в твоём примере был forward, через map же никто конструировать не будет, так как оно никаким боком[2] :)

ерез map же никто конструировать не будет

Задача именно в том, чтобы сконструировать через map. Иначе проблем никаких нет, ясное дело.

То есть

r -> (v -> i -> r) -> c -> i -> r

несложно увидеть, что нам нужно для контейнера c функции с -> i -> v (operator*) и c -> i -> i (operator++), с контролем за достижением end (возвращаем первый r при end или передаём имеющие смысл *c и i + 1 во вторую функцию которая решает как из них сделать второй r с мутацией i).

Так же как в

struct container {

  // state

  struct [const_]iterator {

    // state, constainer [const]&

    value_type operator*();

    void operator++();

  };

  iterator begin() const;

  iterator end() const;

};

нам надо писать эти операции для контейнера, так или иначе, через них можно сделать map для контейнера в последовательность которую мы умеем конструировать (итераторы обобщают разбор линейных частей, конструирование дуально, но тоже может быть обобщено). Сам map для чего-либо нам тут ничего не даст — слишком специфичный и вообще рекурсивный, тогда как ты хочешь итераторы, то есть одиночные ++ на состоянии итератора как мутабельного объекта (const_iterator тоже мутабелен в этом смысле) с возможностью его передавать, копировать и т.п. Более общий fold тоже не поможет — рекурсивный. Только единичный fold можно использовать, то есть eliminator.

Наверно потому что там продолжения, а тут итераторы? Я первое не делал, только воспроизвёл использование gen через обычные мутабельные итераторы.

Сам map для чего-либо нам тут ничего не даст — слишком специфичный и вообще рекурсивный

Если у нас нормальные продолжения, то мы можем в функции-параметре map запомнить состояние в продолжении, затем вызвать продолжение, которое вернёт текущий элемент и запомнит сохранённое продолжение для следующего вызова.

То есть рантайм должен поддерживать прерывания произвольного кода с интерфейсом в виде call/cc в языке. GHC никак не умеет прерывать обычный map, а ContT это обычный CPS.

The Continuation monad represents computations in continuation-passing style (CPS). In continuation-passing style function result is not returned, but instead is passed to another function, received as a parameter (continuation). Computations are built up from sequences of nested continuations, terminated by a final continuation (often id) which produces the final result. Since continuations are functions which represent the future of a computation, manipulation of the continuation functions can achieve complex manipulations of the future of the computation, such as interrupting a computation in the middle, aborting a portion of a computation, restarting a computation, and interleaving execution of computations. The Continuation monad adapts CPS to the structure of a monad.

Before using the Continuation monad, be sure that you have a firm understanding of continuation-passing style and that continuations represent the best solution to your particular design problem. Many algorithms which require continuations in other languages do not require them in Haskell, due to Haskell's lazy semantics. Abuse of the Continuation monad can produce code that is impossible to understand and maintain.

А если и допустить поддержку прерываний прямо в IO, то остаётся вопрос сигнатур и семантики (как чистая map со списком дадут gen :: IO Int).

GHC никак не умеет прерывать обычный map, а ContT это обычный CPS.

Что и требовалось доказать. Чтобы нормально использовать CPS необходима версия стандартной библиотеки обработанная через CPS. Эдакий PreludeContT. Иначе почти ничего полезного написать нельзя.

как чистая map со списком дадут gen :: IO Int

Технически можно было бы решить как

toContT :: (ContT m) => a -> m a
toContT = return

mapContT = toContT map 

А если и допустить поддержку прерываний прямо в IO, то остаётся вопрос сигнатур и семантики (как чистая map со списком дадут gen :: IO Int).

Почему IO Int? Просто Int.

Оно в go работает, емнип, так же как в шарпах с джавами.

А как оно работает в шарпах с джавами?

замыкания аллоцируются в хипе. Ну вобщем-то оно и не совсем понятно как их аллоцировать на стеке.

У тебя там proc мутабельность использует, так что не map, а mapM_ в IO — ну вот в IO у GHC есть механизм исключений (который для чистого кода не работает), можно этот mapM_ прервать и что-то вверх возвратить, но механизма сохранения состояний с продолжениями всё равно нет, так что со стандартным mapM_ пример в принципе не реализуется — либо всё в ContT за которым CPS (как известно — более чистые функции получаются как частные случае более монадических, но не наоборот, поэтому нужны mapM в IO и вот даже mapM в ContT IO), либо механизм исключений должен быть расширен в рантайме до механизма продолжений.

gen :: Int будет всегда одним и тем же числом в хаскеле, а там он всегда разный, так что gen :: IO Int, то есть «генератор», в моём примере с итератором такой gen, например — вытаскиваются разные вещи. Ну и в IO уже есть (асинхронные) исключения, что уже ближе к честным рантайм-продолжениям (половина истории).

либо всё в ContT за которым CPS (как известно — более чистые функции получаются как частные случае более монадических, но не наоборот, поэтому нужны mapM в IO и вот даже mapM в ContT IO)

Вот-вот. Всё из IO можно переписать в ContT IO, но вручную. Даже нельзя как в Common Lisp + cl-cont просто написать import Cont — надо вручную исправлять типы (и добавлять return).

, либо механизм исключений должен быть расширен в рантайме до механизма продолжений.

Это значит реализовать полнофункциональный call/cc.

gen :: Int будет всегда одним и тем же числом в хаскеле

Продолжение же разное суем, так что не будет.

Продолжение же разное суем, так что не будет.

Haskell чистый язык. Если что-то имеет тип :: Int, то это константа (по определению из семантики языка). Если что-то при каждом запуске возвращает разное число, то тип обязан быть :: IO Int. А если «Продолжение же разное суем», то формально необходим :: ContT IO Int