ANNOUNCE: enumerator, an alternative iteratee package
Most of you have probably read Oleg's essays on using left-fold enumerators for incremental IO. In short, by encapsulating monadic left-folds in an "Iteratee" type, incremental pure processing is possible without using lazy IO. Sources to read: Oleg: Streams and Iteratees < http://okmij.org/ftp/Streams.html > Magnus Therning: Trying to work out iteratees < http://therning.org/magnus/archives/735 > cdsmith: Iteratees Step By Step (Part 1) < http://cdsmith.wordpress.com/2010/05/23/iteratees-step-by-step-part-1/
John Millikin (me): Understanding Iteratees < http://ianen.org/articles/understanding-iteratees/ > Currently, the primary package for left-fold enumerators is John Lato's "iteratee". It is based on Oleg's original code, extended to support various forms of containers, platform-specific IO, and codecs for the WAV and TIFF formats. While I appreciate Mr. Lato's development of the package, I find it far too large, and its documentation too sparse, to effectively use. To correct this, I've written the "enumerator" package. It is also derived from Oleg's IterateeM.hs , but with a simplified API and significantly reduced dependency list. Hackage entry: http://hackage.haskell.org/package/enumerator Haddock docs: http://ianen.org/haskell/enumerator/api-docs/ Source code (literate PDF): http://ianen.org/haskell/enumerator/enumerator.pdf darcs get http://ianen.org/haskell/enumerator/ Additionally, I've included examples of using enumerators to implement simplified versions of the "cat" and "wc" utilities. These should serve as a useful starting point for anybody who wants to use enumerators in their own code: http://patch-tag.com/r/jmillikin/enumerator/snapshot/current/content/pretty/... http://patch-tag.com/r/jmillikin/enumerator/snapshot/current/content/pretty/... There are already a few libraries using the existing "iteratee" package (snap, attoparsec-iteratee, hexpat-iteratee); I am very interested in advice from the authors of these libraries. In particular, are any of the removed features (ListLike, WrappedByteString, seeking) something your libraries depend on? Are there any useful combinators you'd like to see included?
Hi John, Thanks for creating a competitor to the iteratee library. I think iteratees are an important abstraction, but there are some things about the iteratee library that I'm not fond of, despite John Lato doing a great job. I think having a bit of healthy competition to explore the design space is excellent. I have questions for you below. On Wed, Aug 18, 2010 at 9:31 PM, John Millikin <jmillikin@gmail.com> wrote:
Most of you have probably read Oleg's essays on using left-fold enumerators for incremental IO. In short, by encapsulating monadic left-folds in an "Iteratee" type, incremental pure processing is possible without using lazy IO. Sources to read:
[snip]
While I appreciate Mr. Lato's development of the package, I find it far too large, and its documentation too sparse, to effectively use. To correct this, I've written the "enumerator" package. It is also derived from Oleg's IterateeM.hs , but with a simplified API and significantly reduced dependency list.
I don't mind the dependency list, but I was mildly concerned that iteratee appears to work only on unix and that the API is a bit rough.
Hackage entry: http://hackage.haskell.org/package/enumerator Haddock docs: http://ianen.org/haskell/enumerator/api-docs/ Source code (literate PDF): http://ianen.org/haskell/enumerator/enumerator.pdf
darcs get http://ianen.org/haskell/enumerator/
Additionally, I've included examples of using enumerators to implement simplified versions of the "cat" and "wc" utilities. These should serve as a useful starting point for anybody who wants to use enumerators in their own code:
http://patch-tag.com/r/jmillikin/enumerator/snapshot/current/content/pretty/...
http://patch-tag.com/r/jmillikin/enumerator/snapshot/current/content/pretty/...
The main reason I would use iteratees is for performance reasons. To help me, as a potential consumer of your library, could you please provide benchmarks for comparing the performance of enumerator with say, a) iteratee, b) lazy/strict bytestring, and c) Prelude functions? I'm interested in both max memory consumption and run-times. Using criterion and/or progression to get the run-times would be icing on an already delicious cake!
There are already a few libraries using the existing "iteratee" package (snap, attoparsec-iteratee, hexpat-iteratee); I am very interested in advice from the authors of these libraries. In particular, are any of the removed features (ListLike, WrappedByteString, seeking) something your libraries depend on? Are there any useful combinators you'd like to see included?
The only reason iteratee provides WrappedByteString is because the type class used to abstract over the stream type requires something with kind * -> * and ByteString has kind *. The extra wrapping just adds an ignored phantom type to bytestrings. So if you don't require specific kinds I don't think you'd need to provide a WrappedByteString. ListLike is possibly nice, but in the type indexed iteratee implementation that I started (but could not finish due to some issues with the type indexing) I didn't use it. ListLike doesn't support type threaded lists at all. On a side note, in my type threaded iteratee library, I initially elided StreamChunk but later added something similar in because I found it useful. I can't recall of the top of my head what the reasoning was, but I could dig deeper if it interests you. I was also following a fairly faithful re-implementation of John Lato's implementation, just with type indexing. I should probably post my partial library regardless. Perhaps others can find ways around the bits I was stuck on. I can see seeking as being important as your library moves into new domains of use. Particularly when reading large binary streams when the data is sparse. Thanks and congrats! Jason
On Wed, Aug 18, 2010 at 23:33, Jason Dagit <dagit@codersbase.com> wrote:
The main reason I would use iteratees is for performance reasons. To help me, as a potential consumer of your library, could you please provide benchmarks for comparing the performance of enumerator with say, a) iteratee, b) lazy/strict bytestring, and c) Prelude functions? I'm interested in both max memory consumption and run-times. Using criterion and/or progression to get the run-times would be icing on an already delicious cake!
Oleg has some benchmarks of his implementation at < http://okmij.org/ftp/Haskell/Iteratee/Lazy-vs-correct.txt >, which clock iteratees at about twice as fast as lazy IO. He also compares them to a native "wc", but his comparison is flawed, because he's comparing a String iteratee vs byte-based wc. I'll benchmark my "wc" and "cat" against common alternative implementations. My expectation it that they will be much slower than buffers, slightly slower than strict bytestrings, and faster than lazy bytestrings. One of the large advantages iteratees have over lazy IO is that space use is very predictable. While exact numbers depend on the enumerator and iteratee, they are typically small and constant. For example, enumFile uses a 4096-byte buffer which is copied to a ByteString[1], so "cat" will use only about 10 KiB for a file copy. enumHandle lets this value be tuned, depending on whether you'd like smaller space use or fewer buffer reads. [1] I don't know why this is done -- the reuse buffer/copy idiom is present in Oleg's code, but I suspect just using B.hGet will be more efficient. I'll do some benchmarks to confirm.
ListLike is possibly nice, but in the type indexed iteratee implementation that I started (but could not finish due to some issues with the type indexing) I didn't use it. ListLike doesn't support type threaded lists at all. On a side note, in my type threaded iteratee library, I initially elided StreamChunk but later added something similar in because I found it useful. I can't recall of the top of my head what the reasoning was, but I could dig deeper if it interests you. I was also following a fairly faithful re-implementation of John Lato's implementation, just with type indexing. I should probably post my partial library regardless. Perhaps others can find ways around the bits I was stuck on.
If you can recall the reasoning behind using ListLike or StreamChunk, it would be useful. Their advantages over simply using lists is not obvious to me.
I can see seeking as being important as your library moves into new domains of use. Particularly when reading large binary streams when the data is sparse.
Though I don't have any personal experience writing Haskell parsers for sparsely-populated files, I suspect that folds are poorly adapted to seeking. It will probably be more efficient to implement your own enumerator or enumeratee, which contains logic for skipping uninteresting portions of the file.
Just released version 0.1.1, which includes: * Michael Snoyman's improved 'consume' * (>==>) and (<==<) operators, for composing enumerators (sort of like (>=>) for monads) * ($$) operator, an alias for (==<<), which matches Oleg's operator and makes reading 'run' statements a bit easier. * catchError, for handling errors * liftTrans, for lifting an iteratee's inner monad to a monad transformer * liftFoldL and liftFoldL', for building iteratees out of pure left folds. An example of their use is 'iterLines' in Examples/wc.hs * liftFoldM, like liftFoldL but for monadic left folds
Just released 0.2. It has the text IO and codecs module, with support for ASCII, ISO-8859-1, UTF-8, UTF-16, and UTF-32. It should be relatively easy to add support for codec libraries like libicu or libiconv in the future. Both encoding and decoding are incremental, so you can (for example) process million-line logfiles in constant space. Examples/wc.hs has been updated to use this decoding module for its "character count" mode, which should allow users to see how it's used. Basically, you use 'joinI' to flatten the iteratees returned from enumeratees. The joinI / enumeratee style is used for implementing nested streams. This also changes the binary enumHandle to use non-blocking IO, as recommended by Magnus Therning. I'm embarrassed to admit I still don't understand the improvement, exactly, but three people so far have told me it's a good idea. As always, API docs and a literate PDF are available at: http://ianen.org/haskell/enumerator/api-docs/ http://ianen.org/haskell/enumerator/enumerator.pdf
Hi John, What do you think of putting those parsing functions like head, last, length, etc, under another module or, alternatively, putting the main definitions under another module (say, Base or Core)? I wouldn't mind if they all get re-exported. I say that because since the library aims to be minimalistic, it would be nice to import the core parts only. That makes it easy to avoid some name clashes as well. Take care, Paulo
participants (3)
-
Jason Dagit -
John Millikin -
Paulo Tanimoto