gmane.comp.lang.haskell.cafe

Re: Can Haskell outperform C++?

Roman Werpachowski — 2012-05-18T11:45:12

My apologies to you and Gregg.


OK, got that now. So Haskell doesn't have a *big* advantage over C w/r
to the ease of implementation of both algorithms?


Yes, but aren't the differences in the same ballpark, and if we want
to compare *languages*, we should use identical algorithms to make the
comparison fair.


It matters much less if you write the code to be run multiple times.

Regards,
RW

Re: AI - machine learning

C Gosch — 2012-05-18T11:21:00

Hi all,

I have implemented max-sum/sum-product in c++ before and a while ago,
did the same in Haskell.
I don't think my implementation is as idiomatic Haskellish as I would
like, and I have so far not
published it and also not looked at it for a little while (since I
have some more projects :) ).
However, if you are interested, I will publish it (maybe on github?),
and I think we should join forces.
I am also very interested in machine learning techniques, but I can
unfortunately use neither those nor Haskell at
my day job at present.

Let me know what you think.

Best regards,
Christian


Message: 3
Date: Thu, 17 May 2012 15:36:08 +0400
From: Paul Graphov <graphov< at >gmail.com>
Subject: Re: [Haskell-cafe] AI - machine learning
To: miro <miroslav.karpis< at >gmail.com>
Cc: haskell-cafe< at >haskell.org
Message-ID:
       <CAKHAQn+yFGCdLPoKR0sEhvJobwPPykvqTYieqZeBbzhyVodizg< at >mail.gmail.com>
Content-Type: text/plain; charset=UTF-8

Hi Miro!

I have no useful information for you. Few weeks ago I also checked for
any AI (mac

Re: Can Haskell outperform C++?

Richard O'Keefe — 2012-05-18T03:30:09

On 17/05/2012, at 10:07 PM, Roman Werpachowski wrote:


It was me, not Gregg.  There was and is no claim that method 2 is "much harder
to implement in C or C++".  In fact both methods *were* implemented easily in C.
The claim was and remains solely that
THE TIME DIFFERENCE BETWEEN *ALGORITHMS*
   can be bigger than
THE TIME DIFFERENCE BETWEEN *LANGUAGES*
   and is in this particular case.

(And that's despite the fact that the C version kept the set of unused
elements as a one-native-word bit mask, while the Prolog version kept it
as a linked list.) 

There is also a second claim, which I thought was uncontentious:
the relative difficulty of tasks varies with language.

Re: cool tools

Ryan Newton — 2012-05-17T20:36:36

Indeed, cabal-install 0.14.0 has been *excellent* for me so far.  Thanks
Andres!

On Thu, May 17, 2012 at 10:05 AM, Chris Dornan <chris< at >chrisdornan.com>wrote:

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe< at >haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: Can Haskell outperform C++?

Gregg Lebovitz — 2012-05-17T15:36:42

Isaac,

I understand. Thank you. I will be more careful about my wording in the 
future. I really do appreciate your taking the time to point this out to 
me. I am here to learn and help where I can.

Gregg

On 5/17/2012 11:25 AM, Isaac Gouy wrote:

Re: Can Haskell outperform C++?

Isaac Gouy — 2012-05-17T15:25:54




Gregg,

You wrote that you were looking at the benchmarks and then made a definite assertion about what was shown on the website. Unsuspecting readers would assume that you were truthfully reporting what you saw on the website.

I cannot explain to them why you made an assertion which could be seen not to be true, simply by looking at the benchmarks game website.

best wishes, Isaac

Re: Data Kinds and superfluous (in my opinion) constraints contexts

Iavor Diatchki — 2012-05-17T14:15:56

Hi,

It is quite likely that the error that you are getting with approach 2 is
because when you are constructing the `Combinator` value, there is not
enough type information to figure out how to solve the constraint (and it
sounds like this happens because there is not enough type information to
reduce the type function).   The fix depends on the concrete program but it
might be something as simple as adding a type signature somewhere.

Note, again, that it is not sufficient to know that the constraint could be
solved for any type of the appropriate kind: we need to actually solve the
constraint so that we can determine what the program should do.

The difference between the two `data` definitions is that the second one
uses a technique called _existential quantification_, which "hides" the
type `s`.  If this type appears nowhere else in the surrounding expressions
and the constraint could not be solved, then the constraint is ambiguous.
I could explain that in more detail, if it is unclear please ask.

Happ

cool tools

Chris Dornan — 2012-05-17T14:05:22

I have been playing around with the latest cabal-install (0.14.0) and it is
working really nicely. Having unpacked a cabal bundle you can now type
'cabal install' inside the root and it will work everything out as if you
had asked to install directly from the repo -- very nice.

I have also noticed that GHC is suggesting alternatives when it encounters
missing identifiers. This gives a strong sense of helpfulness that I think
accurately reflects the long and sustained (decades-long) effort that has
gone into making the GHC diagnostics as useful as possible.

The tools are so good because the developers have been paying attention to
the gripes. 

But we should sometimes say thank you too... it is much appreciated.

Chris

Re: Can Haskell outperform C++?

Gregg Lebovitz — 2012-05-17T12:50:58

Isaac,

I see your point. Probably I shouldn't have made that assertion given my 
limited understanding of the benchmarks. I want to thank you for your 
kind and gentle way of pointing this out to me. I feel very welcomed and 
encourage.

I still plan to work on the performance paper with the help of others on 
this list. I look forward to your support and constructive feedback.

Gregg


On 5/16/2012 6:59 PM, Isaac Gouy wrote:

Re: Can Haskell outperform C++?

Gregg Lebovitz — 2012-05-17T12:24:46

Roman,

I think this question is for Richard. I haven't had a chance to play 
with these methods. I will try to do that today.

Gregg

On 5/17/2012 6:07 AM, Roman Werpachowski wrote:

Re: AI - machine learning

Paul Graphov — 2012-05-17T11:36:08

Hi Miro!

I have no useful information for you. Few weeks ago I also checked for
any AI (machine learning first of all) related packages exist and
found nothing satisfactory except for some quite small packages
implementing a single algorithm (like NN-back-propagation). So there
is a lot to do :)

