- Haskell-Cafe - Haskell.org

ANNOUNCE: uuid-1.2.6
by Antoine Latter 21 Sep '12

21 Sep '12

Hi folks, I'm happy to announce a new point release of the uuid library, 1.2.6: http://hackage.haskell.org/package/uuid-1.2.6 The 'uuid' package implements most of RFC 4122[1] including random generation and generation based on hardware MAC addresses. I haven't announced a point-release in a while. The changes since 1.2.1 include: * When generating UUIDs from the hardware MAC address, if the MAC address is not available we now use a random seed for our (hidden, global) state machine * The 'Read' instance now drops leading spaces * Added the functions 'toWords' and 'fromWords', primary to support the package uuid-quasi[2]. Take care, Antoine 1: http://tools.ietf.org/html/rfc4122 2: http://hackage.haskell.org/package/uuid-quasi

2 2

simple servers
by brad clawsie 21 Sep '12

21 Sep '12

Hi cafe looking at http://www.haskell.org/haskellwiki/Simple_Servers The last two solutions compared are forkIO vs. explicit event support (based on what was System.Event). Further reading appears to indicate that event support has been integrated into the runtime. Is it true that writing a simple server using forkIO now integrates native event loops implicitly? Or do I still need to create code that explicitly uses (what is now) GHC.Event? One last question. When writing C code, using epoll apis explicitly can impose some blocking. Is the same to be said for GHC.Event? I know all of the changes I am discussing seemed to happen in ghc more than a year ago, sorry, I just can't find anything to explicitly guide me here. Thanks! Brad

4 5

progress reporting in a backtracking algorithm
by Harald Bögeholz 20 Sep '12

20 Sep '12

Dear Haskell Cafe, I am playing around with a backtracking algorithm that can take quite a while to compute all solutions to a problem. I'd like to use Debug.Trace.trace to provisionally output something that lets me estimate the total time it might take. But I just can't wrap my head around it. This is how I think I'd write it in a C-like language: backtrack(int level, double position, double stepsize, misc...) { // with variations = number of variations to try on this level double part = stepsize / variations // split time on this level for (i=0; i<variations; ++i) { double current = position + part*i // do the actual work backtrack(level+1, current, part); if (level < not_too_much_detail) printf("progress: %f%%\n", current); } } and start with backtrack(1, 0.0, 100.0). And now for something completely Haskell: I have a function step :: State -> Index -> [State] that on a certain level tries all allowable varaiants and returns a list of those that can be further pursued on deeper levels. Then solving the problem involves applying the step on all levels (whicht are indexed by some array indices here): solve :: Problem -> [State] solve problem = foldM step start grid where start = stateFromProblem problem grid = indices (sLines start) I am totally at loss at how I could accomplish some kind of progress reporting in this lazily evaluated (I hope) backtracking scheme. If anybody would like to review the full code (about 80 lines total vor the solver, not counting I/O), this is where I am right now: https://github.com/ctbo/slitherlink/tree/c8951ca1eaf83ce9de43f0483740ce339f… and this is the branch I am working on right now: https://github.com/ctbo/slitherlink/tree/2lines Or is there maybe a totally different and better way to approach this kind of tree search in Haskell? I'm eager to learn. Thanks for your attention Harald -- Harald Bögeholz <bo(a)ct.de> (PGP key available from servers) Redaktion c't Tel.: +49 511 5352-300 Fax: +49 511 5352-417 http://www.ct.de/ int f[9814],b,c=9814,g,i;long a=1e4,d,e,h; main(){for(;b=c,c-=14;i=printf("%04d",e+d/a),e=d%a) while(g=--b*2)d=h*b+a*(i?f[b]:a/5),h=d/--g,f[b]=d%g;} (Arndt/Haenel) Affe Apfel Vergaser /* Heise Zeitschriften Verlag GmbH & Co. KG * Karl-Wiechert-Allee 10 * 30625 Hannover * Registergericht: Amtsgericht Hannover HRA 26709 * Persönlich haftende Gesellschafterin: Heise Zeitschriften Verlag * Geschäftsführung GmbH * Registergericht: Amtsgericht Hannover, HRB 60405 * Geschäftsführer: Ansgar Heise, Dr. Alfons Schräder */

