translating Scheme call/cc to Haskell callCC

Question

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?

Answer 1

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.

Answer 2

First of all, Scheme call/cc and Haskell callCC are somewhat different things, as explained on the page undelimited continuations are not functions

The main issue is that you may not need call/cc at all -- even in Scheme. Your example of breaking out of a loop is much better implemented using exceptions -- better from the point of view of efficiency (no need to capture the continuation which you will not be using anyway), and better conceptually. If the task is to abort the current continuations, there are tools exactly for that purpose. R7RS has recognized it and introduced exceptions. To use exceptions in Haskell, use the Error or Either monad. For example, in your code

baz :: Either [Int] [Int]
baz = foldM (\acc v -> do
        when (v >= 5) $ Left acc
        return $ v : acc) [] [0..]

thing1 = either id id baz

The operator call/cc was introduced to Scheme when there was little experience with control operators. Now we have a lot of experience, and the many serious drawbacks of call/cc have come to light. If you are interested in more details, the following page talks in great details about the problems with call/cc. An argument against call/cc