May 2012 - Haskell-Cafe

Data Kinds and superfluous (in my opinion) constraints contexts
by Serguey Zefirov 17 May '12

17 May '12

I decided to take a look at DataKinds extension, which became available in GHC 7.4. My main concerns is that I cannot close type classes for promoted data types. Even if I fix type class argument to a promoted type, the use of encoding function still requires specification of context. I consider this an omission of potentially very useful feature. Example is below. ----------------------------------------------------------------------------------------- {-# LANGUAGE TypeOperators, DataKinds, TemplateHaskell, TypeFamilies, UndecidableInstances #-} {-# LANGUAGE GADTs #-} -- a binary numbers. infixl 5 :* data D = D0 | D1 | D :* D deriving Show -- encoding for them. data EncD :: D -> * where EncD0 :: EncD D0 EncD1 :: EncD D1 EncDStar :: EncD (a :: D) -> EncD (b :: D) -> EncD (a :* b) -- decode of values. fromD :: D -> Int fromD D0 = 0 fromD D1 = 1 fromD (d :* d0) = fromD d * 2 + fromD d0 -- decode of encoded values. fromEncD :: EncD d -> Int fromEncD EncD0 = 0 fromEncD EncD1 = 1 fromEncD (EncDStar a b) = fromEncD a * 2 + fromEncD b -- constructing encoded values from type. -- I've closed possible kinds for class parameter (and GHC successfully compiles it). -- I fully expect an error if I will try to apply mkD to some type that is not D. -- (and, actually, GHC goes great lengths to prevent me from doing that) -- By extension of argument I expect GHC to stop requiring context with MkD a where -- I use mkD "constant function" and it is proven that a :: D. class MkD (a :: D) where mkD :: EncD a instance MkD D0 where mkD = EncD0 instance MkD D1 where mkD = EncD1 -- But I cannot omit context here... instance (MkD a, MkD b) => MkD (a :* b) where mkD = EncDStar mkD mkD data BV (size :: D) where BV :: EncD size -> Integer -> BV size bvSize :: BV (size :: D) -> Int bvSize (BV size _) = fromEncD size -- ...and here. -- This is bad, because this context will arise in other places, some of which -- are autogenerated and context for them is incomprehensible to human -- reader. -- (they are autogenerated precisely because of that - it is tedious and error prone -- to satisfy type checker.) fromIntgr :: Integer -> BV (size :: D) -- doesn't work, but desired. -- fromIntgr :: MkD size => Integer -> BV (size :: D) -- does work, but is not that useful. fromIntgr int = BV mkD int -----------------------------------------------------------------------------------------

4 5

Fwd: Can Haskell outperform C++?
by Colin Adams 17 May '12

17 May '12

Oops. Forget to reply to all. ---------- Forwarded message ---------- From: Colin Adams <colinpauladams(a)gmail.com> Date: 17 May 2012 08:43 Subject: Re: [Haskell-cafe] Can Haskell outperform C++? To: Roman Werpachowski <roman.werpachowski(a)gmail.com> On 17 May 2012 07:12, Roman Werpachowski <roman.werpachowski(a)gmail.com>wrote: > > 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. > > 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.

1 0

Re: [Haskell-cafe] Can Haskell outperform C++?
by Roman Werpachowski 17 May '12

17 May '12

> Date: Wed, 16 May 2012 06:54:08 -0400 > From: wren ng thornton <wren(a)freegeek.org> > Subject: Re: [Haskell-cafe] Can Haskell outperform C++? > To: haskell-cafe(a)haskell.org > Message-ID: <4FB38750.9060009(a)freegeek.org> > Content-Type: text/plain; charset=ISO-8859-1; format=flowed > But on the other hand, there are quite a lot of people who focus > excessively on "optimization" when the actual differences for the code > they're writing are either negligible (e.g., because of I/O bottlenecks) > or uninteresting (e.g., a 2x slowdown is a nuisance rather than a > crisis). 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

1 0

Re: [Haskell-cafe] Can Haskell outperform C++?
by Richard O'Keefe 17 May '12

17 May '12

On 17/05/2012, at 2:04 PM, Gregg Lebovitz wrote: > 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. 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): 16 120 5 ( 0.0): 16 6 ( 0.1): 61 720 6 ( 0.0): 61 7 ( 0.6): 272 5040 7 ( 0.1): 272 8 ( 4.4): 1385 40320 8 ( 0.3): 1385 9 ( 35.2): 7936 362880 9 ( 1.4): 7936 10 ( 359.7): 50521 3628800 10 ( 9.3): 50521 11 ( 4035.7): 353792 39916800 11 ( 67.0): 353792 12 (49584.6): 2702765 479001600 <- method 1 12 ( 528.1): 2702765 <- method 2 Those times are in C; SWI Prolog (which compiles to an abstract instruction set that is then interpreted by portable C) was about 24 times slower. A factor of 94 comfortably exceeds a factor of 24...