1 0

Haskell Weekly News: Issue 244
by Daniel Santa Cruz 19 Sep '12

19 Sep '12

Welcome to issue 244 of the HWN, an issue covering crowd-sourced bits of information about Haskell from around the web. This issue covers the week of September 9 to September 15, 2012. Inbox As you might have heard, GHC 7.6.1 is out for all platforms. I would say "get it while it is still hot", but I guess I missed my opportunity to do that last week. [1] http://goo.gl/0fwDQ Sonke Hahn wrote in to announce that on Monday "Story Episodes of Nikki and the Robots" was was released. [2] http://goo.gl/dBifT Malcolm Wallace has uploaded videos from ICFP 2012, for those of us that didn't have the opportunity to be there. Big thanks for sharing these with the community! [3] http://goo.gl/6ZhYV Quotes of the Week * copumpkin: when in doubt, blame ski * shachaf: You can call the greengrocer and place an order. That'll convert their unordered pears into ordered pears! * shachaf: Those who would give up essential type independence for a little temporary type safety deserve neither independence nor safety. * ddarius: edwardk: So your plan for Haskell adoption is to write Haskell in languages that aren't Haskell, say "Man, these languages suck, this would be super easy in Haskell", and then use the Haskell you started with reproducing functionality at an "unbelievable" rate. * cmccann: personally I'm just waiting for an extension that demotes types to the value level, so that we can finally have natural numbers. Top Reddit Stories * Yet another Haskell IDE in the works Domain: yesodweb.com, Score: 71, Comments: 94 On Reddit: [4] http://goo.gl/N1nfs Original: [5] http://goo.gl/z47p8 * The case of the mysterious explosion in space Domain: serpentine.com, Score: 65, Comments: 9 On Reddit: [6] http://goo.gl/O782g Original: [7] http://goo.gl/eQxOc * Haskell vs. F# vs. Scala: A High-level Language Features and Parallelism Support Comparison Domain: macs.hw.ac.uk, Score: 47, Comments: 30 On Reddit: [8] http://goo.gl/XWdPX Original: [9] http://goo.gl/daRy2 * The functor design pattern Domain: haskellforall.com, Score: 42, Comments: 45 On Reddit: [10] http://goo.gl/FpJL4 Original: [11] http://goo.gl/pZ4yu * How To Exclude Women From Your Technical Community: A Tutorial Domain: tim.dreamwidth.org, Score: 42, Comments: 309 On Reddit: [12] http://goo.gl/iKN7H Original: [13] http://goo.gl/GKMjb * A simple library that allows logic programming in Haskell Domain: github.com, Score: 38, Comments: 10 On Reddit: [14] http://goo.gl/J9Pbp Original: [15] http://goo.gl/1bRw5 * Larry Wall: "You should probably know about it [Haskell] if only to be able to say 'is this like Haskell?', and, if so, then you know you'll have to hire some really smart people to program in it." Domain: youtube.com, Score: 34, Comments: 130 On Reddit: [16] http://goo.gl/z1PTW Original: [17] http://goo.gl/5bCN9 * Malcolm Wallace is broadcasting videos from ICFP Domain: m.youtube.com, Score: 33, Comments: 9 On Reddit: [18] http://goo.gl/O6uuy Original: [19] http://goo.gl/Kyg5O * Darcs hub alpha: a darcsden fork to “turn the dogfooding knobs up to 11” Domain: hub.darcs.net, Score: 30, Comments: 10 On Reddit: [20] http://goo.gl/5D614 Original: [21] http://goo.gl/pDHL9 * The Architecture of the Mighttpd High-Speed Web Server Domain: iij.ad.jp, Score: 28, Comments: 4 On Reddit: [22] http://goo.gl/7yRbw Original: [23] http://goo.gl/oCkBt * Tying the knot on a Rubik's cube Domain: self.haskell, Score: 25, Comments: 7 On Reddit: [24] http://goo.gl/0XPiY Original: [25] http://goo.gl/0XPiY * Kazu Yamamoto: Improving the performance of Warp Domain: yesodweb.com, Score: 24, Comments: 1 On Reddit: [26] http://goo.gl/yvRfR Original: [27] http://goo.gl/gEQlA * Taking advantage of "Theorems for Free"? Domain: self.haskell, Score: 20, Comments: 9 On Reddit: [28] http://goo.gl/cqy6U Original: [29] http://goo.gl/cqy6U Top StackOverflow Questions * Is there a nice way to make function signatures more informative in Haskell? votes: 37, answers: 6 Read on SO: [30] http://goo.gl/vOY98 * Purely functional data structures for text editors votes: 26, answers: 7 Read on SO: [31] http://goo.gl/ciJQ3 * Lazy Pattern matching in Data.List votes: 15, answers: 1 Read on SO: [32] http://goo.gl/T2YPC * Can I provide the type-checker with proofs about inductive naturals in GHC 7.6? votes: 14, answers: 1 Read on SO: [33] http://goo.gl/zoMDr * Why does Haskell's “flip id” has this type? votes: 12, answers: 1 Read on SO: [34] http://goo.gl/HWuyZ * How long pauses can occur in a Haskell program due to garbage collection? votes: 11, answers: 1 Read on SO: [35] http://goo.gl/Stnq7 * Good introduction to free theorems [closed] votes: 11, answers: 1 Read on SO: [36] http://goo.gl/2OVYJ * Int vs Word in common use? votes: 10, answers: 3 Read on SO: [37] http://goo.gl/JR9xK * Haskell collections with guaranteed worst-case bounds for every single operation? votes: 9, answers: 1 Read on SO: [38] http://goo.gl/Oc4L9 * Zipper data structure for graphical model editor votes: 8, answers: 1 Read on SO: [39] http://goo.gl/BF865 Until next time, Daniel Santa Cruz References 1. http://comments.gmane.org/gmane.comp.lang.haskell.general/19477 2. http://joyridelabs.de/blog/?p=1435 3. http://www.youtube.com/playlist?list=PL4UWOFngo5DV0sAM9qsfnPzNtRaDyZ7MD 4. http://www.yesodweb.com/blog/2012/09/building-haskell-ide 5. http://www.reddit.com/r/haskell/comments/zrm9z/yet_another_haskell_ide_in_t… 6. http://www.serpentine.com/blog/2012/09/12/the-case-of-the-mysterious-explos… 7. http://www.reddit.com/r/haskell/comments/zrxns/the_case_of_the_mysterious_e… 8. http://www.macs.hw.ac.uk/~dsg/gph/papers/abstracts/fhpc12.html 9. http://www.reddit.com/r/haskell/comments/zxcks/haskell_vs_f_vs_scala_a_high… 10. http://www.haskellforall.com/2012/09/the-functor-design-pattern.html 11. http://www.reddit.com/r/haskell/comments/zxl49/the_functor_design_pattern/ 12. http://tim.dreamwidth.org/1762846.html 13. http://www.reddit.com/r/haskell/comments/zxmzv/how_to_exclude_women_from_yo… 14. https://github.com/smichal/hs-logic 15. http://www.reddit.com/r/haskell/comments/zq1gb/a_simple_library_that_allows… 16. http://www.youtube.com/watch?v=LR8fQiskYII&feature=player_detailpage#t=169s 17. http://www.reddit.com/r/haskell/comments/zpff3/larry_wall_you_should_probab… 18. http://m.youtube.com/channel/UCP9g4dLR7xt6KzCYntNqYcw?&desktop_uri=%2Fchann… 19. http://www.reddit.com/r/haskell/comments/zsjag/malcolm_wallace_is_broadcast… 20. http://hub.darcs.net/ 21. http://www.reddit.com/r/haskell/comments/zx4th/darcs_hub_alpha_a_darcsden_f… 22. http://www.iij.ad.jp/en/company/development/tech/mighttpd/ 23. http://www.reddit.com/r/haskell/comments/zrydv/the_architecture_of_the_migh… 24. http://www.reddit.com/r/haskell/comments/znt85/tying_the_knot_on_a_rubiks_c… 25. http://www.reddit.com/r/haskell/comments/znt85/tying_the_knot_on_a_rubiks_c… 26. http://www.yesodweb.com/blog/2012/09/improving-warp 27. http://www.reddit.com/r/haskell/comments/ztvu7/kazu_yamamoto_improving_the_… 28. http://www.reddit.com/r/haskell/comments/zydcs/taking_advantage_of_theorems… 29. http://www.reddit.com/r/haskell/comments/zydcs/taking_advantage_of_theorems… 30. http://stackoverflow.com/questions/12416723/is-there-a-nice-way-to-make-fun… 31. http://stackoverflow.com/questions/12358083/purely-functional-data-structur… 32. http://stackoverflow.com/questions/12429449/lazy-pattern-matching-in-data-l… 33. http://stackoverflow.com/questions/12442858/can-i-provide-the-type-checker-… 34. http://stackoverflow.com/questions/12339822/why-does-haskells-flip-id-has-t… 35. http://stackoverflow.com/questions/12404031/how-long-pauses-can-occur-in-a-… 36. http://stackoverflow.com/questions/12421085/good-introduction-to-free-theor… 37. http://stackoverflow.com/questions/12432154/int-vs-word-in-common-use 38. http://stackoverflow.com/questions/12393104/haskell-collections-with-guaran… 39. http://stackoverflow.com/questions/12339805/zipper-data-structure-for-graph…

