July 2011 - Haskell-Cafe

Binding of an integer variable
by Paul Reiners 28 Jul '11

28 Jul '11

I have a question about the following GHCi interaction: Prelude> let x = 23 Prelude> :show bindings x :: Integer = _ What is the meaning of the underscore in the third line? Why doesn't it say this, instead? x :: Integer = 23

6 7

ANN: syntactic-0.5
by Emil Axelsson 28 Jul '11

28 Jul '11

I've just uploaded a new version of syntactic: http://hackage.haskell.org/package/syntactic The most important change is that I've added observable sharing based on StableNames. The implementation and interface are conceptually quite similar to Andy Gill's data-reify. The library offers both referentially transparent common sub-expression elimination (that uses a combination of hashing and observable sharing under the hood), as well as direct observation of sharing. The difference between the two flavors is demonstrated in the accompanied file: Examples/NanoFeldspar/Test.hs (See test7_X.) Still missing a way to rebuild an expression with let bindings from the syntax graphs. This is ongoing work. / Emil

1 0

Haskell Weekly News: Issue 192
by Daniel Santa Cruz 27 Jul '11

27 Jul '11

Welcome to issue 192 of the HWN, a newsletter covering developments in the Haskell community. This release covers the week of July 17 to 23, 2011. [1] http://goo.gl/8hDku You can find an HTML rendition of this issue at: http://contemplatecode.blogspot.com/2011/07/haskell-weekly-news-issue-192.h… Announcements Nicolas Wu announced the 4th edition of the Haskell Parallel Digest. The digest is made possible by the Parallel GHC Project. [2] http://goo.gl/lm5T1 Quotes of the Week * copumpkin: perhaps I should stop eating people I've never met * Saizan: agda is webscale in the sense that you need half of The Cloud to run the typechecker * kmc: my algorithm is O(1), but the constant factor grows quadratically as the problem size increases * cmccann: C++ is dual to Haskell in a sense: it's much too hard for the average programmer to use safely, but they do anyway with disastrous results; whereas Haskell isn't actually that difficult to use but people don't even try Top Reddit Stories * What Haskell Doesn't Have Domain: elaforge.blogspot.com, Score: 73, Comments: 58 On Reddit: [3] http://goo.gl/17UDu Original: [4] http://goo.gl/u4Ozy * Take the State of Haskell 2011 Survey Domain: blog.johantibell.com, Score: 55, Comments: 0 On Reddit: [5] http://goo.gl/Q7iip Original: [6] http://goo.gl/jq1Je * Economic Interpreter for Haskell Domain: pnyf.inf.elte.hu, Score: 40, Comments: 5 On Reddit: [7] http://goo.gl/BmBqf Original: [8] http://goo.gl/92mfS * Haskell on Heroku Domain: yesodweb.com, Score: 38, Comments: 5 On Reddit: [9] http://goo.gl/LYHZY Original: [10] http://goo.gl/Ly4n7 * Haskell Stickers! Domain: redbubble.com, Score: 33, Comments: 7 On Reddit: [11] http://goo.gl/WVXoH Original: [12] http://goo.gl/RpQ0f * Rewritten Agda introduction Domain: pnyf.inf.elte.hu, Score: 31, Comments: 34 On Reddit: [13] http://goo.gl/gz6TJ Original: [14] http://goo.gl/oTg5J * A plugin for GHC to turn Haskell into a strict language Domain: github.com, Score: 28, Comments: 18 On Reddit: [15] http://goo.gl/BK4os * What is the state of HackageDB 2.0? Domain: hackage.haskell.org, Score: 26, Comments: 8 On Reddit: [16] http://goo.gl/nrMTc Original: [17] http://goo.gl/tui2x * wxHaskell: The road to the Haskell Platform? Domain: sourceforge.net, Score: 26, Comments: 33 On Reddit: [18] http://goo.gl/vqfPC Original: [19] http://goo.gl/KNa16 * Just do It: Simple Monadic Equational Reasoning [pdf] Domain: cs.ox.ac.uk, Score: 24, Comments: 2 On Reddit: [20] http://goo.gl/GG0cs Original: [21] http://goo.gl/7MHGw * Cabal-dev 0.8 is out with improvements to: flag parsing, user cabal settings, cabal-dev ghci and more! Domain: github.com, Score: 24, Comments: 15 On Reddit: [22] http://goo.gl/YO6Q6 * Functors, applicative functors, monads – their relationship by example Domain: heh.fi, Score: 23, Comments: 0 On Reddit: [23] http://goo.gl/bkJ4Y Original: [24] http://goo.gl/bf6zo * Snap 0.5.2 released Domain: snapframework.com, Score: 23, Comments: 0 On Reddit: [25] http://goo.gl/0RCh3 Original: [26] http://goo.gl/jeFU5 Top StackOverflow Questions * Help in understanding pointfree code votes: 14, answers: 1 Read on SO: [27] http://goo.gl/Ryy5c * How can I combine Handles in Haskell? votes: 12, answers: 2 Read on SO: [28] http://goo.gl/25W4E * Current state of integrating unit tests with Haskell's Cabal? votes: 9, answers: 1 Read on SO: [29] http://goo.gl/nm8Zc * Does iteratee I/O make sense in non-functional languages? votes: 9, answers: 2 Read on SO: [30] http://goo.gl/f8YhP * Literate Haskell: References And Indexing votes: 8, answers: 1 Read on SO: [31] http://goo.gl/QYPBK * Call C Functions from Haskell at runtime votes: 7, answers: 1 Read on SO: [32] http://goo.gl/oj0R7 * Type-class instances for types with 2 parameters when the type-class has only one votes: 7, answers: 2 Read on SO: [33] http://goo.gl/JmxBr * List of options: equivalent of sequence in Scala? votes: 7, answers: 4 Read on SO: [34] http://goo.gl/MnZg8 * Is it necessary to specify every superclass in a class context of a class declaration? votes: 7, answers: 1 Read on SO: [35] http://goo.gl/OxoSN * Partial decoding of ByteStrings to Text votes: 7, answers: 1 Read on SO: [36] http://goo.gl/9JSKw * Haskell, algorithms and school votes: 7, answers: 1 Read on SO: [37] http://goo.gl/bsM5v About the Haskell Weekly News To help create new editions of this newsletter, please send stories to dstcruz(a)gmail.com. Until next time, Daniel Santa Cruz References 1. http://haskell.org/ 2. http://permalink.gmane.org/gmane.comp.lang.haskell.parallel/14 3. http://www.reddit.com/r/haskell/comments/iuhc0/what_haskell_doesnt_have/ 4. http://elaforge.blogspot.com/2011/07/what-haskell-doesnt-have.html 5. http://www.reddit.com/r/haskell/comments/irxtf/take_the_state_of_haskell_20… 6. http://blog.johantibell.com/2011/07/its-time-for-this-years-state-of.html 7. http://www.reddit.com/r/haskell/comments/iuswk/economic_interpreter_for_has… 8. http://pnyf.inf.elte.hu/fp/Economic_en.xml?yes 9. http://www.reddit.com/r/haskell/comments/iuoun/haskell_on_heroku/ 10. http://www.yesodweb.com/blog/2011/07/haskell-on-heroku 11. http://www.reddit.com/r/haskell/comments/iwm3r/haskell_stickers/ 12. http://www.redbubble.com/products/configure/6390818-sticker 13. http://www.reddit.com/r/haskell/comments/itkii/rewritten_agda_introduction/ 14. http://pnyf.inf.elte.hu/fp/Overview_en.xml?fuckyoureddit#agda 15. http://www.reddit.com/r/haskell/comments/iur1n/a_plugin_for_ghc_to_turn_has… 16. http://www.reddit.com/r/haskell/comments/isqmc/what_is_the_state_of_hackage… 17. http://hackage.haskell.org/trac/hackage/wiki/HackageDB/2.0 18. http://www.reddit.com/r/haskell/comments/itwl5/wxhaskell_the_road_to_the_ha… 19. http://sourceforge.net/mailarchive/forum.php?thread_name=alpine.DEB.2.00.11… 20. http://www.reddit.com/r/haskell/comments/it13r/just_do_it_simple_monadic_eq… 21. http://www.cs.ox.ac.uk/jeremy.gibbons/publications/mr.pdf 22. http://www.reddit.com/r/haskell/comments/it50b/cabaldev_08_is_out_with_impr… 23. http://www.reddit.com/r/haskell/comments/it3lh/functors_applicative_functor… 24. http://heh.fi/haskell/functors/ 25. http://www.reddit.com/r/haskell/comments/iv6g3/snap_052_released/ 26. http://snapframework.com/blog/2011/07/20/snap-0.5.2-released 27. http://stackoverflow.com/questions/6797247/help-in-understanding-pointfree-… 28. http://stackoverflow.com/questions/6736790/how-can-i-combine-handles-in-has… 29. http://stackoverflow.com/questions/6787231/current-state-of-integrating-uni… 30. http://stackoverflow.com/questions/6795384/does-iteratee-i-o-make-sense-in-… 31. http://stackoverflow.com/questions/6736482/literate-haskell-references-and-… 32. http://stackoverflow.com/questions/6740850/call-c-functions-from-haskell-at… 33. http://stackoverflow.com/questions/6747083/type-class-instances-for-types-w… 34. http://stackoverflow.com/questions/6750609/list-of-options-equivalent-of-se… 35. http://stackoverflow.com/questions/6782389/is-it-necessary-to-specify-every… 36. http://stackoverflow.com/questions/6786328/partial-decoding-of-bytestrings-… 37. http://stackoverflow.com/questions/6797216/haskell-algorithms-and-school

