continuing the coding interview

Written: 2021-03-25 to 2021-03-26
by Norman Liu

Inspired by Kyle Kingsbury’s series on software magick.

You hear back from Dave a week later. It turns out that the engineering team really liked your approach to FizzBuzz. They’ve invited you back for a second round, and you’re excited to take the next steps toward gainful employment.

The day finally comes. Logging into Zoom, you take a deep breath and draw current from the atmosphere to refresh your senses. The gentle hum of your PSU fans drone gently, the sparks emanating from your fingertips. You greet Dave again. He looks a lot more alert today, as if he’s mentally prepped himself for what’s to come.

“Let’s get started, alright?” He says with a smile. You grin back, although it looks more like an evil smirk.


Two Sum!

Given an array of numbers, and a target, return whether two numbers exist in the array that add up to the target.


You blink. What the hell is an array? You ask for clarification.

“An array? It’s a sequence of items stored contiguously in memory.” he says, perplexed. A faint vision pops up in your consciousness, as your linked lists begin to transform. The primordial linkages of cons cells within their functional ether start to glow, slowly dimming and disappearing into the void. Their pointers are cleaved off, leaving bare values in their stead. The world begins to flatten, as the naked primitives twirl and shift, arranging themselves into a single line segment. As they pack themselves into an orderly axis, the space between them is replaced by unboxed values joined together in a tight arrangement, connected not by reference, but by position.

Ah, an array. Short for “arrangement of yusable things”. You wonder what the use case would be for this kind of data configuration. Maybe if RAM was expensive again?

A single word comes to your mind, and you silently whisper it to yourself.

imperative.

“Let’s get started.”, you tell Dave. “First off, arrays aren’t a real thing. Please don’t gaslight your candidates”. Secondly, it seems like we’ll need a way to iterate through a collection of numbers.”

You know that dependencies are going out of style, and you want to show Dave that you care about code bloat as much as the next developer. It’s clear that this is a problem that needs to be solved from the ground-up.

“Sequential evaluation of instructions doesn’t make sense in an actual programming language, so we’ll need a way to simulate that abstractl-”, you say excitedly. Dave turns his head, expect you to continue. More specifically, he’s waiting for you to give him a continuation.

{-# LANGUAGE InstanceSigs #-}
newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r} 

lift :: Monad m => m a -> ContT r m a
lift ma = ContT (ma >>=)

“The r stands for result!”, you interject before he asks.

instance Functor (ContT r m) where
    -- (a -> b) -> ((a -> m r) -> m r) -> ((b -> m r) -> m r)
    fmap :: (a -> b) -> ContT r m a -> ContT r m b
    fmap f cont = ContT (\bmr -> runContT cont $ bmr . f)

instance Applicative m => Applicative (ContT r m) where
    pure :: a -> ContT r m a
    pure x = ContT ($ x)

    -- ((a -> b -> m r) -> m r) 
    -- -> ((a -> m r) -> m r) 
    -- -> ((b -> m r) -> m r)
    (<*>) :: ContT r m (a -> b) -> ContT r m a -> ContT r m b
    contAB <*> contA = ContT 
        $ \b -> runContT contAB 
            $ \ab -> runContT contA (b . ab)

instance Monad m => Monad (ContT r m) where
    return = pure

    -- ((a -> m r) -> m r)
    -- -> (a -> ((b -> m r) -> m r))
    -- -> ((b -> m r) -> m r)
    (>>=) :: ContT r m a -> (a -> ContT r m b) -> ContT r m b
    contA >>= f = ContT
        $ \bmr -> runContT contA
            $ \a -> runContT (f a) bmr

You stop typing for a moment and turn your head toward your other monitor. “The only way we can guarantee sequential evaluation is by using monads. Now - Haskell is a black box, and we’re operating in a strange non-category called Hask.” Dave sighs.

“Things could crash or infinitely loop at any time, so we need to be careful about what we try to compute. We need our statements to execute in order, and the only way to do that is generate that ordering explicitly through callbacks. At the same time, callback hell is a real place, so we need a way to stay pure and veer as far away from it as possible.” He laughs for a moment because he thinks you’re joking.