1 0

foldl vs. foldr
by Jan Stolarek 19 Sep '12

19 Sep '12

Hi list, I have yet another question about folds. Reading here and there I encountered statements that foldr is more important than foldl, e.g. in this post on the list: http://www.haskell.org/pipermail/haskell-cafe/2012-May/101338.html I want to know are such statements correct and, if so, why? I am aware that foldl' can in some circumstances operate in constant space, while foldr can operate on infinite lists if the folding function is lazy in the second parameter. Is there more to this subject? Properties that I mentioned are more of technical nature, not theoretical ones. Are there any significant theoretical advantages of foldr? I read Bird's and Wadler's "Introduction to functional programming" and it seems to me that foldl and foldr have the same properties and in many cases are interchangeable. Greets, Janek

4 3

[ANNOUNCE] Fmark markup language
by José Lopes 19 Sep '12

19 Sep '12

Hello everyone, I just wanted to share a package I created called Fmark, now available on HackageDB. Feedback both on the project and on the code is greatly appreciated :) Fmark (Friendly Markup) is a very simple markup language without syntax and simple but sophisticated document styling, capable of producing PDF and XML files. The key philosophy behind this markup language is to eliminate the strange syntactic characters seen in most markup languages, but at the same time try to maintain a high level of expressiveness, using only document reconstruction. Check it out http://hackage.haskell.org/package/fmark https://github.com/jabolopes/fmark Best regards, José -- José António Branquinho de Oliveira Lopes 58612 - MEIC-A Instituto Superior Técnico (IST), Universidade Técnica de Lisboa (UTL) jose.lopes(a)ist.utl.pt