1 0

Haskell Weekly News: Issue 227
by Daniel Santa Cruz 17 May '12

17 May '12

Welcome to issue 227 of the HWN, an issue covering crowd-sourced bits of information about Haskell from around the web. This issue covers the week of May 6 to 12, 2012. Announcements Doaitse Swierstra reminded us about the Summer School on Applied Functional Programming, at Utrech University. Hurry to check it out, as the deadline for registration is May 20th! [1] http://goo.gl/TZYdd Janis Voigtlander announced the release of the 22nd edition of the Haskell Communities and Activities Report. [2] http://goo.gl/pXIZn Quotes of the Week * dcoutts: (on #darcs): "[on github:] it's like the facebook of source repos" * dmwit: "Functional programming" is a technical term that means more than just what the two words mean separately. * Axman6: "GHC Warning: Did you see that in an OOP textbook? You probably don't want to be doing that" * StevenKaas: Haskell's Wager: what if infinite lists can suffer infinitely even when lazily evaluated? * quicksilver: "Patent covering a device for emitting greetings to the world community as a whole in computer-readable format" (US Patent no 1787528391) Top Reddit Stories * Videos to the functional programming course I attend are freely available. I thought you might enjoy them. Domain: self.haskell, Score: 47, Comments: 10 On Reddit: [3] http://goo.gl/SoV7x Original: [4] http://goo.gl/SoV7x * red-black trees in haskell, using GADTs, existential types, and zippers, oh my Domain: gist.github.com, Score: 40, Comments: 21 On Reddit: [5] http://goo.gl/Ae08L Original: [6] http://goo.gl/iDxjY * Equality proofs and deferred type errors, A compiler pearl [Vytiniotis, Peyton Jones,Magalhaes PDF] Domain: research.microsoft.com, Score: 40, Comments: 17 On Reddit: [7] http://goo.gl/6OUbX Original: [8] http://goo.gl/OP6ep * LLVM now supports NVIDIA GPU's Domain: nvidianews.nvidia.com, Score: 36, Comments: 19 On Reddit: [9] http://goo.gl/DF7sY Original: [10] http://goo.gl/rvYdL * The Architecture of Open Source Applications, Volume II (with chapters on GHC and Yesod, royalties go to Amnesty International) Domain: lulu.com, Score: 35, Comments: 9 On Reddit: [11] http://goo.gl/XfsXB Original: [12] http://goo.gl/1sr6u * Jesper's Blog: My Take on Haskell vs Scala Domain: jnordenberg.blogspot.com, Score: 29, Comments: 8 On Reddit: [13] http://goo.gl/3EM45 Original: [14] http://goo.gl/aWGgn * Haskell Communities and Activities Report --- May 2012 Domain: haskell.org, Score: 27, Comments: 3 On Reddit: [15] http://goo.gl/q8XFZ Original: [16] http://goo.gl/fW3Sf * Keter: Web App Deployment Domain: yesodweb.com, Score: 23, Comments: 19 On Reddit: [17] http://goo.gl/VOSVF Original: [18] http://goo.gl/OJ783 * A small and simple tip for Google Code Jam-mers Domain: self.haskell, Score: 22, Comments: 15 On Reddit: [19] http://goo.gl/9QPDW Original: [20] http://goo.gl/9QPDW * Composable Value Editors for GTK Domain: twdkz.wordpress.com, Score: 21, Comments: On Reddit: [21] http://goo.gl/w4WoR Original: [22] http://goo.gl/LevtB * The Brittleness of Type Hierarchies (codegrunt.co.uk) and a Haskell approach Domain: self.haskell, Score: 16, Comments: 17 On Reddit: [23] http://goo.gl/w4m8o Original: [24] http://goo.gl/w4m8o Top StackOverflow Questions * Static types, polymorphism and specialization votes: 18, answers: 3 Read on SO: [25] http://goo.gl/wxDZt * Redoing the standard classes [closed] votes: 12, answers: 2 Read on SO: [26] http://goo.gl/22MCG * Using Cont to acquire values from the future and the past votes: 11, answers: 1 Read on SO: [27] http://goo.gl/1zSVo * Why is `($ 4) (> 3)` equivalent to `4 > 3`? votes: 9, answers: 3 Read on SO: [28] http://goo.gl/5oTei * Recursively defined instances and constraints votes: 9, answers: 1 Read on SO: [29] http://goo.gl/uliWA * Freeing memory allocated with newCString votes: 8, answers: 1 Read on SO: [30] http://goo.gl/k3Izw * What is the meaning of “quasi” in quasiquotations? votes: 8, answers: 5 Read on SO: [31] http://goo.gl/YjPbl * Ensuring files are closed promptly votes: 7, answers: 3 Read on SO: [32] http://goo.gl/UCKSB * Is there ever a good reason to use unsafePerformIO? votes: 7, answers: 5 Read on SO: [33] http://goo.gl/y2meC * What characters are permitted for haskell operators? votes: 7, answers: 3 Read on SO: [34] http://goo.gl/0n1kX * Defining an algebra module using constructive-algebra package votes: 6, answers: 2 Read on SO: [35] http://goo.gl/vqIcG * Haskell: Type safety with logically different Boolean values votes: 6, answers: 3 Read on SO: [36] http://goo.gl/f1Gtz * Data structure to represent automata votes: 5, answers: 2 Read on SO: [37] http://goo.gl/MhsvC Until next time, Daniel Santa Cruz References 1. http://permalink.gmane.org/gmane.comp.lang.haskell.cafe/98235 2. http://permalink.gmane.org/gmane.comp.lang.haskell.general/19294 3. http://www.reddit.com/r/haskell/comments/tgz57/videos_to_the_functional_pro… 4. http://www.reddit.com/r/haskell/comments/tgz57/videos_to_the_functional_pro… 5. https://gist.github.com/2659812 6. http://www.reddit.com/r/haskell/comments/ti5il/redblack_trees_in_haskell_us… 7. http://research.microsoft.com/en-us/um/people/simonpj/papers/ext-f/icfp12.p… 8. http://www.reddit.com/r/haskell/comments/tjnzj/equality_proofs_and_deferred… 9. http://nvidianews.nvidia.com/Releases/NVIDIA-Contributes-CUDA-Compiler-to-O… 10. http://www.reddit.com/r/haskell/comments/tgdia/llvm_now_supports_nvidia_gpu… 11. http://www.lulu.com/shop/amy-brown-and-greg-wilson/the-architecture-of-open… 12. http://www.reddit.com/r/haskell/comments/teqai/the_architecture_of_open_sou… 13. http://jnordenberg.blogspot.com/2012/05/my-take-on-haskell-vs-scala.html 14. http://www.reddit.com/r/haskell/comments/tedrh/jespers_blog_my_take_on_hask… 15. http://www.haskell.org/communities/05-2012/html/report.html 16. http://www.reddit.com/r/haskell/comments/tivjx/haskell_communities_and_acti… 17. http://www.yesodweb.com/blog/2012/05/keter-app-deployment 18. http://www.reddit.com/r/haskell/comments/thygx/keter_web_app_deployment/ 19. http://www.reddit.com/r/haskell/comments/ta5lx/a_small_and_simple_tip_for_g… 20. http://www.reddit.com/r/haskell/comments/ta5lx/a_small_and_simple_tip_for_g… 21. http://twdkz.wordpress.com/2012/05/10/composable-value-editors/ 22. http://www.reddit.com/r/haskell/comments/tg58a/composable_value_editors_for… 23. http://www.reddit.com/r/haskell/comments/tdmt5/the_brittleness_of_type_hier… 24. http://www.reddit.com/r/haskell/comments/tdmt5/the_brittleness_of_type_hier… 25. http://stackoverflow.com/questions/10534744/static-types-polymorphism-and-s… 26. http://stackoverflow.com/questions/10500320/redoing-the-standard-classes 27. http://stackoverflow.com/questions/10560124/using-cont-to-acquire-values-fr… 28. http://stackoverflow.com/questions/10476883/why-is-4-3-equivalent-to-4-3 29. http://stackoverflow.com/questions/10529360/recursively-defined-instances-a… 30. http://stackoverflow.com/questions/10513007/freeing-memory-allocated-with-n… 31. http://stackoverflow.com/questions/10556631/what-is-the-meaning-of-quasi-in… 32. http://stackoverflow.com/questions/10518049/ensuring-files-are-closed-promp… 33. http://stackoverflow.com/questions/10529284/is-there-ever-a-good-reason-to-… 34. http://stackoverflow.com/questions/10548170/what-characters-are-permitted-f… 35. http://stackoverflow.com/questions/10536990/defining-an-algebra-module-usin… 36. http://stackoverflow.com/questions/10544984/haskell-type-safety-with-logica… 37. http://stackoverflow.com/questions/10516603/data-structure-to-represent-aut…

