[Haskell-cafe] strictness properties of monoidal folds

[Sebastian Fischer]

Hello Cafe,

left- and rightwards folds come in strict and lazy variants foldl/fold' and
foldr/foldr' which makes sense because strict versions sometimes use less
stack space while lazy versions support infinite data. For example,

head (foldr (:) [] [1..])

returns in an instant while

head (foldr' (:) [] [1..])

diverges. On the other hand

foldl' (flip (:)) 0 [1..10^9]

runs in constant space while

foldl (flip (:)) 0 [1..10^9]

consumes all memory available on my machine (at least without optimizations.
With optimizations GHC's strictness analyzer seems to be smart enough to
make the accumulator strict.)

Data.Foldable also provides the monoidal fold function foldMap. It is left
unspecified whether the elements are accumulated leftwards, rightwards or in
some other way, which is possible because the combining function is required
to be associative. Does this additional freedom for implementors go so far
as to allow for strict accumulation? Is it safe to implement foldMap
(without prime) with a strict accumulator or are there examples where lazy
accumulation is useful like in the above foldr example and distinguishable
from strict accumulation without breaking the monoid laws?

Sebastian

P.S. I thought the `Last` monoid would be an example that requires a lazy
accumulator but it is not because the `Just` constructor guards list
elements.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Regular Expression Parsing via derivatives

[Chris Smith]

On Mon, 2011-08-01 at 12:38 -0400, Alex Clemmer wrote:
> Hmm. Not sure how I missed that. And, I also inquired about developing
> a "core featre" instead of a library -- implying disparity where in
> retrospect there doesn't appear to be any.

Right... the only regular expression support for Haskell at all comes in
the form of libraries.  One of the nice things about Haskell is how
little has to be built in to the language.

-- 
Chris Smith


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

Re: [Haskell-cafe] Regular Expression Parsing via derivatives

[Alex Clemmer]

Hmm. Not sure how I missed that. And, I also inquired about developing a
"core featre" instead of a library -- implying disparity where in retrospect
there doesn't appear to be any.

That's too bad, but thanks for the helpful response!

On Mon, Aug 1, 2011 at 12:26 PM, Antoine Latter  wrote:

> On Mon, Aug 1, 2011 at 10:51 AM, Alex Clemmer
>  wrote:
> > Hi Haskell people,
> >
> > I've been snooping through various mailing lists and the current Haskell
> > implementation of regular expressions and I was wondering if there has
> been
> > a discussion about implementing regex parsing with derivatives. If so, I
> > haven't seen it. If not, I'd like to have a discussion about it -- if for
> no
> > other reason than to decide whether I should implement it as a library,
> or
> > (to attempt to implement it) as a core feature.
> >
> > For those of you who don't know, recent work by Might and Darais
> indicates
> > that parsing CFGs can be done better (i.e., significantly faster) than
> more
> > "traditional" approaches. Might's presenting at ICFP later in September
> > about it.
> >
> > I guess the first thing I should ask is, which mailing list is actually
> the
> > right place to field this inquiry. I considered dropping it in the main
> > haskell list, but wasn't sure how people would respond.
> >
>
> This is probably the right list to ask.
>
> I don't know much about the topic, a a quick Google search turned up:
>
> http://hackage.haskell.org/package/regex-pderiv
>
> which has the right keywords.
>
> More discussion on related (or not!) here:
>
>
> http://www.google.com/search?q=Regular+Expression+derivative+haskell&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US:unofficial&client=firefox-a
>
> Antoine
>
> > --
> > Alex
> >
> >
> > ___
> > Haskell-Cafe mailing list
> > Haskell-Cafe@haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
> >
>



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

Re: [Haskell-cafe] Regular Expression Parsing via derivatives

[Antoine Latter]

On Mon, Aug 1, 2011 at 10:51 AM, Alex Clemmer
 wrote:
> Hi Haskell people,
>
> I've been snooping through various mailing lists and the current Haskell
> implementation of regular expressions and I was wondering if there has been
> a discussion about implementing regex parsing with derivatives. If so, I
> haven't seen it. If not, I'd like to have a discussion about it -- if for no
> other reason than to decide whether I should implement it as a library, or
> (to attempt to implement it) as a core feature.
>
> For those of you who don't know, recent work by Might and Darais indicates
> that parsing CFGs can be done better (i.e., significantly faster) than more
> "traditional" approaches. Might's presenting at ICFP later in September
> about it.
>
> I guess the first thing I should ask is, which mailing list is actually the
> right place to field this inquiry. I considered dropping it in the main
> haskell list, but wasn't sure how people would respond.
>

This is probably the right list to ask.

I don't know much about the topic, a a quick Google search turned up:

http://hackage.haskell.org/package/regex-pderiv

which has the right keywords.

More discussion on related (or not!) here:

http://www.google.com/search?q=Regular+Expression+derivative+haskell&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US:unofficial&client=firefox-a

Antoine

> --
> Alex
>
>
> ___
> 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] Regular Expression Parsing via derivatives

