ping

Done, PTAL

LGTM.

@cartazio, thoughts?

1. i think this is a VALID / USEFUL contribution

2. this seems like a solid natureal implementation if we ignore fusion.... but should we? (Ryan points out that eg the partition function does too, but should it?)

3. how about we figure this out by seeing if we can construct the bundle/stream monad combinator versions of this and compare them

4. (@RyanGlScott how many things in Vector.Generic dont have an impl in bundle or stream? we may need to review that ... perhaps on another ticket
   )

roughly: ignoring fusion this looks good ... but if we ignore fusion we should just use Array right? :)

@cartazio I think uncons would make sense on Streams, but am not sure how to write unsnoc efficiently; is the latter worth doing?

i think you can look at stream-take and stream-last definitions as starting points perhaps?

I swear I saw some machinery for left vs right streams at some point in vector, but i'm not finding it at the moment

https://github.com/haskell/vector/blob/master/Data/Vector/Fusion/Stream/Monadic.hs#L143 has length, not srue if thats quite th right form though

i might be missing something obvious mind you :)

likewise, we probably want to then ahve bundle versions of those operations perhaps? @dolio ?

@cartazio any word on what needs to be done to accept this PR? (e.g. bundle ops)

@cartazio ping

now that the most recent release has been done, i'm catching up on polishing backlog.

i'll look

@strake I do support @cartazio push for thinking about fusion.

With respect to unsnoc it is not feasible to implement it without either duplicated work or materializing the whole vector, because you'd require to iterate the whole stream in order to get to the last element. Therefore your unsnoc implementation is perfectly fine.

As far as uncons is concerned we can convert a vector to a stream, grab the first element from that stream and construct another stream where we drop that first element. I could be wrong of course, since I haven't tried how fusion with rewrite rules will interact with such approach, but I think it should be fine.

uncons :: Monad m => Stream m a -> m (Maybe (a, Stream m a))
uncons str@(Stream step t) = unconsMaybeLoop SPEC t
  where
    unconsMaybeLoop !_ s = do
      r <- step s
      case r of
        Yield x _ -> return $ Just (x, drop 1 str)
        Skip s'   -> unconsMaybeLoop SPEC s'
        Done      -> return Nothing
    {-# INLINE [0] unconsMaybeLoop #-}
{-# INLINE uncons #-}

An even more general and useful approach would be to implement headMaybe in the exact same manner and reuse that to implement uncons:

headMaybe (Stream step t) = headMaybeLoop SPEC t
  where
    headMaybeLoop !_ s = do
      r <- step s
      case r of
        Yield x _ -> return $ Just x
        Skip s'   -> headMaybeLoop SPEC s'
        Done      -> return Nothing
    {-# INLINE [0] headMaybeLoop #-}
{-# INLINE headMaybe #-}

@strake If you'd like to give it a shot that be great if not I'll try it out in a few days myself.

Trying to integrate with fusion only makes it worse. Because we have constant time slicing consecutive uncons/unsonc are very efficient with current implementation.

@strake Thank you for the PR. Sorry it took so long to get it merged.