May 2012 - Haskell-Cafe

Heads up: importing the Cabal issue tracker to github next week
by Bryan O'Sullivan 22 May '12

22 May '12

I am planning on doing this early next week, probably in two phases. As part of the import process, github will generate a *lot* of notification emails. I'm afraid there is nothing I can do to stem the tide, as github does not provide a mechanism to suppress these. If you have a github account, and you have filed bugs against Cabal in Trac, please brace yourself.

2 1

Haskell Day 2012 (in Japan)
by Kazu Yamamoto 22 May '12

22 May '12

Hello Cafe, This is just FYI. We Hasekell community in Japan will have an event called Haskell Day 2012 on 27th May to cerebrate the publication of the Japanese version of "Learn you". 180+ people have already registered: # This page is written in Japanese. http://partake.in/events/ab7f77b4-7541-47a4-867d-21a096ca883c P.S. The Japanese version of "Learn you" was on sale yesterday and already sold out in many bookstores. :-) --Kazu

1 0

(+1) vs let inc=(+1)
by Greg Fitzgerald 22 May '12

22 May '12

In ghci 7.4.1: Prelude> :t (+1) (+1) :: Num a => a -> a Prelude> let inc=(+1) Prelude> :t inc inc :: Integer -> Integer Why the difference? Thanks, Greg

3 3

From some "High-Performance Computing" book; "It is hard to eradicate from C++'ers the need for objects, classes, etc. ..."
by KC 22 May '12

22 May '12

"For high-performance computing you want to avoid such software engineering abstractions as classes, objects, etc...." Therefore, I would say, since Haskell makes possible many fine-levels of abstraction, if the compiler can strip most of these away, then it would come close to the speed of C (i.e. C++ without most of the software engineering abstractions). Still, I remember that quote that, "Another level of indirection solves everything." Or If you're Penn & Teller, "Another level of misdirection solves everything." Casey -- -- Regards, KC

1 0

ANN: reform - a type-safe form generation and validation library in the spirit of formlets and digestive-functors < 0.2
by Jeremy Shaw 22 May '12

22 May '12

I am pleased to annouce the release of 'reform'. A full tutorial is available here: http://www.happstack.com/docs/crashcourse/Reform.html Reform is an HTML form generation and validation library. It follows in the footsteps of formlets and digestive-functors <= 0.2. In fact, much of the code in reform comes from the digestive-functors-0.2 code base. Reform is designed to be usuable with a wide variety of Haskell web servers and templating libraries. You can find the following packages on hackage: * reform - the core library * reform-happstack - support for using reform with the Happstack server * reform-blaze - support for creating forms for blaze-html * reform-hsp - support for creating forms for HSP (another xml/html template library) The source code is available via darcs: darcs get http://patch-tag.com/r/stepcut/reform The darcs repo also includes proof-of-concept support for 'Heist'. Reform will feel very familiar to formlets and digestive-functors <= 0.2 users. The primary motivation behind this library is to provide a supported alternative to digestive-functors 0.2 for users that prefer 0.2 over 0.3. The key new feature in reform is the ability to separate the validation code from the view generation code. This allows library authors to provide validators (known as Proofs) which the users can use when constructing their forms. The proof names appear in the type-signatures. This allows the library author to ensure that the value returned by a user created form is not merely the correct type, but has also passed validation. The reform-happstack package also provides simple and transparent Cross-Site Request Forgery (CSRF) protection, using the double-submit method. This method has some weaknesses. For example, I believe it can be circumvented if your site is vulnerable to cross-site scripting (XSS) attacks. If you have suggestions on how to improve the CSRF protection -- please let us know! I hope to do a full comparison of reform vs digestive-functors 0.3 vs yesod forms in a few weeks. - jeremy

3 3

Zipper and Comonad
by Mathijs Kwik 22 May '12

22 May '12

Hi all, After using zippers for a while, I wanted to dig a bit deeper into them. I found there is some relation between Zipper and Comonad, but this confuses me somewhat. After reading a bit more about Comonads [1] and [2], I think I understand them somewhat, and I see how they too are useful for navigating a data structures and giving functions the ability to "look around". What confuses me though, is the relation between these 2. This source [3] mentions all zippers can be made instances of Comonad, and demonstrates how to do this for simple, 1-dimensional (list) zippers. But a comment on [4] says a Zipper by itself is already an application of Comonad. I want to find out which is the case. Looking at the types does not yield me a solution yet. This is Zipper from LYAH: data Tree a = Empty | Node a (Tree a) (Tree a) data Crumb a = LeftCrumb a (Tree a) | RightCrumb a (Tree a) type Breadcrumbs a = [Crumb a] type Zipper a = (Tree a, Breadcrumbs a) This is Comonad from the comonad package (flattened to 1 class): class Functor w => Comonad w where duplicate :: w a -> w (w a) extend :: (w a -> b) -> w a -> w b extract :: w a -> a Now, if [3] is correct, I can write "instance Comonad Zipper". If I understood all this correctly, "extend" becomes "(Zipper a -> b) -> Zipper a -> Zipper b". This gives me something like a "look-around fmap" which sounds useful. If the comment on [4] is correct though, Zipper somehow has a Comonad "built-in", (probably hidden the interaction between Tree and [Crumb]). So in that case, a Zipper would be a (somewhat customized) "instance Comonad Tree" with some extensions. "(Tree a -> b) -> Tree a -> Tree b" seems reasonable. It will build up a new tree with the same shape as the input tree, and allows the mapping function to examine every node _and_ its child nodes. It does not allow "looking up" though. So what do I make of this? It's clear that every Zipper can be a Comonad, and it's probably useful in some cases, but on the other hand, a Zipper already gives the ability to look around and modify (a -> a) things, so the comonadic instance only allows you to do this in a somewhat structure-preserving way. It's still not clear to me whether there is some truth in "a Zipper itself is an application of Comonad". What I looked at above is just a Tree instance, which obviously lost power compared to a full Zipper. But I somehow feel there indeed is a somewhat deeper relation between these 2 compared to just "can be made instance of". Please share your thoughts. Thanks, Mathijs [1] http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html [2] http://blog.sigfpe.com/2008/03/comonadic-arrays.html [3] http://blog.sigfpe.com/2007/01/monads-hidden-behind-every-zipper.html [4] http://gelisam.blogspot.com/2007/04/i-understand-comonads.html