If you are going to do something in this area please let me know, I'll
be glad to collaborate!

p.s. Now I'm taking Machine Learning course at Coursera.org and
looking forward to apply this knowledge with Haskell.

On Tue, May 15, 2012 at 3:02 AM, miro <miroslav.karpis< at >gmail.com> wrote:

Re: Data Kinds and superfluous (in my opinion) constraints contexts

Serguey Zefirov — 2012-05-17T11:18:57

2012/5/17 Iavor Diatchki <iavor.diatchki< at >gmail.com>:

Oh, it was of great matter to me. Because constraints like that get
through type family expressions and make it hard to conceal state that
should satisfy constraints on type family expressions over the type of
the state.

I can write something like that:

data Combinator s a where
    Combinator :: Class (TypeFamExpr s) => ... -> Combinator s a

And I cannot write something like that:
data Combinator a where
    Combinator :: Class (TypeFamExpr s) => .mentions s.. -> Combinator a

If my TypeFamExpr does have type variables, I get a wild type error
messages that mentions partially computed TypeFamExpr as an argument
to constraint.

I can make more detailed example, if you wish.

Re: Can Haskell outperform C++?

Roman Werpachowski — 2012-05-17T10:07:37

Gregg,

what makes Method 2 so much harder than Method 1 to implement in C or C++?

Regards,
RW

Fwd: Can Haskell outperform C++?

Colin Adams — 2012-05-17T07:44:15

Oops. Forget to reply to all.

---------- Forwarded message ----------
From: Colin Adams <colinpauladams< at >gmail.com>
Date: 17 May 2012 08:43
Subject: Re: [Haskell-cafe] Can Haskell outperform C++?
To: Roman Werpachowski <roman.werpachowski< at >gmail.com>

On 17 May 2012 07:12, Roman Werpachowski <roman.werpachowski< at >gmail.com>wrote:

Seconded.
I remember once being asked to examine a certain batch program for
performance improvements. I spotted an obvious inefficiency, and made a
recommendation, which was implemented. It saved something like 10 - 30
minutes on the overnight run (which took hours), so I was disappointed with
the result. But the client was delighted, as the run now fitted into the
batch window.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe< at >haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: Can Haskell outperform C++?

Roman Werpachowski — 2012-05-17T06:12:18


