Discuss the concept of "Continuation-Passing Style" in Haskell. When is it used? — Haskell Interview Question #95

Continuation-Passing Style (CPS) is a programming paradigm where functions, instead of returning a result, take an extra argument (a continuation) that represents the code to be executed after the current function has completed. The current function then passes its return value to the continuation rather than returning it directly. CPS is used in different contexts, such as asynchronous programming, optimizations, and working with control structures that are not natively expressible within the language.

In Haskell, CPS is mainly used to achieve better control over the evaluation order, optimize tail recursion, or deal with asynchronous callbacks, among other reasons. Let’s take a look at CPS through a simple example.

Given a standard function for summing two numbers:

add :: Int -> Int -> Int
add x y = x + y

We can rewrite this function in CPS by adding an extra argument representing the continuation:

addCPS :: Int -> Int -> (Int -> r) -> r
addCPS x y k = k (x + y)

Notice how, instead of directly returning the result (‘x + y‘), we now pass it to the continuation function ‘k‘. We can nest multiple CPS functions to illustrate the idea further:

exampleCPS :: Int -> Int -> Int -> Int -> (Int -> r) -> r
exampleCPS a b c d k = addCPS a b $ abSum ->
                       addCPS c d $ cdSum ->
                       k (abSum * cdSum)

Using this function, we can compute the result like this:

exampleResult :: Int
exampleResult = exampleCPS 1 2 3 4 id

CPS is also used in conjunction with monads, particularly the ‘Cont‘ monad from the ‘mtl‘ package. ‘Cont‘ is defined as follows:

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

The essential idea behind the ‘Cont‘ monad is that it wraps a CPS function. It is an instance of the ‘Monad‘ type class, so you can use monadic combinators like ‘>>=‘, which allows for clearer composition of CPS functions.

Here’s how the ‘addCPS‘ function can be rewritten using the ‘Cont‘ monad:

import Control.Monad.Cont

addCont :: Int -> Int -> Cont r Int
addCont x y = return (x + y)

And the previously nested example can be expressed more elegantly using ‘Cont‘ and do-notation:

exampleCont :: Int -> Int -> Int -> Int -> Cont r Int
exampleCont a b c d = do
  abSum <- addCont a b
  cdSum <- addCont c d
  return (abSum * cdSum)

In summary, Continuation-Passing Style in Haskell is a powerful tool that allows for greater control over evaluation order and optimizations, as well as handling control structures and asynchronous code more effectively. It can be expressed using plain functions and lambda expressions or combined with the ‘Cont‘ monad for a more idiomatic approach.