3 2

Data.Array.Unboxed in GHC 7.4
by Tom Nielsen 22 May '12

22 May '12

Dear cafe, I have just upgraded to GHC 7.4, and now I run into some compilation problems. Specifically, I have a package that needs both Data.Array.Unboxed and System.IO.Unsafe. But I cannot enable both base and haskell98 in a cabal file. is there any way out of this? If I enable both haskell98 and base, I get Query.hs:1:1: Ambiguous module name `Prelude': it was found in multiple packages: base haskell98-2.0.0.1 cabal: Error: some packages failed to install: as documented elsewhere (http://hackage.haskell.org/trac/ghc/ticket/4958) With haskell98 replacing base, I get Query.hs:55:8: Could not find module `System.IO.Unsafe' It is a member of the hidden package `base'. Perhaps you need to add `base' to the build-depends in your .cabal file. Use -v to see a list of the files searched for. cabal: Error: some packages failed to install: and without haskell98 or array, cabal tells me to add those to .cabal build-depends. So how can I use the Data.Array.Unboxed package together with all the stuff from base that is not in haskell98? Thanks, Tom

1 1

Large graphs
by Benjamin Ylvisaker 21 May '12

21 May '12

I have a problem that I'm trying to use Haskell for, and I think I'm running into scalability issues in FGL. However, I am quite new to practical programming in Haskell, so it's possible that I have some other bone-headed performance bug in my code. I tried looking around for concrete information about the scalability of Haskell's graph libraries, but didn't find much. So here are the characteristics of the problem I'm working on: - Large directed graphs. Mostly 10k-100k nodes, but some in the low 100ks. - Sparse graphs. The number of edges is only 2-3x the number of nodes. - Immutable structure, mutable labels. After initially reading in the graphs, their shape doesn't change, but information "flows" around the graph, changing the labels on nodes and edges. I wrote some code that reads in graphs and some some basic flow computations on them. The first few graphs I tried were around 10k nodes, and the performance was okay (on the order of several seconds). When I tried some larger graphs (~100k), the memory consumption spiked into multiple GB, the CPU utilization went down to single digit percentages and the overall running time was closer to hours than seconds. Because the graph structure is basically immutable for my problem, I'm tempted to write my own graph representation based on mutable arrays. Before I embark on that, I wonder if anyone else can share their experience with large graphs in Haskell? Is there a library (FGL or otherwise) that should be able to scale up to the size of graph I'm interested in, if I write my code correctly? Thanks, Ben

4 4

Mighttpd 2.6.0 has been released
by Kazu Yamamoto 20 May '12

20 May '12

Hello cafe, I have released Mighttpd 2.6.0: http://mew.org/~kazu/proj/mighttpd/en/ Some users started using Mighttpd 2 and I was requested to implement missing features for real world operation. So, I implemented the following features in Mighttpd 2.6.0: - Route file reloading - Graceful shutdown for upgrading - URL rewriting (with HTTP redirection) For more information, please read the homepage above. I would like to thank Michael Snoyman for merging the necessary patch to warp. Regards, --Kazu

1 0

Cardinal Haskell RBTree? And structural sharing.
by Matt Lamari 20 May '12

20 May '12

I dug this haskell code of the internet wayback machine. Don't worry, Dons - it may be old; but it's still Golden. . . it seems to be from the Okasaki book with a working delete and key-value variant: http://web.archive.org/web/20100629235553/http://www.cse.unsw.edu.au/~dons/… I'm still at the lower end of Haskell expertise; but I can read this, and am porting the concept into my Heresy library for CL. The algorithm seems to be proven via some haskell static means (that I don't fully understand); but it also holds up to my heavy unit tests. What I value from functional containers, though, is that the modded structure shares the bulk of its identity/nodes with the prior variant. However, I added sharing as a metric to my unit test, so it can also discover when a new (by identity) node exists in the modified/new reference that is logically analogous to a node the old/prior one. . . . . which would waste space if people are holding various references to evolving containers. When purely translating this code, even in zero-change cases, one function will build a red node from a black, only to have the caller use *that* to build a brand new black - as across the 2 levels it has no way of seeing that the optimal node is merely the original node. Through some fundamental changes, and a bit of "whack a mole" (especially in the delete case) I *think* I caught and removed them all. . . . Anyway, my point: It seems that these containers can be analyzed with respect to their pure algorithm/logical correctness; but also structural storage. Is there much talk on that side of the issue? Is there any cardinal reference for this or similar data structures with the storage issue resolved? I'd be interested in looking at another implementation, especially one where the size issue isn't just tested; but proven. . . .

1 0