- Haskell-Cafe - Haskell.org

Contract opportunity with Biosimilarity LLC
by Greg Meredith 29 Jul '11

29 Jul '11

Dear Haskellians, No desire to spam, but some folks on this list might find this of interest. Best wishes, --greg Biosimilarity LLC is looking for a the next Merlin! We need an artiste with a certain taste and technical instinct that have attracted them to next generation functional programming languages and other high magic. We need a technologist who can make the demons and dragons of web front ends do their bidding while making sound architectural and platform choices. Naturally, comfort with the Open Source ecosystem from git and GitHub to mvn and/or sbt to Jenkins is a given. For such a candidate we don't have to talk about familiarity with Scala or Haskell or ML or JavaScript or Clojure because they eat languages for breakfast and graphics libraries for lunch. The initial engagement is for a limited contract. However, if things go well, who knows what adventures await? The innovations and market potential of the project are guaranteed to keep any sorcerer fascinated. And, you'll get a chance to work with a team of like-minded magicians with long track records of delivering landmark software. While Biosimilarity is a Seattle-based company, telecommuting is definitely an option for the right candidate. If you feel like this might be you, please contact me directly at this email or via the number provided below. Sending along a CV in advance of a more personable communication is likely to be the most effective protocol, but we're always open to creativity. An online portfolio of web projects could also be an advantage, but again raw creativity and can-do carry the day here. -- L.G. Meredith Managing Partner Biosimilarity LLC 1219 NW 83rd St Seattle, WA 98117 +1 206.650.3740 http://biosimilarity.blogspot.com

3 2

Re: [Haskell-cafe] compare iteratee with python's yield
by oleg＠okmij.org 29 Jul '11

29 Jul '11

Your question is insightful. The posted answers are excellent. I merely wish to illustrate one, already made, point on a concrete example. The complete code is in the file http://okmij.org/ftp/Haskell/Iteratee/IterDemo.hs The file implements a series of progressively more complex examples -- from wc to grep, -- stressing compositionality. The whole program is assembled from independent building blocks; as our task changes, we replace one building block with another. The building blocks, iteratees, may be stateful. We never have to worry about writing out the whole state of the program and properly initializing it. The overall state is implicitly composed from the state of each building block; each iteratee manages its own state without leaking it. The particular example to illustrate the state encapsulation is grep1_word > grep1_word word fname = > let search = IterateeM.dropWhile (/= word) >> IterateeM.head > runI' = runI . en_handle (\_ -> "not found:" ++ word) in > print =<< run =<< enum_file fname > (runI =<< en_lines > ((runI' =<< en_words search) > `en_pair` (count_i `en_pair` en_last))) which implements "grep -w -n -m 1 <word> <filename>". It searches for the first occurrence of the given word in the file and returns the line of that occurrence and the line number. (The example also illustrates exception handling: The exception is raised by Iteratee.head when IterateeM.dropWhile dropped the whole stream while looking for the given word.) A few comments: en_lines is the enumeratee, transforming a stream of characters into a stream of lines; en_words is the enumeratee that transforms the stream of lines to the stream of words. The stateful iteratee count_i counts the elements in any stream; en_last, the analogue of List.last, returns the last seen element. The combinator en_pair pairs two iteratees to run in parallel, processing the same stream chunk-by-chunk. The processing stops as soon as one of the iteratees in the pair stopped. That behavior does the trick: "en_words search" stops when the word is found. The whole pair is stopped too. The other component of the pair, (count_i `en_pair` en_last), will receive EOF and tell us the line and the line count they have last seen. I guess the example can be written in Python-like style as follows (simplifying and assuming that the file is already parsed into lines): counter = 0 for line in file_lines: counter = counter + 1 if contains line word: print counter print line break Suppose we wish to change our example to print not only the found line, but a few lines before it (the option "-B" of grep). We have to modify our Python-like code: -- add a piece of state to keep the context lines, and initialize it -- add code to update the state as we read lines -- add the finalization code, to convert the state to the desired result The code will look like the following (### mark the changes): counter = 0 lines_seen = [] ### for line in file_lines: counter = counter + 1 accumulate lines_seen line ### if contains line word: print counter print (finalize lines_seen) ### break In contrast, to modify the iteratee code for the new task, we make the _single_ change: replace en_last with (en_lastN 5) (for 5 lines of context). It should be stressed that the Python code has to be changed in three *distinct, disconnected places*. New state has to be defined and initialized, before the loop. The state has to be updated, somewhere in the loop. The state has to be finalized, in the loop termination part. When changing code, it is easy to overlook the needed changes. For example, it is easier to accumulate the context lines in reverse order. When printing the lines, we should not forget to reverse them. When changes are disconnected, it is hard to reason and test for them. With so many other things going on, it is hard to write a proper test (for example, when testing the context accumulation we don't care about word matching; we should test the accumulation in isolation of whatever else we are doing in the iteration). The iteratee en_lastN deals only with the context accumulation aspect: > -- Return N last received elements > -- The acc below is the list of N last elements in the reverse > -- order > en_lastN :: Monad m => Int -> Iteratee el m [el] > en_lastN n = ie_cont $ step [] > where > step acc (Chunk []) = ie_contM (step acc) > step acc (Chunk ls) = ie_contM (step $! Prelude.take n $ reverse ls ++ acc) > step acc stream = ie_doneM (reverse acc) stream The initialization of the state, the accumulation and the finalization are all in the same place. The en_lastN iteratee does not care of counting, searching, or whatever else is going on. In fact, the iteratee is pure and deals with arbitrary elements (not necessarily lines). We can test it using Quickcheck or HUnit. No IO is needed for the test. Thus in the iteratee style, the overall state of the program becomes distributed, across iteratees that encapsulate and manage only their own, small portion of the program state. The code IterDemo.hs shows other examples, including emulating generators (aka, unfold_stream, or the `while loop'), to build the stream of intermediate results of an iteratee. An iteratee in question does not even suspect that it is being used `incrementally', seduced to reveal the intermediate results. Thank you for the inspiring question.

1 0

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 28 Jul '11

28 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 28 Jul '11

28 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