1 0

Haskell Symposium 2012 - deadline approaching
by Janis Voigtländer 16 May '12

16 May '12

[Deadline for submission of abstracts is in two weeks. The submission page is open, earlier submissions welcome.] ======================================================================== "Haskell 2012" ACM SIGPLAN Haskell Symposium 2012 Copenhagen, Denmark 13th September, 2012 (directly after ICFP) CALL FOR PAPERS http://www.haskell.org/haskell-symposium/2012/ ======================================================================== The ACM SIGPLAN Haskell Symposium 2012 will be co-located with the 2012 International Conference on Functional Programming (ICFP), in Copenhagen, Denmark. The purpose of the Haskell Symposium is to discuss experiences with Haskell and future developments for the language. Topics of interest include, but are not limited to: * Language Design, with a focus on possible extensions and modifications of Haskell as well as critical discussions of the status quo; * Theory, such as formal treatments of the semantics of the present language or future extensions, type systems, and foundations for program analysis and transformation; * Implementations, including program analysis and transformation, static and dynamic compilation for sequential, parallel, and distributed architectures, memory management as well as foreign function and component interfaces; * Tools, in the form of profilers, tracers, debuggers, pre-processors, testing tools, and suchlike; * Applications, using Haskell for scientific and symbolic computing, database, multimedia, telecom and web applications, and so forth; * Functional Pearls, being elegant, instructive examples of using Haskell; * Experience Reports, general practice and experience with Haskell, e.g., in an education or industry context. Papers in the latter three categories need not necessarily report original research results; they may instead, for example, report practical experience that will be useful to others, reusable programming idioms, or elegant new ways of approaching a problem. (Links with more advice appear on the symposium web page.) The key criterion for such a paper is that it makes a contribution from which other Haskellers can benefit. It is not enough simply to describe a program! Regular papers should explain their research contributions in both general and technical terms, identifying what has been accomplished, explaining why it is significant, and relating it to previous work (also for other languages where appropriate). In addition, we solicit proposals for system demonstrations, based on running (perhaps prototype) software rather than necessarily on novel research results. Such short demo proposals should explain why a demonstration would be of interest to the Haskell community. Travel Support: =============== Student attendees with accepted papers can apply for a SIGPLAN PAC grant to help cover travel expenses. PAC also offers other support, such as for child-care expenses during the meeting or for travel costs for companions of SIGPLAN members with physical disabilities, as well as for travel from locations outside of North America and Europe. For details on the PAC programme, see its web page (http://www.sigplan.org/PAC.htm) Proceedings: ============ There will be formal proceedings published by ACM Press. In addition to printed proceedings, accepted papers will be included in the ACM Digital Library. Authors must transfer copyright to ACM upon acceptance (for government work, to the extent transferable), but retain various rights (http://www.acm.org/publications/policies/copyright_policy) Authors are encouraged to publish auxiliary material with their paper (source code, test data, etc.); they retain copyright of auxiliary material. Accepted demo proposals, assessed for relevance by the PC, will be published on the symposium web page, but not formally published in the proceedings. Submission Details: =================== * Abstract Submission: Thu 31st May 2012 * Paper Submission : Sat 2nd June 2012, anywhere on earth * Author Notification: Wed 27th June 2012 * Final Papers Due : Tue 10th July 2012 Submitted papers should be in portable document format (PDF), formatted using the ACM SIGPLAN style guidelines (9pt format, more details appear on the symposium web page). The length is restricted to 12 pages, except for "Experience Report" papers, which are restricted to 6 pages. Each paper submission must adhere to SIGPLAN's republication policy, as explained on the web. Demo proposals are limited to 2-page abstracts, in the same format. "Functional Pearls", "Experience Reports", and "Demo Proposals" should be marked as such with those words in the title at time of submission. The paper submission deadline and length limitations are firm. There will be no extensions, and papers violating the length limitations will be summarily rejected. Submission is via EasyChair: https://www.easychair.org/conferences/?conf=haskell2012 Programme Committee: ==================== * Amal Ahmed, Northeastern University * Jost Berthold, University of Copenhagen * Nils Anders Danielsson, University of Gothenburg * Iavor Diatchki, Galois Inc. * Jeremy Gibbons, University of Oxford * Jurriaan Hage, Utrecht University * Zhenjiang Hu, National Institute of Informatics Tokyo * Daan Leijen, Microsoft Research * Ben Lippmeier, University of New South Wales * Simon Peyton Jones, Microsoft Research * Colin Runciman, University of York * Eijiro Sumii, Tohoku University * Janis Voigtländer (chair), University of Bonn * Brent Yorgey, University of Pennsylvania Links: ====== * http://www.haskell.org/haskell-symposium (the permanent web page of the Haskell Symposium) * http://www.haskell.org/haskell-symposium/2012 (the 2012 Haskell Symposium web page) * http://www.icfpconference.org/icfp2012 (the ICFP 2012 web page)