8 21

ANNOUCE: one-liner-0, SYB-like generics with constraint kinds
by Sjoerd Visscher 19 Sep '12

19 Sep '12

Hi all, I am pleased to announce the first release of One-Liner, a package for writing short and concise generic instances of type classes. It works a bit like Scrap-Your-Boilerplate, but it uses the new constraint kinds instead of the Typeable class. On hackage: http://hackage.haskell.org/package/one-liner-0 On github: https://github.com/sjoerdvisscher/one-liner For example, this is how to write generic equality (using the All monoid): eqADT :: (ADT t, Constraints t Eq) => t -> t -> Bool eqADT s t = ctorIndex s == ctorIndex t && getAll (mbuilds (For :: For Eq) (\fld -> All $ s ! fld == t ! fld) `at` s) The code works like this: "Constraints t Eq" means it requires that all subcomponents of type t have an Eq instance, and then values s and t are equal if they are built by the same constructor and each subcomponent is equal. The package is called One-Liner because the generic functions often end up as short as eqADT, especially if there's already an appropriate Monoid or Applicative functor available. Here are two more examples, generic put and get for the Binary package (after adding the missing Monoid instance for Put) putADT :: (ADT t, Constraints t Binary) => t -> Put putADT t = putWord8 (toEnum (ctorIndex t)) >> gfoldMap (For :: For Binary) put getADT :: (ADT t, Constraints t Binary) => Get t getADT = do ix <- fromEnum <$> getWord8 buildsA (For :: For Binary) (const get) !! ix Finally, to give a complete sense of what's involved, here's an example data type and its ADT implementation: data T a = A Int a | B a (T a) instance ADT (T a) where ctorIndex A{} = 0 ctorIndex B{} = 1 type Constraints (T a) c = (c Int, c a, c (T a)) buildsRecA For sub rec = [ (ctor "A", A <$> sub (FieldInfo (\(A i _) -> i)) <*> sub (FieldInfo (\(A _ a) -> a))) , (ctor "B", B <$> sub (FieldInfo (\(B a _) -> a)) <*> rec (FieldInfo (\(B _ t) -> t))) ] If you want to learn more, you can find an introductory blog post here: https://github.com/sjoerdvisscher/blog/blob/master/2012/2012-09-06%20constr… Some complete examples are here: https://github.com/sjoerdvisscher/one-liner/tree/master/examples Some more generic functions, including generic Show and Read: https://github.com/sjoerdvisscher/one-liner/blob/master/src/Generics/OneLin… -- Sjoerd Visscher https://github.com/sjoerdvisscher/blog

1 0

How to implement nested loops with tail recursion?
by sdiyazg＠sjtu.edu.cn 19 Sep '12

19 Sep '12

I need to implement fast two-level loops, and I am learning using seq to make calls tail-recursive. I write programs to compute main = print $ sum [i*j|i::Int<-[1..20000],j::Int<-[1..20000]] This program (compiled with -O2) runs twenty times slower than the unoptimized (otherwise the loop gets optimized out) C version. But it seems to run in constant memory, so I assume that it has been turned into loops. #include <stdio.h> int main(){ int s=0; for(int i=1;i<=20000;++i){ for(int j=1;j<=20000;++j){ s+=i*j; } } printf("%d\n",s); return 0; } Then I write main = print $ f 1 where f i = let x = g 1 in x `seq` (x + if i<20000 then f (i+1) else 0) :: Int where g j = let x = i*j in x `seq` (x + if j<20000 then g (j+1) else 0) :: Int This version runs out of memory. When I scale the numbers down to 10000, the program does run correctly, and takes lots of memory. Even if I change the seqs into deepseqs, or use BangPatterns (f !i =... ; g !j = ...), the situation doesn't change. A monadic version import Control.Monad.ST.Strict import Control.Monad import Data.STRef.Strict main = print $ runST $ do s <- newSTRef (0::Int) let g !i !j = if (j<=10000) then modifySTRef s (+1)>>(g i (j+1)) else return () let f !i = if (i<=10000) then g i 1>>(f $ i+1) else return () f 1 readSTRef s also runs out of memory. So how can I write a program that executes nested loops efficiently?

3 6

ANNOUNCE: som-1.0
by Amy de Buitléir 19 Sep '12

19 Sep '12

Do you have some data that you'd like to understand better? I'm happy to announce a new package called som that may help: http://hackage.haskell.org/package/som https://github.com/mhwombat/som/wiki (wiki) A Kohonen Self-organising Map (SOM) maps input patterns onto a regular grid (usually two-dimensional) where each node in the grid is a model of the input data, and does so using a method which ensures that any topological relationships within the input data are also represented in the grid. This implementation supports the use of non-numeric patterns. In layman's terms, a SOM can be useful when you want to discover the underlying structure of some data. I have a brief tutorial in the wiki, which I hope to expand over the next few weeks.

1 0

ANNOUNCE: grid-2.0
by Amy de Buitléir 19 Sep '12

19 Sep '12

I'm happy to announce a new major release of the grid package: http://hackage.haskell.org/package/grid https://github.com/mhwombat/grid/wiki (wiki) WHAT'S NEW: The GridMap module provides ordered maps from tiles on a grid to values. This module is a wrapper around Grid and Map, in order to combine the functionality of grids and maps into a single type. This may be of interest to anyone developing a game based on a grid. ABOUT GRID: Grid provides tools for working with regular arrangements of tiles, such as might be used in a board game or self-organising map (SOM). Grid currently supports triangular, square, and hexagonal tiles, with various 2D and toroidal layouts. If you need a tile shape or layout that isn't currently provided, please let me know. See Math.Geometry.Grid for an example of how to use the package. Suggestions for improvement are welcome.

1 0