- Haskell-Cafe - Haskell.org

Data.List / Map: simple serialization?
by Dmitri O.Kondratiev 10 Jun '11

10 Jun '11

Hello, Please advise on existing serialization libraries. I need a simple way to serialize Data.List and Data.Map to plain text files. Thanks, Dmitri

6 12

Plug space leak with seq. How?
by Alexey Khudyakov 10 Jun '11

10 Jun '11

Hello café! This mail is literate haskell I have some difficulties with understanding how bang patterns and seq works. > {-# LANGUAGE BangPatterns #-} > import Control.Monad > import Control.Monad.Trans.State.Strict > > leak :: State Int () > leak = do > a <- get > put (a+1) > leak This function have obvious space leak. It builds huge chain of thunks so callling `runState leak 0' in ghci will eat all memory. Fix is trivial - add bang pattern. However I couldn't achieve same effect with seq. How could it be done? > noLeak :: State Int () > noLeak = do > a <- get > let !a' = (a + 1) > put a' > noLeak Thanks.

3 5

SIGPLAN Programming Languages Software Award
by Isaac Potoczny-Jones 10 Jun '11

10 Jun '11

I'm pleased to be able to relay the following announcement from ACM SIGPLAN: The SIGPLAN Programming Languages Software Award is awarded to an institution or individual(s) to recognize the development a software system that has had a significant impact on programming language research, implementations, and tools. The impact may be reflected in the wide-spread adoption of the system or its underlying concepts by the wider programming language community either in research projects, in the open-source community, or commercially. The award includes a prize of $2,500. For 2011, the winners of the award are Simon Peyton Jones and Simon Marlow of Microsoft Research, Cambridge, for GHC The award winners are donating the entirety of the prize money to haskell.org. Citation: Simon Peyton Jones and Simon Marlow receive the SIGPLAN Software Award as the authors of the Glasgow Haskell Compiler (GHC), which is the preeminent lazy functional programming system for industry, teaching, and research. GHC has not only provided a language implementation, but also established the whole paradigm of lazy functional programming and formed the foundation of a large and enthusiastic user community. GHC's flexibility has supported experimental research on programming language design in areas as diverse as monads, generalized algebraic data types, rank-N polymorphism, and software transactional memory. Indeed, a large share of the research on lazy functional programming in the last 5–10 years has been carried out with GHC. Simultaneously, GHC's reliability and efficiency has encouraged commercial adoption, in the financial sector in institutions like Credit Suisse and Standard Chartered Bank, and for high assurance software in companies like Amgen, Eaton, and Galois. A measure of GHC's influence is the way that many of the ideas of purely functional, "typeful programming" have been carried into newer languages and language features. including C#, F#, Java Generics, LINQ, Perl 6, Python, and Visual Basic 9.0. Peyton Jones and Marlow have been visionary in the way that they have transitioned research into practice. They have been role models and leaders in creating the large and diverse Haskell community, and have made GHC an industrial-strength platform for commercial development as well as for research. Links: http://www.sigplan.org/award-software.htm http://corp.galois.com/blog/2011/6/7/sigplan-programming-languages-software…

11 15

Delimited Continuations For Web Development?
by aditya siram 10 Jun '11

10 Jun '11

Hi all, Is anyone in the Haskell community doing web development using delimited continuations? Oleg had a talk on it [1] using Ocaml and CGI but I haven't heard of anyone taking it further. -deech [1]http://okmij.org/ftp/continuations/index.html#shift-cgi

1 0

Re: [Haskell-cafe] Input and output of mathematical expressions
by Daniel Patterson 09 Jun '11

09 Jun '11

(I originally sent this reply from the wrong address, see below) On Jun 9, 2011, at 11:03 AM, Daniel Patterson wrote: > Also if you are doing this for web, I haven't used it personally (yet), but http://www.mathjax.org/ looks really good... would allow you to actually just write it in LaTeX (as writing MathML by hand is not something I'd like to subject anyone to). > > On Jun 9, 2011, at 10:59 AM, Chris Smith wrote: > >> Ae you looking to do this in a web application, or client-side? Since one of your requirements is to display a typeset equation, that makes a bit of difference. In a web-based setting, the best way to do that is probably MathML, whereas a GUI will be a bit harder. >> >> On Jun 9, 2011 8:24 AM, "Jacek Generowicz" <jacek.generowicz(a)cern.ch> wrote: >> > Greetings Cafe, >> > >> > What would you recommend as a Haskell-based means of interactively >> > reading and writing mathematical formulae? >> > >> > As a toy example, what might I use to write a program which presents >> > the user with >> > >> > Please simplify the expression: \pi x^2 + 3\pi x^2 >> > >> > (Where the TeX-style expression would be presented with a greek pi and >> > superscript twos on the xs.) >> > >> > The user should then have the ability to reply with something that >> > looks like the result of TeXing >> > >> > 5 \pi x^2 >> > >> > Whatever means the user uses to enter this expression, he should be >> > able to preview the "typeset" version of his input before submitting. >> > >> > Any ideas? >> > >> > Thanks. >> > >> > >> > _______________________________________________ >> > Haskell-Cafe mailing list >> > Haskell-Cafe(a)haskell.org >> > http://www.haskell.org/mailman/listinfo/haskell-cafe >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >

