Search code examples
haskellschemecontinuations

translating Scheme call/cc to Haskell callCC

Let us consider breaking out of an otherwise non-terminating fold:

(call/cc (lambda (folded)
  (stream-fold
    (lambda (acc v)
      (if (< v 5)
        (cons v acc)
        (folded acc)))
    '()
    (in-naturals 0))))
; returns '(4 3 2 1 0)

The Haskell equivalent of the above code would be

callCC $ \folded -> foldl (\acc v -> if v < 5 then v:acc else folded acc) [] [0..]

This code does not compile and complains about being unable to construct an infinite type in the expression folded acc. I already have an idea how to eliminate this kind of error in cases like the Y combinator, but the same approach does not seem to work here. What is the right approach for this kind of situation?

Solution

  • yeah; as j. abrahamson says, 

    import Control.Monad.Trans.Cont
import Control.Monad

bar :: Cont r [Int]
bar = callCC $ \folded ->
    foldM (\acc v -> do
        when (v >= 5) $ folded acc
        return $ v : acc) [] [0..]

thing = runCont bar id

    works.