Yeah, my answer on the ByteString front is to make a bunch of Reducers for a Builder data type that works like the one in Data.Binary.Builder. It generates a much more suitable Reducer and can reduce Chars, Strings, Strict and Lazy UTF8-encoded Bytestrings, etc. I'm using that inside of my toy compiler right now when I need to generate output, like a Lazy ByteString of source. (My variant Builder -- ok, my mostly cut and pasted Builder, has been made slightly smarter and is now tuned to work with UTF8 encoded data, which is what I've been feeding it lately.) I may migrate it into the monoids library from my current project if there is interest, but I'm trying to avoid ballooning that up too far in size again and re-entering dependency hell.

The monoids library drew a pretty hard distinction between things that build up nicely (Monoids/Reducers) and things that tear down easily (Generators) but only works with a few things that do both efficiently (i.e. Seq/FingerTree) For my purposes this has worked rather well, but raw strict (and to a lesser degree, lazy) ByteStrings make abysmal Reducers. ;) 

In the end, bolting a list-like interface on something that can be _made_ to implement all of the operations but can't be made to implement them remotely efficiently, seems like it is asking for trouble, bug reports about performance, and pain.

On the other hand, FingerTrees of wrapped strict ByteStrings work nicely as a monoidal lazy bytestring-like structure that provides an efficient snoc, indexing operation, and very efficient slicing for extracting token values with maximal sharing. I'll be giving a talk at the next Boston Haskell User Group in a few days about my abuse of those in a terrible hodge-podge solution of Iteratees, Parsec 3 and monoids, which yields an efficient parallel/incremental lexer.

I'll see about posting the slides afterwards.

-Edward Kmett

On Thu, Aug 13, 2009 at 4:43 PM, John Lato <jwlato@gmail.com> wrote:
On Thu, Aug 13, 2009 at 1:51 PM, Jake McArthur<jake.mcarthur@gmail.com> wrote:
> John Lato wrote:
>>
>
>> This might work with UVector (I intend to try it this evening); I
>> don't know how well the fusion framework will hold up in class
>> dictionaries.
>
> Do report back, as I am curious as well.

I have just recently hacked together a small test.  The code is at
http://inmachina.net/~jwlato/haskell/testUVector.hs

The task is to generate a list of 1 million Ints (really 1e6-1), map a
multiply by 2, and check to see if any values equal 0.  The uvector
code is (essentially):

> let res = anyU (== ( 0:: Int)) . mapU (* 2) . enumFromToU 1 $ 1000000

and by itself runs in a small fraction of a second.  Technically the
start and stop values are specified on the command line, but these are
the values I predominantly used.

Here are results for some other modes:

ListLike.map: significantly slower, and runs out of memory (memory
request failed)
ListLike.rigidMap: appears to be the same as using mapU directly
mapReduce:  significantly slower (the 1e6 element test completed after
about an hour), but ran in a very small amount of memory.

It looks like GHC was able to see through the rigidMap function at
least, but I don't know if this would still work with the instance
defined in another file.

Cheers,
John
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe