Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)

2011-04-26 Thread John Lato 
Joining slightly late...


 From: John Millikin jmilli...@gmail.com

 John Lato's iteratee package is based on IterateeMCPS.hs[1]. I used
 IterateeM.hs for enumerator, because when I benchmarked them the non-CPS
 version was something like 10% faster on most operations.


Based on tests I did before iteratee-0.4, the fastest implementation was
Oleg's alternate design which is in the comments of IterateeM.hs.  I don't
think any current packages use that however, with good reason.

I'd be interested to see the results of a shootout between iteratee and
enumerator.  I would expect them to be basically equivalent most of the
time, with maybe two or three operations with a small (but consistent)
difference one way or the other.

John L.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)

2011-04-26 Thread John Millikin 
On Tuesday, April 26, 2011 7:19:25 AM UTC-7, John Lato wrote:

 I'd be interested to see the results of a shootout between iteratee and 
 enumerator.  I would expect them to be basically equivalent most of the 
 time, with maybe two or three operations with a small (but consistent) 
 difference one way or the other.


I did some basic benchmarks a few months ago; if I remember correctly, it 
depends almost entirely on how well GHC optimizes CPS on a particular 
platform. The relative performace was very similar to Lennart Kolmodin's 
benchmarks of binary at  
http://lennartkolmodin.blogspot.com/2011/02/binary-by-numbers.html . In 
particular, CPS/iteratee is faster on 32-bit, while state 
passing/enumerator is faster on 64-bit.

This difference exists for almost all operations, and was on the order of 
5-15% depending on the shape of the input. I couldn't figure out a good way 
to benchmark the libraries themselves when there's so much noise from the 
compiler.

I'm waiting for GHC7 to stabilise a bit before doing another benchmark -- 
the LLVM backend and new CPS handling should make both implementations 
faster, once they're a bit more mature. I really hope CPS becomes as fast on 
64-bit as it is on 32-bit, because it's a much cleaner implementation.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)

2011-04-26 Thread John Lato 
On Tue, Apr 26, 2011 at 6:32 PM, John Millikin jmilli...@gmail.com wrote:

 On Tuesday, April 26, 2011 7:19:25 AM UTC-7, John Lato wrote:

 I'd be interested to see the results of a shootout between iteratee and
 enumerator.  I would expect them to be basically equivalent most of the
 time, with maybe two or three operations with a small (but consistent)
 difference one way or the other.


 I did some basic benchmarks a few months ago; if I remember correctly, it
 depends almost entirely on how well GHC optimizes CPS on a particular
 platform. The relative performace was very similar to Lennart Kolmodin's
 benchmarks of binary at 
 http://lennartkolmodin.blogspot.com/2011/02/binary-by-numbers.html . In
 particular, CPS/iteratee is faster on 32-bit, while state
 passing/enumerator is faster on 64-bit.

 This difference exists for almost all operations, and was on the order of
 5-15% depending on the shape of the input. I couldn't figure out a good way
 to benchmark the libraries themselves when there's so much noise from the
 compiler.


That figures.  Thanks for sharing this.

John L.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)

2011-04-22 Thread Maciej Marcin Piechotka 
On Tue, 2011-04-19 at 10:02 -0300, Felipe Almeida Lessa wrote:
 
 Now, that's what I get from reading the code.  I don't remember if it
 is explicitly allowed or forbidden for an iteratee to generate
 leftovers out of nowhere.  My guess is that it doesn't make much sense
 to allow it. 

For the record: such code is therefore illegal

abab :: Iteratee Char Identity ()
abab = continue parseA
   where parseA (Chunks ('a':'b':xs)) = parseA (Chunks xs)
 parseA (Chunks ('a':[])) = continue parseB
 parseA (Chunks xs@(_:_)) = yield () xs
 parseA (Chunks []) = continue parseA
 parseA EOF = yield () EOF
 parseB (Chunks ('b':xs)) = parseA (Chunks xs)
 parseB (Chunks xs@(_:_)) = yield () (a:xs)
 parseB (Chunks []) = continue parseB
 parseB EOF = yield () ['a']

Regards


signature.asc
Description: This is a digitally signed message part
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)

2011-04-22 Thread Felipe Almeida Lessa 
On Fri, Apr 22, 2011 at 5:54 AM, Maciej Marcin Piechotka
uzytkown...@gmail.com wrote:
 For the record: such code is therefore illegal

 abab :: Iteratee Char Identity ()
 abab = continue parseA
       where parseA (Chunks ('a':'b':xs)) = parseA (Chunks xs)
             parseA (Chunks ('a':[])) = continue parseB
             parseA (Chunks xs@(_:_)) = yield () xs
             parseA (Chunks []) = continue parseA
             parseA EOF = yield () EOF
             parseB (Chunks ('b':xs)) = parseA (Chunks xs)
             parseB (Chunks xs@(_:_)) = yield () (a:xs)
             parseB (Chunks []) = continue parseB
             parseB EOF = yield () ['a']