1 0

Retaining functions in memory
by Siddhartha Gadgil 27 Jul '11

27 Jul '11

I have been making programs for mathematical applications (low-dimensional topology) in Haskell, which I find a delight to code in. However, the execution is slow, and this seems to be because recursively defined functions seem to be recomputed. For example f(100) needs f(15) which needs f(7) ... The dependencies are not obvious to the compiler. I was looking for a way to retain the values of a specific function in memory. Is there some way to do this. Thanks, Siddhartha

4 3

Input redirection in WinGHCi
by Paul Reiners 27 Jul '11

27 Jul '11

I know I can do the following from a command prompt: $ runghc WC < quux.txt How do I do this in WinGHCi? I know I have to first load the file like this: Prelude> :load WC But then what? This doesn't work: *Main> WC < quux.txt <interactive>:1:1: Not in scope: data constructor `WC' <interactive>:1:6: Not in scope: `quux' <interactive>:1:11: Not in scope: `txt'

2 1

Please help me spot where space leak occur.
by Olexander Kozlov 27 Jul '11

27 Jul '11

Greetings Haskell community, I stuck with a space leak problem in simple task. I have a function described with a list of pairs: type Fn a b = [(a, b)] mapping values from a to b. And I have a composition operation which accepts two functions and returns theirs composition: compose :: Eq b => Fn a b -> Fn b c -> Fn a c Finding composition of 1,000,000 functions takes about 240M with the following implementation: type Fn a b = [(a, b)] lkup :: Eq a => a -> Fn a b -> b lkup x ((a, b) : abs) = if x /= a then lkup x abs else b compose :: Eq b => Fn a b -> Fn b c -> Fn a c compose ((a, b) : abs) bcs = (a, lkup b bcs) : compose abs bcs compose [] _ = [] fldl :: (a -> b -> a) -> a -> [b] -> a fldl f z (x:xs) = fldl f (f z x) xs fldl _ z [] = z fna = [(1, 2), (2, 3), (3, 1)] fni = [(1, 1), (2, 2), (3, 3)] test = fldl compose fni (replicate 1000000 fna) main = print test I build with: ghc --make -prof -auto-all -caf-all -fforce-recomp -rtsopts Test.hs Profile results: Test.exe +RTS -K50M -p -RTS total time = 0.34 secs (17 ticks @ 20 ms) total alloc = 240,003,820 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc compose Main 58.8 80.0 lkup Main 35.3 0.0 test Main 5.9 11.7 fldl Main 0.0 8.3 After reading 'High-Performance Haskell' by Johan Tibell I tried to made my compose function strict: compose :: Eq b => Fn a b -> Fn b c -> Fn a c compose ((a, b) : abs) bcs = let c = lkup b bcs in c `seq` (a, c) : compose abs bcs compose [] _ = [] and memory consuption reduced down to 180M. Good achievement but still too much! Profile results: Test.exe +RTS -K50M -p -RTS total time = 0.24 secs (12 ticks @ 20 ms) total alloc = 180,003,820 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc compose Main 83.3 73.3 lkup Main 8.3 0.0 fldl Main 8.3 11.1 test Main 0.0 15.6 I tried to make fldl strict as well: fldl :: (a -> b -> a) -> a -> [b] -> a fldl f z (x:xs) = let z' = f z x in z' `seq` fldl f z' xs fldl _ z [] = z and end up with 160M of total allocations. Profile results: Test.exe +RTS -K32M -p -RTS total time = 0.30 secs (15 ticks @ 20 ms) total alloc = 160,003,820 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc compose Main 46.7 82.5 lkup Main 40.0 0.0 test Main 6.7 17.5 fldl Main 6.7 0.0 Please help me spot where space leak occur, I see no other places for space leaks. I'll appreciate any help. (I intentionally wrote my own implementations of lookup and foldl to have direct control on them.)