[Alex Clemmer]

Hi Haskell people,

I've been snooping through various mailing lists and the current Haskell
implementation of regular expressions and I was wondering if there has been
a discussion about implementing regex parsing with derivatives. If so, I
haven't seen it. If not, I'd like to have a discussion about it -- if for no
other reason than to decide whether I should implement it as a library, or
(to attempt to implement it) as a core feature.

For those of you who don't know, recent work by Might and
Daraisindicates that parsing CFGs can
be done better (
*i.e.*, significantly faster) than more "traditional"
approaches.
Might's presenting at ICFP later in September about it.

I guess the first thing I should ask is, which mailing list is actually the
right place to field this inquiry. I considered dropping it in the main
haskell list, but wasn't sure how people would respond.

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

Re: [Haskell-cafe] State of play with Haskell-Cocoa (Objective-C) bindings?

[Edward Amsden]

On Sun, Jul 31, 2011, Luke Evans  wrote:
> - HOC seems very close to what I'm looking for, but the project looks pretty 
> 'dormant'.

My last go-round with HOC it failed at parsing Apple's Objective-C
headers. I've been thinking of digging into it and fixing it, but I'm
a student with very little time so I've not started yet.
-- 
Edward Amsden
Student
Computer Science
Rochester Institute of Technology
www.edwardamsden.com

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

Re: [Haskell-cafe] Unbelievable parallel speedup

[Simon Marlow]

On 03/06/2011 13:10, John D. Ramsdell wrote:

I've enjoyed reading Simon Marlow's new tutorial on parallel and
concurrent programming, and learned some surprisingly basic tricks.  I
didn't know about the '-s' runtime option for printing statistics.  I
decided to compute speedups for a program I wrote just as Simon did,
after running the program on an unloaded machine with four processors.
  When I did, I found the speedup on two processors was 2.4, on three
it was 3.2, and on four it was 4.4!  Am I living in a dream world?

I ran the test nine more times, and here is a table of the speedups.

2.35975 3.42595 4.39351
1.57458 2.18623 2.94045
1.83232 2.77858 3.41629
1.58011 2.37084 2.94913
2.36678 3.63694 4.42066
1.58199 2.29053 2.95165
1.57656 2.34844 2.94683
1.58143 2.3242  2.95098
2.36703 3.36802 4.41918
1.58341 2.30123 2.93933

That last line looks pretty reasonable to me, and is what I expected.
Let's look at a table of the elapse times.

415.67  176.15  121.33  94.61
277.52  176.25  126.94  94.38
321.37  175.39  115.66  94.07
277.72  175.76  117.14  94.17
415.63  175.61  114.28  94.02
277.75  175.57  121.26  94.10
277.68  176.13  118.24  94.23
277.51  175.48  119.40  94.04
415.58  175.57  123.39  94.04
277.62  175.33  120.64  94.45

Notice that the elapse times for two and four processors is pretty
consistent, and the one for three processors is a little inconsistent,
but the times for the single processor case are all over the map.  Can
anyone explain all this variance?


This looks like automatic CPU speed throttling to me.  The OS is 
decreasing the CPU clock speed automatically to save power.  Normally it 
happens in steps (0.75x, 0.5x max clock).  This would also explain why 
when using more cores the results are more stable: the OS has determined 
that there is lots of work to do, and has stopped throttling the CPU. 
If you can it off, do so.


Cheers,
Simon


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