Zipping multiple yields into a single yield

[robertkleffner]

Howdy, fairly new to using Koka but have read most of the papers.

So, for lists we usually have a function zip : list<a> -> list<b> -> list<(a,b)>, that takes two lists and returns a single list with the elements of both input lists linked together sequentially.

For the life of me, I can't figure out how to make an equivalent function for yield. Hope I'm not missing an obvious solution! The type I'm envisioning is something like

zip-iterators : (() -> <yield<a>|e>) -> (() -> <yield<b>|e>) -> <yield<(a,b)>|e> ()

The function would be passed two closures, and those closures would be called in the body such that their yields are handled within zip-iterators, and each element a[i] is 'linked' with each element b[i] into a tuple, and the tuple yielded out for each pair. But I can't figure out how to get the semantics I want using handlers, I seem to continually end up with Cartesian join instead of zip, and I'm a little surprised I'm this stumped.

What's a good way to go about zipping iterators together in Koka, without constructing a list-like collection of the elements of each iterator first?

[anfelor]

Hi, great question! I assume you mean the yield effect from the homepage?

I believe that it is not possible to define a zip function on a fun yield effect, since a computation with this effect can not be stopped and resumed later. In this sense it is similar to a push stream: the computation will push values to you and you have to deal with them immediately.

You can however implement zip on a ctl yield effect, since the ctl allows you to capture the remaining computation. This is more similar to pull streams: you can request the computation to run until it first yields. It looks like this:

effect yield<a>
  ctl yield( x : a ) : ()

// Traverse a list and yield the elements
fun traverse( xs : list<a> ) : yield<a> () 
  match xs
    Cons(x,xx) -> { yield(x); traverse(xx) }
    Nil        -> ()

type stream<a,e>
  Stream(next : () -> e maybe<(a, stream<a,e>)>)

fun to-pull-stream(g : () -> <yield<b>|e> ()) : stream<b,e>
  Stream(fn() {
    with handler {
      return(x) Nothing
      raw ctl yield(b)
        Just((b, Stream(fn() rcontext.resume(()))))
    }
    g()
  })

fun zip-iterators(f : () -> <yield<a>|e> (), g : () -> <yield<b>|e> ()) : <div,yield<(a,b)>|e> ()
  fun go(fs : stream<a,e>, gs : stream<b,e>) : <div,yield<(a,b)>|e> ()
    match (mask<div>(fn() mask<yield>(fs.next)), mask<div>(fn() mask<yield>(gs.next)))
      (Just((a, fs)), Just((b, gs))) ->
        yield((a, b))
        go(fs, gs)
      (_, _) -> ()
  go(to-pull-stream(f), to-pull-stream(g))

fun main()
  with fun yield(i : (int,int))
    println("yielded " ++ i.fst.show ++ " " ++ i.snd.show)
  zip-iterators(fn() [1,2,3].traverse, fn() [4,5,6].traverse)

The distinction between push and pull streams and the problems with the zip function on push streams is explained in more detail in Section 3 of Stream Fusion, to Completeness.

[robertkleffner]

Not only is this answer exactly what I was looking for, you also showed how this is part of a bigger, more general concern. This topic is more complicated than I thought! I did not make the connection between Rx and yield at first. I'm pretty enthusiastic about the resource you provided at the end, will be revisiting that one for a while. Cheers!