2 3

Ur tutorial, and a challenge
by Adam Chlipala 27 Jul '11

27 Jul '11

Last week, I posted a message to this list looking for people interested in joining projects using my domain-specific language Ur/Web. Some responses rightly chastised me for the lack of documentation on the core Ur language's novel type system features. I'm sure many Haskellers have had the experience of quickly grokking the interfaces of new libraries by reading their type signatures, and I think the same is true for Ur. So, to provide that initial bump of background that should help folks get started, I've begun an Ur tutorial: http://www.impredicative.com/ur/tutorial/ The chapters that are already there are intended to be sufficient to help any experienced Haskell programmer get started quickly with Ur/Web. In particular the second chapter on type-level programming may be of interest as a mind expander, even for folks who don't want to use Ur/Web. I'd love feedback about weaknesses in the tutorial! I also want to attach a challenge to this tutorial, as an expansion to an answer I gave earlier about why Ur/Web needs a new programming language and can't just be implemented as a Haskell library. Consider this online Ur/Web demo: http://www.impredicative.com/ur/demo/crud1.html The example involves a library component encapsulating functionality like that of Ruby on Rails's scaffolding: automatic generation of a standard web-based "admin interface" to an SQL database table. The Ur/Web version uses static typing to guarantee that any applications generated by this component are free of injection attacks and other generic problems. The guarantees apply both to app communication with server-side pieces (e.g., static type-checking of SQL) and client-side pieces (e.g., static type-checking of HTML). This is not done by type-checking individual invocations of the admin-interface component. Rather, the component is checked at a static type which guarantees correct operation for _any_specialization_parameters_. So, the challenge is, can this functionality be implemented in Haskell (GHC extensions fair game, any web framework allowed)? If so, how pretty is it? :)