2 1

Type Constraints on Data Constructors
by Guy 09 Jun '11

09 Jun '11

{- continuing discussion from beginners@ -} I have code such as class Foo f where foo :: a -> f a data Bar f a = Foo f => Bar {bar :: f a} instance Foo (Bar f) where foo a = Bar $ foo a GHC insists that I put Foo f => on the instance declaration, even though the constructor for Bar implies this. Is there any reason why GHC cannot infer this constraint from the Bar constructor? One issue raised in the beginners thread is that undefined :: Bar f a is not Foo f, but as undefined cannot be evaluated, this would not appear to be a problem.

5 5

Re: [Haskell-cafe] Type Constraints on Data Constructors
by Guy 09 Jun '11

09 Jun '11

Can this be extended to records, without redundant repetition? data Baz f a = Baz {baz :: Foo f => f a, baz2 :: Foo f => f a} The type constraint for baz2 adds no information, as it's the same f as baz, but I can't leave it out. ----- Original Message ----- > From: Daniel Schüssler <danlex(a)gmx.de> > To: haskell-cafe(a)haskell.org > Cc: Guy <guytsalmaves-h(a)yahoo.com> > Sent: Thursday, 9 June 2011, 2:06 > Subject: Re: [Haskell-cafe] Type Constraints on Data Constructors > > Hello, > > you might be thinking of this type? > > {-# LANGUAGE Rank2Types #-} > > class Foo f where > foo :: a -> f a > > data Baz f a = Baz (forall f. Foo f => f a) > > instance Foo (Baz f) where > foo a = Baz (foo a) > > Maybe the difference between Bar and Baz ist best explained by writing it with > an explicit class dictionary for Foo: > > {-# LANGUAGE Rank2Types #-} > > data FooDict f = FooDict { > foo :: forall a. a -> f a > } > > data Bar f a = Bar (FooDict f) (f a) > > data Baz f a = Baz (FooDict f -> f a) > > fooDict_Baz :: FooDict (Baz f) > fooDict_Baz = FooDict (\a -> Baz (\d -> foo d a)) > > -- fooDict_Bar :: FooDict (Bar f) > -- fooDict_Bar = FooDict (\a -> Bar ? ?) > -- Doesn't work - you'd have to create a 'FooDict f' and a > 'f a' out of just > an 'a' > > > > Cheers, > Daniel

2 1

Re: [Haskell-cafe] Type Constraints on Data Constructors
by Daniel Schüssler 09 Jun '11

09 Jun '11

Hello, you might be thinking of this type? {-# LANGUAGE Rank2Types #-} class Foo f where foo :: a -> f a data Baz f a = Baz (forall f. Foo f => f a) instance Foo (Baz f) where foo a = Baz (foo a) Maybe the difference between Bar and Baz ist best explained by writing it with an explicit class dictionary for Foo: {-# LANGUAGE Rank2Types #-} data FooDict f = FooDict { foo :: forall a. a -> f a } data Bar f a = Bar (FooDict f) (f a) data Baz f a = Baz (FooDict f -> f a) fooDict_Baz :: FooDict (Baz f) fooDict_Baz = FooDict (\a -> Baz (\d -> foo d a)) -- fooDict_Bar :: FooDict (Bar f) -- fooDict_Bar = FooDict (\a -> Bar ? ?) -- Doesn't work - you'd have to create a 'FooDict f' and a 'f a' out of just an 'a' Cheers, Daniel On 2011-June-08 Wednesday 20:45:56 Guy wrote: > {- continuing discussion from beginners@ -} > > I have code such as > > class Foo f where > foo :: a -> f a > > data Bar f a = Foo f => Bar {bar :: f a} > > instance Foo (Bar f) where > foo a = Bar $ foo a > > GHC insists that I put Foo f => on the instance declaration, even though > the constructor for Bar implies this. > > Is there any reason why GHC cannot infer this constraint from the Bar > constructor? One issue raised in the beginners thread is that > undefined :: Bar f a > is not Foo f, but as undefined cannot be evaluated, this would not appear > to be a problem. > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe

1 1

Computing the memory footprint of a HashMap ByteString Int (Was: How on Earth Do You Reason about Space?)
by Johan Tibell 09 Jun '11

09 Jun '11

Hi Aleksandar, I thought it'd be educational to do some back-of-the-envelope calculations to see how much memory we'd expect to use to store words in a HashMap ByteString Int. First, lets start by looking at how much memory one ByteString uses. Here's the definition of ByteString [1]: data ByteString = PS {-# UNPACK #-} !(ForeignPtr Word8) {-# UNPACK #-} !Int -- offset {-# UNPACK #-} !Int -- length The two Int fields are used to support O(1) slicing of ByteStrings. We also need the definitions of ForeignPtr [2] and Int. data ForeignPtr a = ForeignPtr Addr# ForeignPtrContents data ForeignPtrContents = PlainForeignPtr !(IORef (Finalizers, [IO ()])) | MallocPtr (MutableByteArray# RealWorld) !(IORef (Finalizers, [IO ()])) | PlainPtr (MutableByteArray# RealWorld) data Int = I# Int# The UNPACK indicates to the compiler that it should unpack the contents of a constructor field into the constructor itself, removing a level of indirection. We'll end up with a structure that looks like this: data ByteString = PS Addr# ForeignPtrContents Int# -- offset Int# -- length To compute the size of a ByteString, count the number of constructor fields and add one (for the constructor itself). This is how many words the value is going to use. In this case it's 5 words. In addition we need to add the size of the ForeignPtrContents constructor, which happens to be a PlainPtr in this case, so we add two more words. Finally we need to look at the definition of MutableByteArray# [3], which is implemented by a C struct named StgArrWords: typedef struct { StgHeader header; StgWord bytes; StgWord payload[FLEXIBLE_ARRAY]; } StgArrWords; The StgHeader takes one word (when compiling with profiling turned off) so StgArrWords takes 2 words, plus the actual payload. If we add it all up we get 9 words, plus the size of the payload (i.e. the length of a word encoded using UTF-8 in your case). Now lets look at the definition of HashMap [4]: data HashMap k v = Bin {-# UNPACK #-} !SuffixMask !(HashMap k v) !(HashMap k v) | Tip {-# UNPACK #-} !Hash {-# UNPACK #-} !(FL.FullList k v) | Nil We also need the definition of FullList [5]: data FullList k v = FL !k v !(List k v) data List k v = Nil | Cons !k v !(List k v) For the sake of this discussion lets assume the tree is perfectly balanced. For a HashMap of size N this means that we have N leaves (Tip) and N-1 interior nodes (Bin). Each Bin takes 4 words. The size of the Tip depends on the number of hash collisions. These are quite rare so lets assume that the FullList only has one element. Also, the Nil constructor is free as it can be shared by all instances in the program. After applying the UNPACK pragmas the Tip constructor looks like: | Tip Int# !k v !(List k v) This takes another 5 words. Now when we know the overhead of both Bin and Tip we can compute the overhead per key/value pair as: (5N + 4(N-1)) / N = 9 - 4/N ~= 9 words. Given that an Int (not an Int#) takes 2 words, we can approximate the memory cost of a key/value pair in a HashMap ByteString Int as (9 + 9 + 2) * MachineWordSize + AvgByteStringLength bytes. For example, the average English word length is 5 characters, if you include stop words. We'd expect to use (9 + 9 + 2) * 8 + 5 = 165 bytes per unique word in our input corpus, on a 64-bit machine. Plus any GC overhead. This is probably more than one would expect. I'm working on switching HashMap to use another data structure, a Hash Array Mapped Trie, in its implementation. This will bring the overhead down from 9 words to about 4 words. You could try using the lower overhead SmallString type from the smallstring package [6]. It has an overhead of 4 words per string (instead of 9 like ByteString). There's some runtime overhead involved in converting a value (i.e. Text) to a SmallString. I don't know if this overhead will be noticeable in your program. 1. http://code.haskell.org/bytestring/Data/ByteString/Internal.hs 2. https://github.com/ghc/packages-base/blob/master/GHC/ForeignPtr.hs 3. https://github.com/ghc/ghc/blob/master/includes/rts/storage/Closures.h 4. https://github.com/tibbe/unordered-containers/blob/master/Data/HashMap/Comm… 5. https://github.com/tibbe/unordered-containers/blob/master/Data/FullList/Laz… 6. http://hackage.haskell.org/package/smallstring P.S. If your program indeed has a space leak this won't help you, but it's a good way to figure out if your program uses a reasonable amount of memory. Cheers, Johan

3 5

Haskell Weekly News: Issue 185
by Daniel Santa Cruz 09 Jun '11

09 Jun '11

Welcome to issue 180 of the HWN, a newsletter covering developments in the Haskell community. This release covers the week of May 29 to Jun 4, 2011. You can find the HTML version at: http://goo.gl/Tm1Qu Announcements Sebastian Fischer wrote in to inform us of of a student internship for parallel Haskell at the National Institute of Informatics in Tokyo. The internship is for up to three months, between July and September 2011. http://goo.gl/xHjkn EIJIRO Sumii reminded us that the ICFP Programming Contest 2011 will be starting on June 17. http://goo.gl/eumwm Quotes of the Week * Tom Murphy: Great! New I really can say "Come on! It's fun! I can write foldr with foldl!" * Cale: C++, Y U SO UGLY? * xplat: nae, that'd be 'arr, my small example ain't half near as yellow as a lily-livered spaniard! scupper me wi' a cutlass, arr.' * Cale: rnf accidentally the entire data structure Top Reddit Stories * Haskell and parallelism in the Economist Domain: economist.com, Score: 66, Comments: 5 On Reddit: http://goo.gl/rBnc1 Original: http://goo.gl/vFtGY * I have the world's coolest hoodie (X-post from r/programming) Domain: imgur.com, Score: 28, Comments: 15 On Reddit: http://goo.gl/bk5wt Original: http://goo.gl/CT3fb * An OpenGL in Haskell anecdote which illustrates the obvious, HOpenGL is low level and imperative. Domain: haskell.org, Score: 27, Comments: 24 On Reddit: http://goo.gl/QtDNy Original: http://goo.gl/LUoL9 * Yesod for non-Haskellers (also, for Haskellers) Domain: yesodweb.com, Score: 27, Comments: 2 On Reddit: http://goo.gl/ekOQJ Original: http://goo.gl/UCyIv * Fast forwarding lrand48() Domain: blog.sigfpe.com, Score: 24, Comments: 0 On Reddit: http://goo.gl/Ki0in Original: http://goo.gl/5ICat * Silk (Haskell, semantic web start up) is hiring in Amsterdam Domain: news.ycombinator.com, Score: 24, Comments: 0 On Reddit: http://goo.gl/GUFVP Original: http://goo.gl/j8fRW * Nikki and the Robots 0.3 is out Domain: joyridelabs.de, Score: 23, Comments: 7 On Reddit: http://goo.gl/w3yrF Original: http://goo.gl/sJdwj * Introducing the Yesod Wiki Domain: yesodweb.com, Score: 19, Comments: 0 On Reddit: http://goo.gl/4TStP Original: http://goo.gl/noMVO * Communicating Haskell Processes: The Long And The Short Of It Domain: chplib.wordpress.com, Score: 19, Comments: 0 On Reddit: http://goo.gl/mC8cw Original: http://goo.gl/hHHoH * What libraries from scientific computing have yet to be written? Domain: self.haskell, Score: 17, Comments: 23 On Reddit: http://goo.gl/QXwyA Top StackOverflow Questions * "A proof is a program; the formula it proves is a type for the program" [migrated] votes: 17, answers: 0 Read on SO: http://goo.gl/LfzPM * Writing foldl using foldr votes: 16, answers: 2 Read on SO: http://goo.gl/O7I0Z * Binary Serialization for Lists of Undefined Length in Haskell votes: 13, answers: 1 Read on SO: http://goo.gl/pZkyI * From C ++ to Haskell Classes and States votes: 12, answers: 2 Read on SO: http://goo.gl/yYt9R * Why does Haskell force data constructor's first letter to be upper case? votes: 11, answers: 3 Read on SO: http://goo.gl/dnGIl * Why is such a function definition not allowed in haskell ? votes: 10, answers: 5 Read on SO: http://goo.gl/0RoHY 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

1 0