On Feb 17, 2008 4:13 PM, Brandon S. Allbery KF8NH wrote:

Have you looked at the stream-fusion package on Hackage? http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream- fusion-0.1.1

Yeah, I've seen this. It's nice that this is separated, but a little unsatisfying that the bytestring library reimplements it rather than just requiring it as a dependency. This, and the fact that bytestrings are way fast, while the stream-fusion stuff is sometimes slower than just using lists, make me think that either (1) there's sometimes an advantage in programming directly to streams, or (2) maybe more of the stream functions need to be exposed in the API. Or maybe there's another reason... that's part of my question. Chad

chad.scherrer:

On Feb 17, 2008 4:13 PM, Brandon S. Allbery KF8NH wrote:

...

Have you looked at the stream-fusion package on Hackage? http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream- fusion-0.1.1

Yeah, I've seen this. It's nice that this is separated, but a little unsatisfying that the bytestring library reimplements it rather than just requiring it as a dependency. This, and the fact that bytestrings

they currently use two different fusion systems. bytestring uses an older version of what is now stream fusion. at some point we'll switch bytestrings over to using the new stuff in the stream-fusion package, since its a lot better.

are way fast, while the stream-fusion stuff is sometimes slower than just using lists, make me think that either (1) there's sometimes an advantage in programming directly to streams, or (2) maybe more of the stream functions need to be exposed in the API. Or maybe there's another reason... that's part of my question.

ah, you assume stream-fusion lists are slower. for list stuff, since 6.8, i've only seen things the same speed or better. but if you have a program doing the wrong thing, it would be worth looking at. -- Don

chad.scherrer:

...

they currently use two different fusion systems. bytestring uses an older version of what is now stream fusion. at some point we'll switch bytestrings over to using the new stuff in the stream-fusion package, since its a lot better.

Oh, that's pretty interesting. I had assumed bytestring had the latest fusion stuff.

...

ah, you assume stream-fusion lists are slower. for list stuff, since 6.8, i've only seen things the same speed or better. but if you have a program doing the wrong thing, it would be worth looking at.

I was just going by the "Lists to Streams to Nothing At All" paper. That's great that it's gotten faster! Does that mean the path for replacing Data.List with this is any clearer?

Not yet. We still don't have a good system for fusing nested concatMaps, that GHC likes, which come up when you desugar list comprehensions. If you can live without too many comprehensions, then the stream-fusion package is entirely viable. -- Don

On Feb 17, 2008 5:01 PM, Don Stewart wrote:

yeah, with lists, as compared to bytestrings, there are:

* more complex operations to fuse * allocation is much cheaper (lazy list cons nodes) * built in desugaring for build/foldr fusion interferes (enumerations, comprehensions)

so the benefits of fusing lists are less obvious than bytestrings, where every fusion point knocks out a big array allocation, and they're a bit more complex to get the full api going.

Ok, that makes sense.

no, using the rules should be fine. you're not supposed to program in the stream abstraction.

I was working on some run-length encoding stuff and found it most natural to do a lot of it using unfoldr, and I had a state in the unfold that was naturally represented as a tuple. I got a little worried about all the packing and unpacking tuples not being optimized out, and this got me wondering about just using Streams directly. At the time, the Skip constructor for a Step felt natural to use in some places, which I thought could be really convenient. I dunno, maybe it's not an issue. Hmm, if it would help I can try to post some of the code...

...

Wouldn't it make sense to do something like

data ArrayList a i e = Empty | Chunk !(a i e) (ArrayList a i e) ?

someone could do that. we chose to go with the monomorphic case, since its easier to get the api right, and the performance right.

Unless I'm overlooking something, this would involve something like... (1) make the fusion stuff apply to an IArray (pretty handy anyway) (2) make (strict) ByteString an instance of IArray (or maybe via StorableArray) (3) write an ArrayList module, similar to Data.ByteString.Lazy

From this, it would be pretty short again, in theory, to write an alternate ByteString library using the abstractions. The point of this would be to leverage future code improvements and reduce code duplication.

Does this seem reasonable? Or is it too soon to consider this kind of extension? Chad

On Feb 17, 2008 6:06 PM, Derek Elkins wrote:

It's -quite- possible that a coalgebraic perspective is much more natural for your code/problem. If that's the case, use it (the coalgebraic perspective that is). Obviously depending on the internals of the stream library is not a good idea and using Streams directly was not their intent, but it is your code. Do what you will.

Here's an example of the problem. Start with a function extract :: [Int] -> [a] -> [a] extract = f 0 where f !k nss@(n:ns) (x:xs) | n == k = x : f (k+1) ns xs | otherwise = f (k+1) nss xs f _ _ _ = [] which is just a more efficient way of getting extract ns xs == [xs !! n | n <- ns] There should be a way to write this that will be friendly for stream fusion. The best option I can see is unfoldr. But if you try to write it this way, you get something like extract' ns xs = unfoldr f (0,ns,xs) where f (!k, nss@(n:ns), x:xs) | n == k = Just (x, (k + 1, ns, xs)) | otherwise = f (k+1, nss, xs) f _ = Nothing This is fine, except that the second-to-last line means this is still recursive. If I understand correctly, fusion requires that the recursion be encapsulated within the unfoldr or other functions that are expressed internally as stream functions. We could encapsulate the recursion with a function stepUnfoldr :: (s -> Step a s) -> s -> [a] stepUnfoldr f s = unfoldr g s where g s = case f s of Done -> Nothing Yield x s' -> Just (x,s') Skip s' -> g s' Using this, we could just write extract'' ns xs = stepUnfoldr f (0,ns,xs) where f (!k, nss@(n:ns), x:xs) | n == k = Yield x (k + 1, ns, xs) | otherwise = Skip (k+1, nss, xs) f _ = Done This is a pretty natural way to write the algorithm, and the recursion is nicely tucked away. The only remaining question is whether we can get things to fuse. The type of stepUnfoldr looks familiar... *Main> :t stepUnfoldr stepUnfoldr :: (s -> Step a s) -> s -> [a] *Main> :t \f s -> unstream $ Stream f s \f s -> unstream $ Stream f s :: (Data.Stream.Unlifted s) => (s -> Step a s) -> s -> [a] If we could somehow swap out our state type for an unlifted one, we could write a rule stepUnfoldr f = unstream . Stream f It seems like there might be some subtleties there to watch out for, but I'm not sure yet. Anyway, this is the kind of thing I had in mind when I asked about using the internals of Data.Stream more directly. Chad

On Wed, Feb 20, 2008 at 5:53 PM, Roman Leshchinskiy wrote:

In general, I don't see why programming directly with streams is something that should be avoided. You do have to be quite careful, though, if you want to get good performance (but GHC's simplifier is becoming increasingly robust in this respect).

Hmm. I was taking the approach of getting something working, given what is currently exported from Data.Stream. How would you deal with this? Should there be a Data.Stream.Internal or something that exports streams and unlifted types? If I'm understanding this correctly, these things were not exported in the first place because this fusion framework provides an approximation, but not an isomorphism, so partial bottoms don't always behave nicely. I was hoping to get around this by programming instead to Step and then hoping rules could be constructed to translate to Streams. Do you think there's a better way around it?

...

extract ns xs == [xs !! n | n <- ns]

Note that in contrast to your function, this doesn't assume that ns is sorted and hence, there is no way to implement this without producing an intermediate list.

Oh yes, good point. It's so easy to forget about assumptions like that. Chad