Generators in JavaScript and Haskell

Generators.md

ES6. Using yield and yield*.

function* a() {
  var i = yield "first thing from a";
  var j = yield "second thing from a";
  return [i, j];
}

function* b() {
  var x = yield "something from b";
  var y = yield* a();
  return [x, y];
}

var aGen = a();
aGen.next() // "first thing from a"
aGen.next("set this to i"); // { value: "second thing from a", done: false }
aGen.next("set this to j"); // { value: ["set this to i", "set this to j"], done: true }

Delegating to another generator. The generator equivalent of calling a subroutine.

Mutation.

Here's the analogous Haskell code:

a = do
  i <- yield "first thing from a"
  j <- yield "second thing from a"
  return (i, j)

b = do
  x <- yield "something from b"
  y <- a
  return (x, y)

Interestingly, no need for yield*, although we need to lift side effects:

stdinLines = do
  line <- lift getLine
  yield line
  stdinLines

data Generator i o m r
  = Done r
  | Step (m (Generator i o r))
  | Yield o (i -> Generator i o m r)

yield :: Monad m => o -> Generator i o m o
yield o = Yield o Done

In order to get nice do syntax, we need to show that generators are a monad.

instance Monad m => Monad (Generator i o m) where
  return = Done
  Done a >>= f = f a
  Step m >>= f = Step (liftM (>>= f) m)
  Yield o k >>= f = Yield o ((>>= f) . k)

That's admittedly a bit dense, but the intuition isn't so bad. Suppose g :: Generator i o a and f :: a -> Generator i o b. We can smoosh them together to get a new generator, g >>= f, that first runs g until it finishes with an a, and then runs the generator you get from calling f on a. Inputs and outputs flow through g intil it finishes, and then they flow through f a.

Given that generators form a monad, we can give them default instances for Functor and Applicative as well:

import Control.Applicative
import Control.Monad

instance Monad m => Functor (Generator i o m) where
  fmap = liftM

instance Monad m => Applicative (Generator i o m) where
  pure = return
  (<*>) = ap

Generators are functors in a different way than you perhaps would have expected: mapping a function over a generator alters its return value (the r type parameter), not its output values (the o type parameter)! We'll see how to alter the output values in just a bit.

Applicative instance: combine two generators with a binary operation that works on their return values. Along the way towards realizing their return values, concatenate their inputs and outputs.

More about "concatenating" generators. g0 >> g1 flows through g0, ignores its return value, and then starts flowing through g1. In JavaScript, this looks something like

function* concatGens(g0, g1) {
  yield* g0();
  return yield* g1();
}

Other translations to JavaScript:

function* fmap(f, g) {
  return f(yield* g());
}

function* liftA2(f, g0, g1) {
  return f(yield* g0(), yield* g1());
}

function* bind(g0, f) {
  return yield* f(yield* g())();
}

lift :: Monad m => m a -> Generator i o m a
lift = Step . liftM Done

External iteration. Difference between JavaScript's next and the Haskell next.

next :: Monad m => Generator i o m r -> m (Either r (o, i -> Generator i o m r))
next (Done r) = return (Left r)
next (Step m) = m >>= next
next (Yield o k) = return (Right (o, k))

In JavaScript, calling next on a generator resumes its execution until it yields or returns. If the generator is suspended at a yield (which is generally the case, unless the generator hasn't started yet or it's already returned), then the argument you pass to next becomes the yield's return value within the generator.

Haskell: immutability. Calling next (modulo monad stuff) either returns whatever the generator returned, or a pair: whatever the generator yielded and a continuation of type i -> Generator i o m r. We can resume the generator with an i by feeding it to the continuation.

For example, suppose we have a fibonacci generator:

fibs = go 0 1
  where
    go i j = do
      yield i
      go j (i + j)

We can consume it externally like this:

someFibs = do
  Right (n, k) <- next fibs
  Right (n', k') <- next (k ())
  Right (n'', k'') <- next (k' ())
  ...

Way more awkward than the JavaScript version, but that's the price of immutability.

Internal iteration: each g l replaces all yields within g with l. Can you iterate internally in JavaScript? Trickiness with early returns. Recap discussion with Tom about whether for loops in JavaScript are internal or external. I was convinced they're internal (the equivalent of each in Ruby), but Tom changed my mind. Simulating internal iteration via external iteration (you can break, etc.).

each :: Monad m => Generator i o m r -> (o -> Generator i' o' m i) -> Generator i' o' m r
each (Done r) l = Done r
each (Step m) l = Step (liftM (`each` l) m)
each (Yield o k) l = l o >>= (`each` l) . k

For example, we can make analogues of fmap for incoming and outgoing values, respectively:

inMap :: Monad m => Generator i o m r -> (i' -> i) -> Generator i' o m r
inMap g f = each g $ \o -> do
  i <- yield o
  return (f i)

outMap :: Monad m => Generator i o m r -> (o -> o') -> Generator i o' m r
outMap g f = each g $ \o -> do
  yield (f o)

For example, outMap fibs show yields Fibonacci numbers, but converted to strings. It's as if we had written the following:

fibs = go 0 1
  where
    go i j = do
      yield i
      go j (i + j)

-- Replace all yields.

stringyFibs = go 0 1
  where
    go i j = do
      yield (show i)
      go j (i + j)

But what about actually, you know, running a generator with each? This is about to get a bit tacky (hacky but at the level of types).

-- import Data.Void
type Effect m r = Generator Void Void m r

runEffect :: Effect m r -> m r
runEffect (Done r) = return r
runEffect (Step m) = m >>= runEffect
runEffect (Yield o k) = absurd o -- impossible!

> runEffect $ each fibs (lift . putStrLn . show)
0
1
1
2
...

Difference between Void and forall a. a, Generator Void Void m r and forall i o. Generator i o m r. Talk about how plugging yields with each gives you generators that are polymorphic in their inputs and outputs.

A Generator Void Void m r can't possibly yield, since it would need to yield something of type Void. But Void is an uninhabited type! You can think of runEffect as like a version of next that only works on generators that never yield; this lets us use a simpler return type.