1 0

import IO
by A Smith 16 May '12

16 May '12

Hi folks I need a little help. I had a hiccup upgrading my Ubuntu system, and eventually did a fresh install. Its mostly fixed to my old favourite ways but I cannot remember what's needed to install the stuff that the "import IO" statement uses! -- Andrew

2 1

ANN: variable-precision floating point
by Claude Heiland-Allen 16 May '12

16 May '12

Hi all, I'm pleased to announce variable-precision-0.2: http://hackage.haskell.org/package/variable-precision There was no announcement for previous versions, as I quickly found their flaws to be too irritating in practice. --8<-- excerpt from the hackage page Software floating point with type-tagged variable mantissa precision, implemented using a strict pair of Integer and Int scaled alike to decodeFloat. Instances of the usual numeric type classes are provided, along with additional operators (with carefully chosen fixities) to coerce, adjust and reify precisions. --8<-- end excerpt Known shortcomings of this release: * no implementation of (inverse) (hyperbolic) trigonometric functions * no support for negative zero * no support for rounding modes * accuracy has not been extensively verified * termination of algorithms has not been proven The intention of this package is to be simple yet useable in the meantime until there is a version of hmpfr[1] or fixed-precision[2] that work without requiring a custom-compiled GHC. The design of variable-precision was inspired by the latter, and variable-precision is probably inferior, but the lifetime of the variable-precision package is hopefully going to be short. [1] http://hackage.haskell.org/package/hmpfr [2] http://hackage.haskell.org/package/fixed-precision I'm currently mainly using variable-precision for exploring the Mandelbrot Set, particularly in algorithms using Newton's method (for example, tracing external rays, where more precision is needed the closer you get to the boundary of the set). Thanks, Claude PS: --8<-- excerpt from ghci session Prelude Numeric.VariablePrecision> (pi :: F24) .@$ 200 $ show . (pi -) "1.5815072737072126433832795028841971693993751058209749096292229e-6" Prelude Numeric.VariablePrecision> (pi :: F53) .@$ 200 $ show . (pi -) "4.1192675685652988632476805983544532308209749096292228904414057e-15" Prelude Numeric.VariablePrecision> (2 :: F53) .@$ 200 $ show . log "0.69314718055994530941723212145817656807550013436025525413214402" Prelude Numeric.VariablePrecision> log 2 0.6931471805599453 Prelude Numeric.VariablePrecision> (2 :: F53) .@$ 200 $ show . exp "7.3890560989306502272304274605750078131803155705518473240869941" Prelude Numeric.VariablePrecision> exp 2 7.38905609893065 --8<-- end excerpt

