- Haskell-Cafe - Haskell.org

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

darcs patch dependencies in dot format
by Sönke Hahn 20 May '12

20 May '12

Hi all! Yesterday I wrote a little tool to output the dependencies of darcs patches in dot format. The hardest part was to wrap my head around the darcs API and find a way to let it compute the patch dependencies. I don't know, if I got it right, but it looks correct at first glance. Here is the code: https://patch-tag.com/r/shahn/darcs2dot To use it just execute the program in a darcs repo and it will output a dot graph to stdout. The graph does not contain all dependencies, but the transitive reduction. The patch names are truncated at 15 characters. And here is an example graph: http://open-projects.net/~shahn/patchDeps.pdf These are the patch dependencies of one of my darcs repos (https://patch-tag.com/r/shahn/hate) Some observations I made: * There are two completely separate subgraphs. One subgraph seems to be for the testsuite, the other for the actual code. This means, the two don't depend on each other and could easily be put in two distinct repos. * There is a "re-implementation" patch with a lot of incoming and outgoing edges. (Which makes sense.) * There are some sequences of patches (e.g. these four "allow ..." patches in the upper left corner) that seem to contain related patches. * darcs's patch system is awesome! Any comments or suggestions? Cheers, Sönke

10 15

How to write Source for TChan working with LC.take?
by Hiromi ISHII 20 May '12

20 May '12

Hello, there. I'm writing a Source to supply values from TChan. I wrote three implementations for that goal as follows: ~~~~ import Data.Conduit import qualified Data.Conduit.List as LC import Control.Monad.Trans import Control.Concurrent.STM import Control.Monad sourceTChanRaw :: MonadIO m => TChan a -> Source m a sourceTChanRaw ch = pipe where pipe = PipeM next (return ()) next = do o <- liftIO $ atomically $ readTChan ch return $ HaveOutput pipe (return ()) o sourceTChanState :: MonadIO m => TChan a -> Source m a sourceTChanState ch = sourceState ch puller where puller ch = StateOpen ch `liftM` (liftIO . atomically $ readTChan ch) sourceTChanYield :: MonadIO m => TChan a -> Source m a sourceTChanYield ch = forever $ do ans <- liftIO . atomically $ readTChan ch yield ans ~~~~ Namely, one using raw Pipe constructors directly, using `sourceState` and `yield`. I tested these with GHCi. ~~~~ ghci> ch <- newTChanIO :: IO (TChan ()) ghci> atomically $ replicateM_ 1500 $ writeTChan ch () ghci> sourceTChanRaw ch $$ LC.take 10 [(),(),(),(),(),(),(),(),(),()] ghci> sourceTChanState ch $$ LC.take 10 [(),(),(),(),(),(),(),(),(),()] ghci> sourceTChanYield ch $$ LC.take 10 *thread blocks* ~~~~ First two versions' result is what I exactly expected but the last one not: the source written with `yield` never returns value even if there are much enough value. I also realized that following code runs perfectly as I expected: ~~~~ ghci> ch <- newTChanIO :: IO (TChan ()) ghci> atomically $ replicateM_ 1500 $ writeTChan ch () ghci> sourceTChanRaw ch $= LC.isolate 10 $$ LC.mapM_ print [(),(),(),(),(),(),(),(),(),()] ghci> sourceTChanState ch $= LC.isolate 10 $$ LC.mapM_ print [(),(),(),(),(),(),(),(),(),()] ghci> sourceTChanYield ch $= LC.isolate 10 $$ LC.mapM_ print [(),(),(),(),(),(),(),(),(),()] ~~~~ So, here is the question: Why the Source using `yield` doesn't work as expected with LC.take? Or, might be Semantically, what behaviour should be expected for LC.take? Thanks, -- Hiromi ISHII konn.jinro(a)gmail.com

1 0

Is protocol-buffers package maintainer reachable?
by Chris Kuklewicz 19 May '12

19 May '12

To those looking for me: I live! And I got reminded to get back in touch via http://www.well-typed.com/blog/66 (kudos to them!). protocol-buffers is updated, now on to regex-*

