Send Beginners mailing list submissions to beginners@haskell.org To subscribe or unsubscribe via the World Wide Web, visit http://www.haskell.org/mailman/listinfo/beginners or, via email, send a message with subject or body 'help' to beginners-requ...@haskell.org
You can reach the person managing the list at beginners-ow...@haskell.org When replying, please edit your Subject line so it is more specific than "Re: Contents of Beginners digest..." Today's Topics: 1. Improving Performance (Robert Heum?ller) 2. Re: General Hints on Improving Performance - Example DBSCAN (Robert Heum?ller) 3. Re: Improving Performance (Ertugrul S?ylemez) 4. Re: Improving Performance (Robert Heum?ller) 5. Understanding how laziness works (Matt Ford) 6. Re: Improving Performance (Robert Heum?ller) 7. Re: Improving Performance (Ertugrul S?ylemez) 8. Re: Understanding how laziness works (Alexander Batischev) 9. Function application versus function composition performance (Matt Ford) ---------------------------------------------------------------------- Message: 1 Date: Tue, 19 Jun 2012 16:37:57 +0200 From: Robert Heum?ller <mail...@heum.de> Subject: [Haskell-beginners] Improving Performance To: beginners@haskell.org Message-ID: <20120619163757.1c528917@thor> Content-Type: text/plain; charset=US-ASCII Hello, in order to tune my brain to "functional thinking" I've decided to start writing some "real" programs. After having spent a couple of days figuring out how to translate an imperative algorithm into stateless haskell I beleive I've now managed a simple implementation of the DBSCAN clustering algorithm. http://privatepaste.com/e6bb4fb665 This code has several drawbacks (and probably it doesn't work correctly after all) but I would like to tune its performance. Obviously the code calls several functions multiply with the same arguments. Haskell, being stateless should thus always yield the same resuts, correct? In this case performing the same calculations multiply seems pointless. My question: How would you go about improving this code? In any imperative language I would simply cache distances/neighborhoods in a matrix. Obviously this is not what the way to go in haskell? Thank you very much ------------------------------ Message: 2 Date: Tue, 19 Jun 2012 16:45:51 +0200 From: Robert Heum?ller <mail...@heum.de> Subject: Re: [Haskell-beginners] General Hints on Improving Performance - Example DBSCAN To: beginners@haskell.org Message-ID: <20120619164551.5a2a337e@thor> Content-Type: text/plain; charset=US-ASCII I'm sorry the Thread title is not very helpful... I hope this is better > Hello, > > in order to tune my brain to "functional thinking" I've decided to > start writing some "real" programs. After having spent a couple of > days figuring out how to translate an imperative algorithm into > stateless haskell I beleive I've now managed a simple implementation > of the DBSCAN clustering algorithm. > > http://privatepaste.com/e6bb4fb665 > > This code has several drawbacks (and probably it doesn't work > correctly after all) but I would like to tune its performance. > Obviously the code calls several functions multiply with the same > arguments. Haskell, being stateless should thus always yield the same > resuts, correct? In this case performing the same calculations > multiply seems pointless. > > My question: > How would you go about improving this code? > In any imperative language I would simply cache > distances/neighborhoods in a matrix. Obviously this is not what the > way to go in haskell? > > Thank you very much > > _______________________________________________ > Beginners mailing list > Beginners@haskell.org > http://www.haskell.org/mailman/listinfo/beginners ------------------------------ Message: 3 Date: Tue, 19 Jun 2012 17:01:26 +0200 From: Ertugrul S?ylemez <e...@ertes.de> Subject: Re: [Haskell-beginners] Improving Performance To: beginners@haskell.org Message-ID: <20120619170126.5c4b5...@tritium.streitmacht.eu> Content-Type: text/plain; charset="utf-8" Robert Heum?ller <mail...@heum.de> wrote: > in order to tune my brain to "functional thinking" I've decided to > start writing some "real" programs. After having spent a couple of > days figuring out how to translate an imperative algorithm into > stateless haskell I beleive I've now managed a simple implementation > of the DBSCAN clustering algorithm. > > http://privatepaste.com/e6bb4fb665 When asking people to review your code, it would be very helpful to write type signatures for your top-level functions. This alone makes code greatly more readable and also tells a lot about the quality right away. I advice you to get used to writing type signatures for yourself as well. Greets, Ertugrul -- Not to be or to be and (not to be or to be and (not to be or to be and (not to be or to be and ... that is the list monad. -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 836 bytes Desc: not available URL: <http://www.haskell.org/pipermail/beginners/attachments/20120619/dae1a369/attachment-0001.pgp> ------------------------------ Message: 4 Date: Tue, 19 Jun 2012 17:42:48 +0200 From: Robert Heum?ller <mail...@heum.de> Subject: Re: [Haskell-beginners] Improving Performance To: beginners@haskell.org Message-ID: <20120619174248.2cae37ee@thor> Content-Type: text/plain; charset=ISO-8859-1 That's a great start, thanks ;) Am Tue, 19 Jun 2012 17:01:26 +0200 schrieb Ertugrul S?ylemez <e...@ertes.de>: > Robert Heum?ller <mail...@heum.de> wrote: > > > in order to tune my brain to "functional thinking" I've decided to > > start writing some "real" programs. After having spent a couple of > > days figuring out how to translate an imperative algorithm into > > stateless haskell I beleive I've now managed a simple implementation > > of the DBSCAN clustering algorithm. > > > > http://privatepaste.com/e6bb4fb665 > > When asking people to review your code, it would be very helpful to > write type signatures for your top-level functions. This alone makes > code greatly more readable and also tells a lot about the quality > right away. I advice you to get used to writing type signatures for > yourself as well. > > > Greets, > Ertugrul > ------------------------------ Message: 5 Date: Tue, 19 Jun 2012 17:20:15 +0100 From: Matt Ford <m...@dancingfrog.co.uk> Subject: [Haskell-beginners] Understanding how laziness works To: beginners@haskell.org Message-ID: <ca+fwtn9sd9fqhx4q5wsqbbkq9fgwt9ymx3fomsydvv2qjxh...@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1 Apologies for the maybe double post (no subject and hadn't confirmed the mailing list first time I sent this). Hi, Here's a simple expression double ( double [1,2,3,4] ) !! 0 The 1st element of a list is double ( 1*2 : double [2,3,4] ) !! 0 1*2*2 : double ( double [2,3,4 ] ) !! 0 1*2*2 4 calculated without having to traverse the rest of the list due to laziness. But how far does the laziness extend? For example, if I take the 2nd element double (double [1,2,3,4]) !! 1 Do we have 1*2*2 : double ( 2*2 : double [3,4] ) !! 1 1*2*2 : 2*2*2 : double ( double [3,4] ) !! 1 2*2*2 8 Resulting in 8. I assume that the 1st list entry 1*2*2 doesn't actually get calculated, but the expression does get formed? The second element (index 1) gets formed, isolated (by !!) and calculated as the return value. And then things can happily stop. What I'm checking is that the laziness doesn't some how magically extend to not having to form the preceding expressions that make up the resulting list? Or can Haskell recognize that this is like doing function composition i.e., (double . double) [ 1 2, 3, 4 ] !! 1 Thanks for any answer. Cheers, Matt. p.s, I kinda hope things are how I've assumed as the example finally shows me some concrete benefit of function composition which has never seemed important given it's so easily re-written as application. ------------------------------ Message: 6 Date: Tue, 19 Jun 2012 21:44:10 +0200 From: Robert Heum?ller <mail...@heum.de> Subject: Re: [Haskell-beginners] Improving Performance To: beginners@haskell.org Message-ID: <20120619214410.35dc28a2@thor> Content-Type: text/plain; charset="iso-8859-1" Hi again, I've added the type signatures. What's next? http://privatepaste.com/26073e4b0e Thanks Am Tue, 19 Jun 2012 17:01:26 +0200 schrieb Ertugrul S?ylemez <e...@ertes.de>: > Robert Heum?ller <mail...@heum.de> wrote: > > > in order to tune my brain to "functional thinking" I've decided to > > start writing some "real" programs. After having spent a couple of > > days figuring out how to translate an imperative algorithm into > > stateless haskell I beleive I've now managed a simple implementation > > of the DBSCAN clustering algorithm. > > > > http://privatepaste.com/e6bb4fb665 > > When asking people to review your code, it would be very helpful to > write type signatures for your top-level functions. This alone makes > code greatly more readable and also tells a lot about the quality > right away. I advice you to get used to writing type signatures for > yourself as well. > > > Greets, > Ertugrul > -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 490 bytes Desc: not available URL: <http://www.haskell.org/pipermail/beginners/attachments/20120619/a26caa00/attachment-0001.pgp> ------------------------------ Message: 7 Date: Tue, 19 Jun 2012 22:25:05 +0200 From: Ertugrul S?ylemez <e...@ertes.de> Subject: Re: [Haskell-beginners] Improving Performance To: beginners@haskell.org Message-ID: <20120619222505.656c5...@tritium.streitmacht.eu> Content-Type: text/plain; charset="utf-8" Robert Heum?ller <mail...@heum.de> wrote: > I've added the type signatures. What's next? > > http://privatepaste.com/26073e4b0e Great, now that makes it much easier to reason about performance. A quick look at the type signatures tells me that your next step is to use the right tool for the job. In Haskell this basically means to use the right data and control structures. First of all know when not to use lists. A good intuition is to ask yourself whether the lists will actually live in memory. If no, then lists are fine. If yes (like in your case), examine your usage. If you use them like stacks (working on the head only) that's probably fine (it's not in your case). However, if you fold and unfold a lot or index individual elements you probably want a different data structure like a vector or a map. This is a somewhat involved topic and needs a lot of training, but making the right decision here will give you the main performance boost. Note: Whatever you do, stay in pure land. Always use immutable data structures. If your code is too slow, you may be using the right data structure the wrong way. Going mutable is almost always the wrong way. Again: It takes some training, especially in Haskell where (as a beginner) you may not see directly what is actually happening. Also find spots where sharing can be used. Unshared example: f x' + f x' Shared version: let x = f x' in x + x Haskell compilers don't do that automatically for you, because sharing trades memory for run-time performance, and the outcome is hard to predict for a compiler. I suggest experimenting. Greets, Ertugrul -- Not to be or to be and (not to be or to be and (not to be or to be and (not to be or to be and ... that is the list monad. -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 836 bytes Desc: not available URL: <http://www.haskell.org/pipermail/beginners/attachments/20120619/cff0a484/attachment-0001.pgp> ------------------------------ Message: 8 Date: Wed, 20 Jun 2012 00:55:04 +0400 From: Alexander Batischev <eual...@gmail.com> Subject: Re: [Haskell-beginners] Understanding how laziness works To: beginners@haskell.org Message-ID: <20120619205504.GB8505@antaeus> Content-Type: text/plain; charset="us-ascii" Hello! On Tue, Jun 19, 2012 at 05:20:15PM +0100, Matt Ford wrote: > I assume that the 1st list entry 1*2*2 doesn't actually get > calculated, but the expression does get formed? The second element > (index 1) gets formed, isolated (by !!) and calculated as the return > value. And then > things can happily stop. You're right. The spine of the list is being formed, but it doesn't necessarily evaluate values in the cells of the list. Basically, you can imagine some linked list where each cell have two pointers: one pointing to the next element (or thunk) and another pointing to the value (or thunk) of that cell. When you ask for some element of the list, linked list is being built up to the element you asked for, but only that thunks that are "next elements" are being evaluated - values that aren't used stay being thunks. Now, in your particular example you have constant index and constant list, so I'm pretty sure any Haskell compiler would simply execute the code and put the result into program. But that's only an expectation, not knowledge, so please be critical about it. -- Regards, Alexander Batischev PGP key 356961A20C8BFD03 Fingerprint: CE6C 4307 9348 58E3 FD94 A00F 3569 61A2 0C8B FD03 -------------- next part -------------- A non-text attachment was scrubbed... Name: not available Type: application/pgp-signature Size: 836 bytes Desc: Digital signature URL: <http://www.haskell.org/pipermail/beginners/attachments/20120620/2fa85209/attachment-0001.pgp> ------------------------------ Message: 9 Date: Tue, 19 Jun 2012 23:01:32 +0100 From: Matt Ford <m...@dancingfrog.co.uk> Subject: [Haskell-beginners] Function application versus function composition performance To: beginners@haskell.org Message-ID: <CA+FwTn_cXy=7zsjsas2rx6nzzbgwur7kpokwmklqmmmvwx7...@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1 Hi All, My last question got me thinking (always dangerous): an expression that doubles a list and takes the 2nd element (index 1), I assume, goes through the following steps. double (double [1,2,3,4]) !! 1 double ( 1*2 : double [2,3,4]) !! 1 1*2*2 : double ( double [2,3,4] ) !! 1 1*2*2 : double ( 2*2 : double [3,4] ) !! 1 1*2*2 : 2*2*2 : double ( double [3,4] ) !! 1 2*2*2 8 Up until the element requested all the proceeding elements have to have the expression formed as Haskell process the calculation. Now, I want to compare this to using function composition ( double . double ) [ 1 ,2, 3, 4 ] !! 1 This is the bit I'm unsure of - what does the composition look like. It is easy to see that it could be simplified to something like: ( double . double) (x:xs) = x*4 : (double . double) xs This would mean the steps could be written (double . double) [ 1,2,3,4 ] !! 1 (1*4 : (double.double) [2,3,4]) !! 1 (1*4 : 2*4 : (double.double) [ 3,4 ]) !! 1 2*4 8 Ignoring the start and end steps, it will be half the number of steps compared to the application version. Significant then, over long lists. So is this true, are composite functions simplified in Haskell in general so that they may have improved performance over function application? I've seen posts on the internet that say it's a matter of style only: http://stackoverflow.com/questions/3030675/haskell-function-composition-and-function-application-idioms-correct-us. But my reasoning suggests it could be more than that. Perhaps, function application is similarly optimised - maybe by replacing all functions applications with composition and then simplifying? Or maybe the simplifying/optimisation step never happens? As you can see I'm just guessing at things :-) But it's nice to wonder. Many thanks for any pointers, Matt. ------------------------------ _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners End of Beginners Digest, Vol 48, Issue 24 *****************************************