Some of your ancestors are still wallowing in those sulfur pits. Not cool, Dave.

You brush off his slight, and get back to work. The first inklings of your time machine are finished. You close your eyes for a moment, and visualize the spell you’re about to cast. Morphisms and points, previously twirling through an abstract cosmos, suddenly begin to entangle with each other, their arrows tightly bound together by iridescent strands of composition. Dave doesn’t know about the Cont monad, the mother of all monads (she’s your aunt!), the omnipresent abstraction that unifies effects themselves.

The foundations are in place, and you inscribe the last incantations into bytes. You have a few parentheses left over from last month, so you decide to splurge a little bit.

callCC :: ((a -> ContT r m b) -> ContT r m a) -> ContT r m a
callCC f = ContT
    (\amr -> runContT
        (f (\a -> ContT
            (\_ -> amr a)))
        amr)

Dave is definitely more oriented towards objects, and he seems pretty lost. That’s alright - you felt lost too, back when you were figuring out the secrets of time travel. You stop to explain what callCC really means.

callCC works the same way that call-with-current-continuation does in Scheme. The only difference is that we’re not doing any explicit manipulation of the call stack. All we’ve done is reify our continuations as data, so we can play around with them. Let’s go over these types:

callCC :: 

-- a function that takes a function (a -> ContT r m b)
( (a -> ContT r m b) 
-- where b is an arbitrary type
-- and returns another continuation object, of type a
        -> ContT r m a)

-- finally returning that different object in the end
-> ContT r m a

Let’s ignore the m argument and expand out some types:

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

callCC' :: ((a -> Cont r b) -> Cont r a) -> Cont r a
callCC' f = Cont 
    (\ar -> runCont 
        (f (\a -> Cont
            (\_ -> ar a)))
        (ar))

-- all the types:
runCont :: Cont r a -> (a -> r) -> r

f :: (a -> Cont r b) -> Cont r a 
f :: (a -> ((b -> r) -> r)) -> ((a -> r) -> r)

ar :: (a -> r)
a :: a
(ar a) :: r

Where does the b come from??? It’s shadowed and completely ignored, so why is it there?

At its core, all a Cont actually does is function application.

someA :: a

someCont :: Cont r a
someCont = Cont (\ar -> ar someA)

ar :: a -> r

arr :: (a -> r) -> r
arr = runCont someCont

r :: r
r = arr ar
r = ((\(Cont arToR) -> arToR) someCont) ar

When we’re in the Cont monad, we’re explicitly manipulating control flow by dynamically choosing which continuations get called. Values in the rightmost position of the Cont r a signature just represent a value stored in the container, that can only be accessed by passing another continuation to be applied to it. You can get out of the Cont monad by passing id at the end, or by using the Identity monad for ContT.

This gives us the ability to exit early from our do-blocks, since the monadic context we’re abstracting over is what exactly to do after a function returns. We can just ignore the continuation, which will do exactly that - skip the remainder of the computation.

quitT :: r -> ContT r m b
quitT = ContT (\f -> pure x)

launchMissiles :: Monad m => [String] -> m String
launchMissiles = pure . ("Firing at: " <>) 
                    . intercalate ", " 

doomsday :: ContT Bool IO Bool 
doomsday = do
    liftIO $ putStrLn "Ready to fire the missiles?"
    resp <- liftIO getLine
    unless (resp == "nuke me plz OwO") $ quitT False
    launchMissiles ["Canada", "USA", "Russia"]
    pure True

It’s clear that the b in callCC can be anything then, since we’re ignoring it. It’s confusing, I know. We’re like 3 levels of higher-order functions deep.

An example of how callCC might be used in practice:

haltingProblemSolver :: Cont r String
haltingProblemSolver = do
    z <- pure 100
    halted <- callCC $ \halt -> forever $ do
        when (z == 100) $ halt False
        pure True
    pure $ "Turing was " 
         <> if halted then "WRONG" else "right, I guess"

In this case, the function \halt -> Cont ... is the first argument of callCC, of type ((a -> Cont r b) -> Cont r a). halt is just a named argument, that itself is a continuation that will exit the block we’re in. The key is that we’re in a nested block, isolated from the outer do-block. We’re just calling quitT from the lambda, so we end up jumping back to the call site of callCC.

