Stream processing library for Unison

[pchiusano]

Effectful streams are a ubiquitous abstraction that will get used by lots of Unison programs. We want a nice, lightweight, efficient stream type that's well-integrated into Unison. Here's the Unison API:

data Stream f a

instance MonadPlus (Stream f) -- Unison does not have typeclasses but you get the idea

eval :: f a -> Stream f a

uncons :: Stream f a -> Stream f (Maybe (a, Stream f a)) 

run :: Stream Remote! a -> Remote (Vector a)

fromVector :: Vector a -> Stream f a

It is expected that <|> (which is Stream append) and >>= (which is the same idea as the list monad) take constant time, rather than needing to traverse the left-hand expression.

I expect that Stream Remote a values will be very common - it's a stream that might pull data from multiple Unison nodes.

The implementation will be based on type-aligned sequences, following FS2:

data Stream f a = Stream (forall b . Stack f a b -> Stack f a b)

data Stack f a b where
  Empty :: Stack f a a
  ConsBind :: (a -> Stream f b) -> Stack f b c -> Stack f a c 
  ConsEmit :: a -> Stack f a b -> Stack f a b
  ConsEval :: f a -> Stack f a b -> Stack f a b
  ConsAppend :: Stream f a -> Stack f a b -> Stack f a b

-- left as an exercise: implement `MonadPlus`, `eval`, `uncons`, and `run`

But we will have to defunctionalize this representation, so the functions are not Haskell functions but Unison functions, similar to what was done for Unison.Remote.

Subtasks:

• As an exercise to check for understanding, implement pure Haskell version of Stream as given above. Post a compiling gist for reference.
• Add defunctionalized version of Stream to Unison.Stream (open question - should we just add these as another constructor to Unison.Term, like we did for Remote? Or possibly bite the bullet and split out a separate Value type for representing runtime values, and add it there.)
• Integrate into Unison builtins so these functions can be used from Unison

[pchiusano]

@refried this was trickier than I thought. :) I got a compiling, working version after about 2 hours. Probably should have done that sooner rather than sending you on a wild goose chase. My bad. :( I hope this was still a good learning exercise.

I fiddled a bit with different representations and found it was pretty easy to express with the following:

{-# Language ScopedTypeVariables #-}
{-# Language BangPatterns #-}
{-# Language ExistentialQuantification #-}
{-# Language Rank2Types #-}
{-# Language GADTs #-}

module Stream where

import Control.Applicative
import Control.Monad

data Stream f a = forall a0 . Stream (forall b . Stack f a b -> Stack f a0 b)

data Stack f a b where
  Empty :: Stack f a a
  Cons :: [Segment f a] -> Stack f a b -> Stack f a b
  Bind :: (a -> Stream f b) -> Stack f b c -> Stack f a c

data Segment f a where
  Emit :: a -> Segment f a
  Eval :: f a -> Segment f a
  Append :: Stream f a -> Segment f a

data ViewL f a b where
  Unbound :: [Segment f a] -> ViewL f a a
  Bound :: [Segment f a] -> (a -> Stream f b) -> Stack f b c -> ViewL f a c

And some helper functions:

unbind :: Stack f a b -> ViewL f a b
bindSegment :: (x -> Stream f y) -> Segment f x -> Segment f y

From there the implementations of uncons and run became a lot more inevitable - you just unbind the stack, pattern match, and handle all the cases. It might be possible to implement in terms of the simpler representation I gave earlier.

With the earlier representation, implementing everything up through MonadPlus should still be trivial, it's just the two interpreters, uncons and run, that are much trickier.

If you'd still like to give this a try, start with the representation I just gave and go from there. Otherwise we can go over my 'answer' tomorrow.