4 5

Idiomatic ways to make all instances of a certain class also instances of another?
by Tim Cowlishaw 27 Jul '11

27 Jul '11

Hi all, I'm currently embarking on my first major project in Haskell, after dabbling with it for several years, and seem to keep finding myself in situations where I create a typeclass that seems to be some sort of specialisation of another, more general typeclass. Given that this is the case, I've then decided that all instances of the specific class should therefore also be instances of the general class, and arrived at the following method of doing so, using the FlexibleInstances and UndecidableInstances extensions to GHC: {-# LANGUAGE FlexibleInstances, UndecidableInstances #-} class Max a where maximum :: a -> a -> a instance (Ord a) => Max a where maximum = max (Obviously, this is a very trivial, and rather silly example - I'm not really trying to implement a class called 'Max'). However, I'd be curious to know if (a) There are better or more idiomatic ways of achieving the same effect, and (b) Whether or not I should be doing this at all; It did occur to me that this seems rather trying to re-implement OOP-style inheritance with typeclasses, and therefore perhaps not a very Haskellish approach to designing software. Therefore - are there better ways to achieve this, or should I not be doing this at all, and, if the latter, what would be the best means of achieving a similar result (i.e. a typeclass that implements all the functionality of one or more others, optionally with some additional specialism)? Many thanks, Tim

5 7

Fwd: C9 video in the Monadic Design Patterns for the Web series
by Greg Meredith 27 Jul '11

27 Jul '11

Dear Haskellians, A new C9 video in the series! So, you folks already know most of this... except for maybe the generalization of the Conway construction! Best wishes, --greg ---------- Forwarded message ---------- From: Charles Torre <...> Date: Tue, Jul 26, 2011 at 1:12 PM Subject: C9 video in the Monadic Design Patterns for the Web series To: Meredith Gregory <lgreg.meredith(a)gmail.com> Cc: Brian Beckman <...> And we’re live!**** ** ** http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Greg-Meredith-Monadic… **** C**** ** ** *From:* Charles Torre *Sent:* Tuesday, July 26, 2011 11:51 AM *To:* 'Meredith Gregory' *Cc:* Brian Beckman *Subject:* C9 video in the Monadic Design Patterns for the Web series**** ** ** Here it ‘tis:**** ** ** Greg Meredith <http://biosimilarity.blogspot.com/>, a mathematician and computer scientist, has graciously agreed to do a C9 lecture series covering monadic design principles applied to web development. You've met Greg before in a Whiteboard jam session with Brian Beckman<http://channel9.msdn.com/shows/Going+Deep/E2E-Whiteboard-Jam-Session-with-B…> .**** The fundamental concept here is the monad, and Greg has a novel and conceptually simplified explanation of what a monad is and why it matters. This is a very important and required first step in the series since the whole of it is about the application of monadic composition to real world web development.**** In *part 4, *Greg primarily focuses on the idea that *a monad is really an API* -- it's a view onto the organization of data and control structures, not those structures themselves. In OO terms, it's an *interface*. To make this point concrete Greg explores one of the simplest possible data structures that supports at least two different, yet consistent interpretations of the same API. The structure used, Conway's partisan games<http://mathworld.wolfram.com/ConwayGame.html>, turned out to be tailor-made for this investigation. Not only does this data structure have the requisite container-like shape, it provided opportunities to see just what's necessary in a container to implement the monadic interface. ** ** Running throughout the presentation is a more general comparison of reuse between an OO approach versus a more functional one. When the monadic API is "mixed into" the implementing structure we get less reuse than when the implementing structure is passed as a type parameter. Finally, doing the work put us in a unique position to see not just how to generalize Conway's construction, *monadically*, but the underlying pattern which allows the generalization to suggest itself.**** See *part 1 <http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Greg-Meredith-Monadic…> *See *part 2<http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Greg-Meredith-Monadic…> ** *See* part 3<http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Greg-Meredith-Monadic…> ***** ** -- L.G. Meredith Managing Partner Biosimilarity LLC 7329 39th Ave SW Seattle, WA 98136 +1 206.650.3740 http://biosimilarity.blogspot.com -- L.G. Meredith Managing Partner Biosimilarity LLC 1219 NW 83rd St Seattle, WA 98117 +1 206.650.3740 http://biosimilarity.blogspot.com

3 5

Approximate String Matching
by dokondr 27 Jul '11

27 Jul '11

Hi, I am looking for Haskell libraries to do approximate string matching: http://en.wikipedia.org/wiki/Approximate_string_matching I need this to reduce a set of English word variants with spelling errors to a single canonical dictionary entry. Any libraries to work with spelling will also help. Thanks, Dmitri

2 1