It depends on what you use the code for. If I run an overnight report
for the trading book of my bank in 16 hours, it is
not acceptable and is a disaster. If I run it in 8h, it's OK-ish. In
business settings, you often have strict deadlines and
optimizing the code to be 2x faster can make a huge difference, as you
change from missing the deadline to
meeting a deadline.

Regards,
RW

Re: Can Haskell outperform C++?

Richard O'Keefe — 2012-05-17T05:11:42



No slide deck required.  The task is "generating alternating permutations".

Method 1: generate permutations using a backtracking search;
          when a permutation is generated, check if it is alternating.

Method 2: use the same backtracking search, but only allow extensions
  that preserve the property of being an alternating permutation.

For n=12 the second method is 94 times faster than the first, and the
ratio increases with growing n.  At the time I wrote the program I had not
heard of Bauslaugh and Ruskey's constant-average-time algorithm for generating
alternating permutations.  Experimentally the Method 2 backtracking search
appears to take constant time per solution anyway.

 n (time ms):       En         n!

 1 (    0.0):        1          1      <- method 1
 1 (    0.0):        1                 <- method 2
 2 (    0.0):        1          2
 2 (    0.0):        1
 3 (    0.0):        2          6
 3 (    0.0):        2
 4 (    0.0):        5         24
 4 (    0.0):        5
 5 (    0.0):

Re: Data Kinds and superfluous (in my opinion) constraints contexts

Iavor Diatchki — 2012-05-17T04:19:09

Hello,

The context in your example serves an important purpose: it records the
fact that the behavior of the function may differ depending on which type
it is instantiated with.   This is quite different from ordinary
polymorphic functions, such as `const` for example,  which work in exactly
the same way, no matter how you instantiate them.   Note that it doesn't
matter that we can solve the constraint for all types of kind `D`---the
constraint is there because we can't solve it _uniformly_ for all types.

-Iavor
PS: As an aside, these two forms of polymorphism are sometimes called
"parametric" (when functions work in the same way for all types), and
"ad-hoc" (when the behavior depends on which type is being used).




On Sun, May 6, 2012 at 9:48 AM, Serguey Zefirov <sergueyz< at >gmail.com> wrote:

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe< at >haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Heads up: importing the Cabal issue tracker togithub next week

Bryan O'Sullivan — 2012-05-17T03:45:43

I am planning on doing this early next week, probably in two phases.

As part of the import process, github will generate a *lot* of notification
emails. I'm afraid there is nothing I can do to stem the tide, as github
does not provide a mechanism to suppress these. If you have a github
account, and you have filed bugs against Cabal in Trac, please brace
yourself.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe< at >haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: Can Haskell outperform C++?

Gregg Lebovitz — 2012-05-17T02:04:47

Richard,

Thank you. This is an example of what I had in mind when I talked about 
changing the playing field. Do you have a slide deck for this lecture 
that you would be willing to share with me? I am very interested in 
learning more.

Gregg

On 5/16/2012 9:13 PM, Richard O'Keefe wrote:

Re: Can Haskell outperform C++?

Richard O'Keefe — 2012-05-17T01:13:33

In a lecture today I presented (for quite other reasons) a simple combinatorial enumeration problem where the difference between two algorithms was far larger than any plausible difference between programming languages.  If a programming language makes it easier to explore high level alternative algorithms, you may very easily end up with faster programs in a "slower" language.  (Sorry about the very long line: broken return key.)

Re: Can Haskell outperform C++?

Isaac Gouy — 2012-05-16T22:59:01




"debian coding contest" ?

It's been called many things but, until now, not that.




Tiny tiny toy programs - more or less 100 lines - not quite small enough to be microbenchmarks. Why might that be?

Well, not IO bound. Do people usually mean IO performance when they compare programming languages?

(I guess you must have excluded meteor-contest from your consideration. It's a coding contest and so doesn't specify an algorithm.)




binary-trees - No, it doesn't say that.
thread-ring - No.
chameneos-redux - No.
pidigits - No.
regex-dna - No.
k-nucleotide - No.
mandelbrot - No.
reverse-complement - No.

spectral-norm - "Each program must implement 4 separate functions / procedures / methods like the C# program." (The point being cross function calling so don't amalgamate 4 functions into a single function.)

fasta-redux - No.
fasta - No.
meteor-contest - No.

fannkuch-redux - "defined by programs in Performing Lisp Analysis of the FANNKUCH Benchmark"

n-body - "Each program should model the orbits of Jov