1 0

Can't prevent memoizing in simple code
by Yves Parès 16 May '12

16 May '12

The buffer http://hpaste.org/68595 presents a simple code I tried to profile. I spotted what I strongly think to be an abusive memoization. The problem is that I don't see how to (simply) get rid of it. Compiled with -O2, it consumes 130MB of memory, however lines A and B executed separately consume each only 1MB. The infinite list (l 1), whatever I do, keeps being shared between lines A and B. I tried to wrap it in a function, as you can see, I also tried to make it explicitely polymorphic (bypassing monomorphic restriction), nothing solves it, GHC is just to good at memoizing. NB: When compiled without optimisations, the sharing does not happen (side note: but then lack of strictness analysis -- which is what I was testing at the first place -- makes line A (call to suminit2) consume a lot of memory, but this is normal).

2 2

Call for AusHac 2012
by Ivan Lazar Miljenovic 16 May '12

16 May '12

For any Australian Haskellers (or indeed anyone that feels willing to come from wherever you may hail) who have _not_ yet received an email, seen it on Reddit or Google+ but is interested in attending AusHac 2012, we are currently trying to determine which weekend in July best suits everyone. So if you're interested in coming, please fill out the form at http://tinyurl.com/AusHac2012PreferredDates This year we're going to hold AusHac in central Sydney (thanks to Atlassian putting their offices at our disposal!) rather than UNSW, which should make transport and accommodation easier for people. AusHac is open to anyone interested in Haskell, from a complete newbie to one of the Simons. We don't have any specific themes or projects to work on; instead just come along and hack on whatever takes your fancy. -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com http://IvanMiljenovic.wordpress.com

1 0