Stream functions

[anovstrup]

DRAFT: docs and tests in progress

This PR adds a bunch of Stream functions (and a handful of Either functions that are used in the Stream function implementations). Design constraints include:

• use general signatures
• preserve result values whenever reasonable (useful for applications such as logged computations)
• emit eagerly, although I didn't adhere to this constraint consistently, in some cases because the restriction on top-level definitions prevents it (e.g., Stream.Nat.all) and in others because it seemed like a delayed result would better suit the most likely use cases (e.g., Stream.cons)

Interesting/Controversial Decisions

I had a hard time deciding whether functions that ignore the return value of a streaming computation (e.g., Stream.toList) should be parameterized by the return type of that computation (i.e., should Stream.toList : '{g, Stream a} () ->{g} [a] or : '{g, Stream a} r ->{g} [a]?). On the one hand, using () makes it explicit that the function does not distinguish among return values of the stream, but on the other hand it's less flexible for users who are forced to pass void s rather than just s for a non-unit-valued stream s. Ultimately, I decided to favor flexibility.

Issues

The pull request shows a name conflict for Stream.toList, although the patch includes a term replacement entry.

Code review

The changes summarized below are available for you to review, using the following command:

pull-request.load https://github.com/unisonweb/base:.trunk https://github.com/anovstrup/unisonweb-base:.prs._stream

New name conflicts:

 Stream.toList#fl0g3klg92 : '{e, Stream a} () ->{e} [a]
 ↓
 ┌ Stream.toList#fl0g3klg92 : '{e, Stream a} () ->{e} [a]
 └ Stream.toList#hd25q36900 : '{g, Stream a} r ->{g} [a]
   +  anovstrup.mit_2020  : License
   +  unisoncomputing2020 : License
   +  pchiusano           : Author
   +  authors.anovstrup   : Author

Updates:

 patch patch (added 1 updates)