Let’s go back to the definition of callCC:

callCC f = Cont
    (\ar -> runCont
        (f (\a -> Cont
            (\_ -> ar a)))
        ar)

-- ar is the continuation that follows the callCC invocation
-- halt is the argument passed to f
-- False is the argument passed to halt

halted <- callCC 
    |-------------f------------|
  $ \halt -> forever $ do  |-a-|
    when (z == 100) $ halt False
    pure True

Since we’re looping forever, the only way we can “exit” this block is by calling halt with an argument. “Exit” is in quotes because we’re not really exiting - we’re just tail-calling another function that will never return to where we were, but that’s just semantics. Whatever the halt function is called with, will end up being the return value of callCC in this case. If you’re in a block that DOES terminate, then either the argument to haltor the last value in the chain will be the return value, in which case they need to be the same type.

This is powerful because we’re working in nested monad closures, so we can still capture the surrounding computation using scoping. We’ve essentially designed a structured GOTO, which is universally considered to be harmless.

Dave’s eyes look glassed over. You decide it’s about time to hammer out a solution before your lecture brings him over retirement age.

It’s time to go imperative.

import Control.Monad
import Data.IORef
import System.IO.Unsafe (unsafePerformIO)
import qualified Data.IntSet as S
type Imperative = ContT Int IO

hashSet :: b -> S.IntSet
hashSet = const S.empty

var :: a -> Imperative (IORef a)
var = liftIO . newIORef

peek :: IORef a -> Imperative a
peek = liftIO . readIORef

poke :: (IORef a, a -> a) -> Imperative ()
poke (r, f) = liftIO $ modifyIORef' r f

get :: (Int, IORef S.IntSet) -> Imperative Bool
get (a, r) = S.member a <$> peek r 

add :: (Int, IORef S.IntSet) -> Imperative ()
add (a, r) = poke(r, S.insert a)

(=:) :: IORef a -> a -> Imperative ()
r =: x = poke(r, const x)

for :: (Foldable t, Monad m) 
    => t a 
    -> ((a, ContT r m b, ContT r m c) -> ContT r m ()) 
    -> ContT r m ()
for xs f = callCC 
    $ \break -> forM_ xs 
        $ \i -> callCC 
            $ \continue -> f (i, continue(), break())

new :: a -> a
new = id

begin :: ContT r IO r -> r
begin c = unsafePerformIO $ runContT c pure

if_ :: Monad m => m Bool -> m () -> m ()
if_ p b = do
    px <- p
    when px b

You stop for a second to see if Dave is still with you. His expression is a combination of intrigue at what you’re doing, annoyance at how you’re doing it, and curiosity at why you’re like this. You didn’t really overengineer this time, did you?

“DSL’s are a great way to create maintainable interfaces for niche problems, and they’re one of the biggest strengths of functional languages”, you say. He doesn’t seem convinced.

You take a deep breath, closing your eyes, and visualize the bastardized, Kafkaesque universe you’ve molded. The morphisms of infinitely composable points collapse into a single path, a solitary walkway through endless non-deterministic traversals. You step confidently through the void, your footsteps lighting up the ground with faint flashes of light as universal constants start to change. Recursion is replaced by hard loops. Data starts to become mutable and mushy. Stone bricks of concrete categories arrange themselves into brutalist skyscrapers, and a tie materializes around your neck. Looks like it’s time to get to business.

“Take a look - I’m just about ready to solve the problem.”

twoSum :: ([Int], Int) -> IO Bool
twoSum(nums, target) = begin $ do 

    seen <- var(new hashSet());
    exists <- var(False);

    for (nums) $ \(i, continue, break) -> do
        st <- peek(seen);
        if_ ( get(target - i, seen) ) $ do
            exists =: True;
            break;
        add(i, seen);

    res <- peek(exists);
    return res;

Dave thanks you for your time, and answers a few lingering questions you had about retirement fund contributions and PTO. He lets out a final sigh, as the universe in your mind’s eye begins to decompose back into the freely decoupled ether you’re familiar with. The blood stops leaking out of your walls. You take a deep sip of coffee, thanking him for his time.

You didn’t get the job.