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 return
ed, 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 yield
s 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 yield
s 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.