Added definitions:

 Either.fold                      : ∀ o 𝕖 i1 i.
                                    (i1 ->{𝕖} o) -> (i ->{𝕖} o) -> Either i1 i ->{𝕖} o (+2 metadata)
 Either.left                      : Either l r -> Optional l (+2 metadata)
 Either.right                     : Either l r -> Optional r (+2 metadata)
 Either.unwrap                    : Either a a -> a (+2 metadata)
 ┌ Stream.++                      : (v1 ->{g, Stream a} v2)
                                  -> (v2 ->{g, Stream a} v3)
                                  -> v1
                                  ->{g, Stream a} v3 (+2 metadata)
 └ Stream.append                  : (v1 ->{g, Stream a} v2)
                                  -> (v2 ->{g, Stream a} v3)
                                  -> v1
                                  ->{g, Stream a} v3 (+2 metadata)
 ┌ Stream.+:                      : a -> '{Stream a} r -> '{Stream a} r (+2 metadata)
 └ Stream.cons                    : a -> '{Stream a} r -> '{Stream a} r (+2 metadata)
 Stream.Int.all                   : '{Stream Int} a (+2 metadata)
 Stream.Int.from                  : Int ->{Stream Int} a (+2 metadata)
 Stream.Int.negatives             : '{Stream Int} a (+2 metadata)
 Stream.Int.positives             : '{Stream Int} a (+2 metadata)
 Stream.Int.range                 : Int ->{Stream Int} Int ->{Stream Int} () (+2 metadata)
 Stream.Nat.all                   : '{Stream Nat} a (+2 metadata)
 ┌ Stream.Nat.from                : Nat ->{Stream Nat} a (+2 metadata)
 └ Stream.from                    : Nat ->{Stream Nat} a (+2 metadata)
 ┌ Stream.Nat.to                  : Nat ->{Stream Nat} () (+3 metadata)
 └ Stream.to                      : Nat ->{Stream Nat} () (+3 metadata)
 Stream.drop                      : Nat -> '{g, Stream a} r ->{g, Stream a} r (+2 metadata)
 Stream.drop.test                 : [Result] (+3 metadata)
 Stream.emitAndReturn             : a ->{Stream a} a (+2 metadata)
 Stream.filter                    : (a ->{g} Boolean)
                                  -> '{g, Stream a} r
                                  ->{g, Stream a} r (+2 metadata)
 Stream.filter.test               : [Result] (+3 metadata)
 Stream.flatMap                   : (a -> '{e, Stream a} r)
                                  -> '{e, Stream a} r
                                  ->{e, Stream a} r (+2 metadata)
 Stream.fold                      : (b ->{g} a ->{g} b)
                                  -> b
                                  -> '{g, Stream a} r
                                  ->{g} b (+2 metadata)
 Stream.fold.test                 : [Result] (+3 metadata)
 Stream.foldWithResult            : (b ->{g} a ->{g} b)
                                  -> b
                                  -> '{g, Stream a} r
                                  ->{g} (b, r) (+2 metadata)
 Stream.foldWithResult.handler    : (b ->{g} a ->{g} b)
                                  -> b
                                  -> Request (Stream a) r
                                  ->{g} (b, r) (+2 metadata)
 Stream.foldWithResult.test       : [Result] (+3 metadata)
 Stream.fromList                  : [a] ->{Stream a} () (+2 metadata)
 Stream.interleave                : '{Stream a} r -> '{Stream a} r ->{Stream a} r (+2 metadata)
 Stream.interleave.handler        : '{e} r
                                  -> Request (Stream a) r
                                  ->{e, Stream a} r (+2 metadata)
 Stream.map                       : (a ->{g} b)
                                  -> '{g, Stream a} r
                                  ->{g, Stream b} r (+2 metadata)
 Stream.map.test                  : [Result] (+3 metadata)
 Stream.pipe                      : '{g, Stream a} r1
                                  -> '{g, Stream b, Ask a} r2
                                  ->{g, Stream b} Either r1 r2 (+2 metadata)
 Stream.pipe'                     : '{g, Stream a} r
                                  -> '{g, Stream b, Ask a} r
                                  ->{g, Stream b} r (+2 metadata)
 Stream.pipe.handler              : '{g, Stream a} r1
                                  -> Request {Ask a, Stream b} r2
                                  ->{g, Stream b} Either r1 r2 (+2 metadata)
 Stream.scan                      : (b ->{g} a ->{g} b)
                                  -> b
                                  -> '{g, Stream a} r
                                  ->{g, Stream b} r (+2 metadata)
 Stream.take                      : Nat
                                  -> '{g, Stream a} r
                                  ->{g, Stream a} Optional r (+2 metadata)
 Stream.take.testCompletion       : [Result] (+3 metadata)
 Stream.take.testEarlyTermination : [Result] (+4 metadata)
 Stream.terminated                : '{g, Stream a} r ->{g, Stream (Optional a)} r (+2 metadata)
 Stream.terminated.test           : [Result] (+3 metadata)
 Stream.toList.test.bidirectional : [Result] (+3 metadata)
 Stream.toListWithResult          : '{g, Stream a} r ->{g} ([a], r) (+2 metadata)
 Stream.zip                       : '{Stream a} r1
                                  -> '{Stream b} r2
                                  ->{Stream (a, b)} Either r1 r2 (+2 metadata)

Name changes:

Original         Changes
 Stream.range     Stream.Nat.range (added)

[pchiusano]

@anovstrup this looks great so far, let us know when it's ready for review.

One note - we just rebooted the history of base so for your next PR be sure to delete your local trunk of base and just pull git@github.com:unisonweb/base:.trunk _base again.

@runarorama we should make sure to do a squash merge for this PR to avoid reintroducing the excessively huge history.

[runarorama]

How's this going? I'm pretty interested in getting these functions!

[anovstrup]

@runarorama I just pushed the latest, which adds some tests, corrects the implementation of take, and adds zip/interleave.

Status:

• Still need docs
• Some tests are missing
• The new zip/interleave functions need their signatures generalized

Since things have gotten busy at my day job and my night/weekend job (husband/dad), I was thinking about recruiting collaborators on the Slack hackathon channel to help push this over the finish line.

[anovstrup]

@runarorama Alternatively to my recruiting helpers on this PR, maybe you'd prefer to review this one as it stands and then add the missing stuff over time in separate PRs?

[runarorama]

I'm already using your code in some definitions, so I'm happy to review and merge what's here now.

[ceedubs]

+1 for getting these functions into base ☺️

[sullyj3]

What was the rationale for the decision to err on the side of emitting eagerly? It seems more ergonomic to me to apply transformations that both take and return a delayed stream, and then just force it once at the end.

For example, compare the following with a map that emits eagerly:

use .Stream

myStream : '{Stream Text} ()
myStream = 'let
  emit "foo"

f & g = g . f

main : '{IO} ()
main = 'let
  capitalized = '(myStream |> map (toCharList & List.map toUpper & fromCharList)) |> toList
  -- do something with capitalized  
  ()

Whereas with a map that preserves the delayedness, the line in main can instead be

capitalized = myStream |> map (toCharList & List.map toUpper & fromCharList) |> toList

[anovstrup]

@sullyj3 To the best of my recollection, I thought of it as a fairly arbitrary choice but one I wanted to be generally consistent about. Performance considerations tilted the scales in favor of eager effects — there's an overhead to suspending, and I figured users could readily suspend if they wanted to. And, of course, it's easy to implement lazy versions of the eager functions in terms of the eager ones.

[sullyj3]

Makes sense!