Is it really illegal?  I guess you're pointing out a problem with the
last line, because it's EOF and we yield something.  But that
something was given to us in some continue step.  IMHO, that's
perfectly fine.  The same thing goes for the other yield in parseB.

Cheers,

-- 
Felipe.

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)

2011-04-22 Thread John A. De Goes 

You wouldn't be so confused if you had actually looked at Lato's implementation 
and compared it to Oleg's most recent version.

Regards,

John A. De Goes
Twitter: @jdegoes 
LinkedIn: http://linkedin.com/in/jdegoes

On Apr 21, 2011, at 6:27 PM, Jason Dagit wrote:

 
 
 On Thu, Apr 21, 2011 at 8:36 AM, John A. De Goes j...@n-brain.net wrote:
 
 This is a much cleaner definition of Iteratee and I'm happy to see it.
 
 I'm confused by this comment.  Isn't John Lato's implementation of Iteratee 
 (on hackage) is based on the example implementation that Oleg pointed you 
 towards?
 
 

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)

2011-04-21 Thread oleg 

Daniel Schuessler wrote:

 The thing I don't understand yet is the last line: Why is it OK to discard the
 leftover input from the (f x) Iteratee and yield just the leftover input from
 the first one (m0)?

First of all, the question is about an older version of Iteratee. For
example, the following code 
http://okmij.org/ftp/Haskell/Iteratee/Iteratee.hs
defines Iteratee a bit differently so the question does not apply.

 data Iteratee a = IE_done a
 | IE_cont (Maybe ErrMsg) (Stream - (Iteratee a,Stream))

 instance Monad Iteratee where
 return = IE_done
 IE_done a   = f = f a
 IE_cont e k = f = IE_cont e (docase . k)
  where
  docase (IE_done a, stream)   = case f a of
IE_cont Nothing k - k stream
i - (i,stream)
  docase (i, s)  = (i = f, s)

No left-over is discarded any more. 

Your question is about the previous design, called `The second design'
described in Iteratee.hs. The corresponding comment block answers your
question, please search for ``Justification for the case IE_done x
s = f''.

Please see
http://okmij.org/ftp/Haskell/Iteratee/IterateeM.hs
for the `production' case of Iteratee in a base monad. The file
IterateeM.hs talks about one more design, and its drawbacks. 

It's all about finding the optimal trade-off, I guess.



___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)

2011-04-21 Thread John A. De Goes 

This is a much cleaner definition of Iteratee and I'm happy to see it.

When are you going to move from your FTP site to Github, by the way? :)

Regards,

John A. De Goes
Twitter: @jdegoes 
LinkedIn: http://linkedin.com/in/jdegoes

On Apr 21, 2011, at 12:32 AM, o...@okmij.org wrote:

 
 Daniel Schuessler wrote:
 
 The thing I don't understand yet is the last line: Why is it OK to discard 
 the
 leftover input from the (f x) Iteratee and yield just the leftover input from
 the first one (m0)?
 
 First of all, the question is about an older version of Iteratee. For
 example, the following code 
   http://okmij.org/ftp/Haskell/Iteratee/Iteratee.hs
 defines Iteratee a bit differently so the question does not apply.
 
 data Iteratee a = IE_done a
   | IE_cont (Maybe ErrMsg) (Stream - (Iteratee a,Stream))
 
 instance Monad Iteratee where
   return = IE_done
   IE_done a   = f = f a
   IE_cont e k = f = IE_cont e (docase . k)
where
docase (IE_done a, stream)   = case f a of
  IE_cont Nothing k - k stream
  i - (i,stream)
docase (i, s)  = (i = f, s)
 
 No left-over is discarded any more. 
 
 Your question is about the previous design, called `The second design'
 described in Iteratee.hs. The corresponding comment block answers your
 question, please search for ``Justification for the case IE_done x
 s = f''.
 
 Please see
   http://okmij.org/ftp/Haskell/Iteratee/IterateeM.hs
 for the `production' case of Iteratee in a base monad. The file
 IterateeM.hs talks about one more design, and its drawbacks. 
 
 It's all about finding the optimal trade-off, I guess.
 
 
 
 ___
 Haskell-Cafe mailing list
 Haskell-Cafe@haskell.org
 http://www.haskell.org/mailman/listinfo/haskell-cafe


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)

