Streaming nondeterminism ability

Each.u

ability Each where
  each : [a] -> a

Each.toStream.handler : Request {Each} a ->{Stream a} ()
Each.toStream.handler = cases
  { a } -> Stream.emit a
  { Each.each as -> resume } -> match as with
    [] -> ()
    a +: as ->
      handle resume a with Each.toStream.handler
      handle resume (Each.each as) with Each.toStream.handler

Each.toStream : '{Each, g} a ->{Stream a, g} ()
Each.toStream as = handle !as with Each.toStream.handler

Each.toList : '{Each, g} a ->{g} [a]
Each.toList as = Stream.toList '(Each.toStream as)

> Each.toList 'let
  (each [1,2,3] + 10, each [1,2,3,4])
  
---

    19 | > Each.toList 'let
           ⧩
           [ (11, 1),
             (11, 2),
             (11, 3),
             (11, 4),
             (12, 1),
             (12, 2),
             (12, 3),
             (12, 4),
             (13, 1),
             (13, 2),
             (13, 3),
             (13, 4) ]

Lazier.u

ability Each where
  each' : '{Stream a} () -> a

Stream.fromList : [a] ->{Stream a} ()
Stream.fromList = cases
  [] -> ()
  hd +: tl -> Stream.emit hd; fromList tl

Each.toStream.handler : Request {Each} a ->{Stream a} ()
Each.toStream.handler = cases
  { a } -> Stream.emit a
  { Each.each' as -> resume } -> 
    handle !as with 
      go = cases
        { _ } -> ()
        { Stream.emit hd -> tl } -> 
          handle resume hd with handler
          handle !tl with go
      go

Each.each : [a] ->{Each} a
Each.each as = each' '(fromList as)

Each.empty : '{Each} a
Each.empty = '(each' '())

Each.guard : Boolean ->{Each} ()
Each.guard b = if b then each' '(Stream.emit ()) else each' '()

Each.toStream s = handle !s with Each.toStream.handler

Each.toList s = 
  handle 
    handle !s with Each.toStream.handler 
  with 
    Stream.toList.handler

> Each.toList 'let
  (each [1,2,3] + 10, each ["Alice", "Bob", "Carol"])

> Each.toList 'let
  x = each [1,2,3,4,5,6,7]
  guard (x `mod` 2 == 0)
  (x, each ["Alice","Bob"])

---

  I found and typechecked these definitions in ~/unison/scratch.u. If you do an `add` or `update`,
  here's how your codebase would change:
  
    ⍟ These new definitions are ok to `add`:
    
      ability Each
      Each.each             : [a] ->{Each} a
      Each.empty            : '{Each} a
      Each.guard            : Boolean ->{Each} ()
      Each.toList           : '{g, Each, Stream o} o ->{g} [o]
      Each.toStream         : '{g, Each, Stream o} o ->{g, Stream o} ()
      Each.toStream.handler : Request {Each} a ->{Stream a} ()
      Stream.fromList       : [a] ->{Stream a} ()
  
  Now evaluating any watch expressions (lines starting with `>`)... Ctrl+C cancels.


    39 | > Each.toList 'let
           ⧩
           [ (11, "Alice"),
             (11, "Bob"),
             (11, "Carol"),
             (12, "Alice"),
             (12, "Bob"),
             (12, "Carol"),
             (13, "Alice"),
             (13, "Bob"),
             (13, "Carol") ]
  
    42 | > Each.toList 'let
           ⧩
           [(2, "Alice"), (2, "Bob"), (4, "Alice"), (4, "Bob"), (6, "Alice"), (6, "Bob")]

roundRobin.u

test> roundRobin.tests.ex1 = check let
  roundRobin [[1,2], [3,4], [5]] == [1,3,5,2,4]

test> roundRobin.tests.ex2 = check let
  roundRobin [[1,2], [3,4,5,6,7,8,9], [], [0]] 
   == [1,3,0,2,4,5,6,7,8,9]

List.unzip as = (List.map at1 as, List.map at2 as)

List.roundRobin : [[a]] -> [a]
List.roundRobin lists =
  go : [[a]] ->{Stream a} ()
  go = cases
    []    -> ()
    lists ->
      (hds, tls) = List.map List.uncons lists |> somes |> unzip
      Stream.fromList hds
      go tls
  Stream.toList '(go lists)

Stream.fromList : [a] ->{Stream a} ()
Stream.fromList = cases
  [] -> ()
  hd +: tl -> Stream.emit hd; fromList tl
  
Stream.roundRobin : ['{Stream a,g} ()] ->{Stream a,g} ()
Stream.roundRobin streams =
  go : ['{Stream a, g} ()] -> ['{Stream a, g} ()] ->{Stream a, g} ()
  go seen streams = match streams with 
    [] -> if List.size seen == 0 then () 
          else go [] seen
    s +: streams -> handle !s with cases
      { _ } -> go seen streams
      { Stream.emit a -> as } -> 
        emit a
        go (seen :+ as) streams

  go [] streams

> Stream.toList 'let
  go s = '(Stream.fromList s)
  Stream.roundRobin (map go [[1,2], [3,4,5,6,7,8,9], [], [0]])

In collaboration with @seagreen and @rjdellecese. This is a nondeterminism ability that produces streaming output. The Lazier.u also supports streaming the elements of each choice point.