1 0

Protocol Buffers 2.0.7
by Chris Kuklewicz 19 May '12

19 May '12

I have returned from the shadows of the intenet to maintain some packages! Version 2.0.7 of protocol-buffers (3 packages) has been uploaded to hackage. This makes it compile with ghc-7.4.1 and handle missing package names better. Thanks to everyone who sent email and patches, including Nathan Howell, Alexey Khudyakov, Howard B. Golden, Bryan O'Sullivan, Michael Stone, Daniel Rebelo de Oliveira, Paul Graphov, Tsurann, Sergei Trofimovich, Yitzchak Gale. The usual hackage links: http://hackage.haskell.org/package/hprotoc http://hackage.haskell.org/package/protocol-buffers-descriptor http://hackage.haskell.org/package/protocol-buffers And the darcs repo is at: http://code.haskell.org/protocol-buffers/ Q: What is protocol-buffers? A: It is a Haskell version of Google's protocol buffer wire protocol, see http://code.google.com/p/protobuf/ for a full description. Q: What does the hprotoc executable do? A: It convers "protocol-buffer descriptor files" into Haskell code to implement those data messages. Q: What does the protocol-buffers library do? A: It is the runtime API for using the binary protocol, serializing and deserializing the data types generated by hprotoc. Q: What is the protocol-buffers-descriptor library do? A: It is the support library for parsing "protocol-buffer descriptor files" into data structures. Most of this code is generated by hprotoc from a "protocol-buffer descriptor file" for "protocol-buffer descriptor files". Yes, it had to be bootstrapped. -- Dr. Chris Kuklewicz

1 0

ANNOUNCE: time-lens-0.1
by Roman Cheplyaka 19 May '12

19 May '12

I'm happy to announce the first, experimental version of the time-lens library. http://hackage.haskell.org/package/time-lens https://github.com/feuerbach/time-lens Its goal is to simplify working with time and date data structures in Haskell by providing lens-based overloaded accessors for Data.Time types. E.g. to find the current hour you currently need to write something like todHour . localTimeOfDay . zonedTimeToLocalTime <$> getZonedTime With time-lens it becomes getL hours <$> getZonedTime The difference is even more impressive when you need to *update* the hour in a ZonedTime structure, but admittedly such a need is relatively rare. The library is pure Haskell 2010 code. It is also completely type-compatible with Data.Time, so it's very easy to start using it in existing projects. -- Roman I. Cheplyaka :: http://ro-che.info/

1 0

Re: [Haskell-cafe] Can Haskell outperform C++?
by Janis Voigtländer 19 May '12

19 May '12

Am 19.05.2012 12:00, schrieb wren ng thornton: > Exactly. That's what I was trying to get at re the problems of comparing > Haskell to C++ (or indeed any pair of dissimilar languages). A > legitimate comparison will involve far more than microbenchmarks, but > then a legitimate comparison must always have a specific focus and > context in order to be able to say anything interesting. The problems I > see in language comparisons is that by and large they tend not to have > any such focus[1], and consequently they shed little light on how the > languages compare and shed a bit of darkness by serving only to confirm > initial biases. > > > [1] A nice counter-example to this trend are papers like: > > http://www.cse.unsw.edu.au/~chak/papers/modules-classes.pdf > > There was another one comparing the expressivity of Java-style > polymorphism vs Haskell-style polymorphism, based on an analysis of > in-the-wild code; but I can't seem to pull it up at the moment. Possibly "Software extension and integration with type classes" by Lämmel and Ostermann? http://doi.acm.org/10.1145/1173706.1173732 Best, Janis. -- Jun.-Prof. Dr. Janis Voigtländer http://www.iai.uni-bonn.de/~jv/

1 0

Can Haskell outperform C++?
by Isaac Gouy 19 May '12

19 May '12

Wed May 16 16:40:26 CEST 2012, Gregg Lebovitz wrote: 2) ... I think the problem with current comparisons, is that they are designed to favor imperative languages. Please be specific: - Which current comparisons? - How do you know what they are designed to favor?

5 10