2011-04-21 Thread Jason Dagit 
On Thu, Apr 21, 2011 at 8:36 AM, John A. De Goes j...@n-brain.net wrote:


 This is a much cleaner definition of Iteratee and I'm happy to see it.


I'm confused by this comment.  Isn't John Lato's implementation of Iteratee
(on hackage) is based on the example implementation that Oleg pointed you
towards?
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)

2011-04-21 Thread John Millikin 
John Lato's iteratee package is based on IterateeMCPS.hs[1]. I used 
IterateeM.hs for enumerator, because when I benchmarked them the non-CPS 
version was something like 10% faster on most operations.

The new IterateeM.hs solves some problems with the old encoding, but I 
haven't switched enumerator to it yet because it would break backwards 
compatibility.

[1] http://okmij.org/ftp/Haskell/Iteratee/IterateeMCPS.hs
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)

2011-04-20 Thread John Millikin 
It's forbidden for an iteratee to yield extra input that it hasn't consumed; 
however, this is unfortunately not enforced by the type system. ___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)

2011-04-20 Thread John A. De Goes 

It's not OK and it's an artifact of the weak-typing and ill-defined semantics 
that pervade iteratee libraries. It's possible to do a lot of bad stuff, 
including binding with an iteratee yielding a remainder without consuming input.

Regards,

John A. De Goes
Twitter: @jdegoes 
LinkedIn: http://linkedin.com/in/jdegoes

On Apr 19, 2011, at 6:27 AM, Daniel Schüssler wrote:

 Hello,
 
 for reference, said instance is:
 
 instance Monad m = Monad (Iteratee a m) where
  return x = yield x (Chunks [])
 
  m0 = f = ($ m0) $ fix $
  \bind m - Iteratee $ runIteratee m = \r1 -
  case r1 of
  Continue k - return (Continue (bind . k))
  Error err - return (Error err)
  Yield x (Chunks []) - runIteratee (f x)
  Yield x extra - runIteratee (f x) = \r2 -
  case r2 of
  Continue k - runIteratee (k 
 extra)
  Error err - return (Error err)
  Yield x' _ - return (Yield x' 
 extra)
 
 The thing I don't understand yet is the last line: Why is it OK to discard 
 the 
 leftover input from the (f x) Iteratee and yield just the leftover input from 
 the first one (m0)?
 
 Cheers,
 Daniel
 
 ___
 Haskell-Cafe mailing list
 Haskell-Cafe@haskell.org
 http://www.haskell.org/mailman/listinfo/haskell-cafe


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)

2011-04-19 Thread Daniel Schüssler 
Hello,

for reference, said instance is:

 instance Monad m = Monad (Iteratee a m) where
   return x = yield x (Chunks [])
 
   m0 = f = ($ m0) $ fix $
   \bind m - Iteratee $ runIteratee m = \r1 -
   case r1 of
   Continue k - return (Continue (bind . k))
   Error err - return (Error err)
   Yield x (Chunks []) - runIteratee (f x)
   Yield x extra - runIteratee (f x) = \r2 -
   case r2 of
   Continue k - runIteratee (k 
 extra)
   Error err - return (Error err)
   Yield x' _ - return (Yield x' 
 extra)

The thing I don't understand yet is the last line: Why is it OK to discard the 
leftover input from the (f x) Iteratee and yield just the leftover input from 
the first one (m0)?

Cheers,
Daniel

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)

2011-04-19 Thread Felipe Almeida Lessa 
2011/4/19 Daniel Schüssler anotheraddr...@gmx.de:
 Hello,

 for reference, said instance is:

 instance Monad m = Monad (Iteratee a m) where
       return x = yield x (Chunks [])

       m0 = f = ($ m0) $ fix $
               \bind m - Iteratee $ runIteratee m = \r1 -
                       case r1 of
                               Continue k - return (Continue (bind . k))
                               Error err - return (Error err)
                               Yield x (Chunks []) - runIteratee (f x)
                               Yield x extra - runIteratee (f x) = \r2 -
                                       case r2 of
                                               Continue k - runIteratee (k 
 extra)
                                               Error err - return (Error err)
                                               Yield x' _ - return (Yield x' 
 extra)

 The thing I don't understand yet is the last line: Why is it OK to discard the
 leftover input from the (f x) Iteratee and yield just the leftover input from
 the first one (m0)?

On that stage no input was given to (f x), we just runned it without
anything and it already yielded something.  So whatever it yielded
must be without leftovers.

Now, that's what I get from reading the code.  I don't remember if it
is explicitly allowed or forbidden for an iteratee to generate
leftovers out of nowhere.  My guess is that it doesn't make much sense
to allow it.

Cheers,

-- 
Felipe.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe