September 2012 - Haskell-Cafe

Munich Haskell Meeting
by Christian Neukirchen 22 Sep '12

22 Sep '12

Dear all, Heinrich is on holiday next week, thus I'll manage it this time: Once again, it's time for our monthly get-together. Functional programmers from Munich and other cities will meet on Thu, 27th of September, at 19h30 at Cafe Puck in Munich. If you plan to join, please go to http://www.haskell-munich.de/dates and click the button! With hope to meet many of you there, -- Christian Neukirchen <chneukirchen(a)gmail.com> http://chneukirchen.org

1 0

Question about type inference of a GADT term
by Florian Lorenzen 22 Sep '12

22 Sep '12

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hello cafe, I have the following GADT definitions capturing the simply typed lambda calculus with de Bruijn indices for variables and explicitly annotated types for variables: {-# LANGUAGE GADTs #-} {-# LANGUAGE KindSignatures #-} {-# LANGUAGE DataKinds #-} - -- Typing contexts data Ctx = CtxNil | CtxCons Ctx Type - -- Types data Type = TyInt | TyArrow Type Type - -- Variable indices data Ix (ctx :: Ctx) (ty :: Type) where IxZero :: Ix ctx ty IxSucc :: Ix ctx ty1 -> Ix (CtxCons ctx ty2) ty1 - -- Type representations data TyRep (ty :: Type) where TyRepInt :: TyRep TyInt TyRepArrow :: TyRep ty1 -> TyRep ty2 -> TyRep (TyArrow ty1 ty2) - -- Terms data Term (ctx :: Ctx) (ty :: Type) where TmInt :: Integer -> Term ctx TyInt TmVar :: Ix ctx ty -> Term ctx ty TmAdd :: Term ctx TyInt -> Term ctx TyInt -> Term ctx TyInt TmApp :: Term ctx (TyArrow ty1 ty2) -> Term ctx ty1 -> Term ctx ty2 TmAbs :: TyRep ty1 -> Term (CtxCons ctx ty1) ty2 -> Term ctx (TyArrow ty1 ty2) For the following definition test1 = TmAbs TyRepInt (TmVar IxZero) GHCi infers the type test1 :: Term ctx (TyArrow 'TyInt ty2) I was a bit puzzled because I expected Term ctx (TyArrow TyInt TyInt) Of course, this more special type is an instance of the inferred one, so I can assign it by a type signature. Can someone explain why the inferred type is more general? Terms like test2 = TmAbs TyRepInt (TmAdd (TmVar IxZero) (TmInt 5)) have the type I expected: test2 :: Term ctx (TyArrow 'TyInt 'TyInt) Thank you and best regards, Florian - -- Florian Lorenzen Technische Universität Berlin Fakultät IV - Elektrotechnik und Informatik Übersetzerbau und Programmiersprachen Sekr. TEL12-2, Ernst-Reuter-Platz 7, D-10587 Berlin Tel.: +49 (30) 314-24618 E-Mail: florian.lorenzen(a)tu-berlin.de WWW: http://www.user.tu-berlin.de/florenz/ -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://www.enigmail.net/ iEYEARECAAYFAlBcXs4ACgkQvjzICpVvX7b1WQCePiL+SFNj9X+U0V2fnykuatLX pIcAn1VDNRiSR18s7UgctdPeNzFgStbi =LBGb -----END PGP SIGNATURE-----

2 2

Church vs Boehm-Berarducci encoding of Lists
by oleg＠okmij.org 22 Sep '12

22 Sep '12

There has been a recent discussion of ``Church encoding'' of lists and the comparison with Scott encoding. I'd like to point out that what is often called Church encoding is actually Boehm-Berarducci encoding. That is, often seen > newtype ChurchList a = > CL { cataCL :: forall r. (a -> r -> r) -> r -> r } (in http://community.haskell.org/%7Ewren/list-extras/Data/List/Church.hs ) is _not_ Church encoding. First of all, Church encoding is not typed and it is not tight. The following article explains the other difference between the encodings http://okmij.org/ftp/tagless-final/course/Boehm-Berarducci.html Boehm-Berarducci encoding is very insightful and influential. The authors truly deserve credit. P.S. It is actually possible to write zip function using Boehm-Berarducci encoding: http://okmij.org/ftp/ftp/Algorithms.html#zip-folds

6 10

Passing CString array to Haskell shared library
by Alexander Mumme 21 Sep '12

21 Sep '12

Hello everyone! Long time reader, first time poster. Was wondering if someone could give me some direction or hints on how I might go about passing a CString array into an exported Haskell function. What I'm trying to do is augment the RecordLinkage package from R using Haskell. Seems pretty straight forward. With some help from Neil Mitchell's excellent blog post on the subject ( http://neilmitchell.blogspot.com/2011/10/calling-haskell-from-r.html) I've managed to make calls into Haskell and utilize the Text.EditDistance package. This is working rather well, except that I'm trying to calculate the edit distance from each of 3000 strings to each of 780,000 strings. Since I'm calling Haskell from R once for every comparison (and allocating a result record in R for each return) I find myself running out of memory rather quickly. What I'd like to do is send both complete string lists into Haskell to process, and have it pass me back a result vector. Below is how I'm currently making the call using individual strings. I've tried looking through the GHC User's Guide, through the Wiki on usingthe FFI, and a number of other resources, but I seem to have come to an impasse. Could anyone lend some assistance? ------------- Code start ----- {-# LANGUAGE ForeignFunctionInterface #-} module Levenshtein where import Foreign.C.Types import Foreign.C.String import Foreign.Ptr import Foreign.Storable import Text.EditDistance levenshteinWeight :: Ptr Int -> Ptr Int -> Ptr Int -> Ptr CString -> Ptr CString -> Ptr Int -> IO () levenshteinWeight del ins subs str1 str2 result = do del <- peek del ins <- peek ins subs <- peek subs str1' <- peekCString =<< peek str1 str2' <- peekCString =<< peek str2 poke result $ levenshteinDistance EditCosts { deletionCosts = ConstantCost del, insertionCosts = ConstantCost ins, substitutionCosts = ConstantCost subs, transpositionCosts = ConstantCost 1} str1' str2' foreign export ccall levenshteinWeight :: Ptr Int -> Ptr Int -> Ptr Int -> Ptr CString -> Ptr CString -> Ptr Int -> IO () ------------- Code end ----- Thanks in Advance! Alex

1 0

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 21 Sep '12

21 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 20 Sep '12

20 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