News aggregator

accessing the RTS -M flag value from GHC.RTS.Flags

haskell-cafe - Tue, 04/05/2016 - 9:46pm
Given, import GHC.RTS.Flags main = do gcf <- getRTSFlags print (maxHeapSize (gcFlags gcf)) And running on x86-64 in GHC 7.10.3, $ ./ghcflags 0 $ ./ghcflags +RTS -M1M 256 $ ./ghcflags +RTS -M1024K 256 $ ./ghcflags +RTS -M4096K 1024 Is there anyway I can get access to the value stored in the -M flag and depend on that value being correct? I was not able find it in the user's guide or anywhere else for that matter. Thanks, Adam
Categories: Offsite Discussion

Text.Regex.matchRegex: Success is empty?

haskell-cafe - Tue, 04/05/2016 - 9:16pm
Esteemed Haskellers, It is working for me, but I am puzzled by the matchRegex function: > import Text.Regex > :i matchRegex matchRegex :: Regex -> String -> Maybe [String] -- Defined in ‘Text.Regex’ Searches that fail return Nothing: > matchRegex (mkRegex "z") "abracadabra" Nothing which makes sense. But why do searches that succeed return an empty list of Strings? > matchRegex (mkRegex "a") "abracadabra" Just [] >
Categories: Offsite Discussion

Documenting extensions

haskell-cafe - Tue, 04/05/2016 - 9:12pm
I'd like to believe the Haskell report is a bible. I learned H98 using the Prelude as a source of examples and Hugs as a testbed. That was a comfortable and rewarding combination. Later I discovered that by default GHC rejected almost all my report-conforming (H98 and H2010) code. Ironically, its website at the time asserted, "Haskell is a standard language." In fact, far from reflecting biblical authority, the de facto Haskell discussed in this cafe comes in some 2^99 flavors -- enough to use a different language for every run of the compiler for the life of the universe. Witness: ghc --supported-languages | grep -v '^No[A-Z]' | wc -l (99 is the answer for GHC 7.8.4. In fact not all combinations of -X options are legal, but you get the point.) Unfortunately there is no coherent discussion of all those Haskells. The extensions section of the GHC User Guide gives no formal syntax, often teaches semantics only by example, and is replete with sales pitches, partial analogies, inconsistent terminology, an
Categories: Offsite Discussion

Brent Yorgey: The network reliability problem and star semirings

Planet Haskell - Tue, 04/05/2016 - 7:28pm

In a previous post I defined the network reliability problem. Briefly, we are given a directed graph whose edges are labelled with probabilities, which we can think of as giving the likelihood of a message successfully traversing a link in a network. The problem is then to compute the probability that a message will successfully traverse the network from a given source node to a given target node.

Several commenters pointed out the connection to Bayesian networks. I think they are right, and the network reliability problem is a very special case of Bayesian inference. However, so far this hasn’t seemed to help very much, since the things I can find about algorithms for Bayesian inference are either too general (e.g. allowing arbitrary functions at nodes) or too specific (e.g. only working for certain kinds of trees). So I’m going to put aside Bayesian inference for now; perhaps later I can come back to it.

In any case, Derek Elkins also made a comment which pointed to exactly what I wanted to talk about next.

Star semirings and path independence

Consider the related problem of computing the reliability of the single most reliable path from to in a network. This is really just a disguised version of the shortest path problem, so one can solve it using Dijkstra’s algorithm. But I want to discuss a more general way to think about solving it, using the theory of star semirings. Recall that a semiring is a set with two associative binary operations, “addition” and “multiplication”, which is a commutative monoid under addition, a monoid under multiplication, and where multiplication distributes over addition and . A star semiring is a semiring with an additional operation satisfying . Intuitively, (though can still be well-defined even when this infinite sum is not; we can at least say that if the infinite sum is defined, they must be equal). If is a star semiring, then the semiring of matrices over is also a star semiring; for details see Dolan (2013), O’Connor (2011), Penaloza (2005), and Lehmann (1977). In particular, there is a very nice functional algorithm for computing , with time complexity (Dolan 2013). (Of course, this is slower than Dijkstra’s algorithm, but unlike Dijkstra’s algorithm it also works for finding shortest paths in the presence of negative edge weights—in which case it is essentially the Floyd-Warshall algorithm.)

Now, given a graph and labelling , define the adjacency matrix to be the matrix of edge probabilities, that is, . Let be the star semiring of probabilities under maximum and multiplication (where , since ). Then we can solve the single most reliable path problem by computing over this semiring, and finding the largest entry. If we want to find the actual most reliable path, and not just its reliability, we can instead work over the semiring , i.e. probabilities paired with paths. You might enjoy working out what the addition, multiplication, and star operations should be, or see O’Connor (2011).

In fact, as shown by O’Connor and Dolan, there are many algorithms that can be recast as computing the star of a matrix, for an appropriate choice of semiring: for example, (reflexive-)transitive closure; all-pairs shortest paths; Gaussian elimination; dataflow analysis; and solving certain knapsack problems. One might hope that there is similarly an appropriate semiring for the network reliability problem. But I have spent some time thinking about this and I do not know of one.

Consider again the simple example given at the start of the previous post:

For this example, we computed the reliability of the network to be , by computing the probability of the upper path, , and the lower path, , and then combining them as , the probability of success on either path less the double-counted probability of simultaneous success on both.

Inspired by this example, one thing we might try would be to define operations and . But when we go to check the semiring laws, we run into a problem: distributivity does not hold! , but . The problem is that the addition operation implicitly assumes that the events with probabilities and are independent: otherwise the probability that they both happen is not actually equal to . The events with probabilities and , however, are not independent. In graph terms, they represent two paths with a shared subpath. In fact, our example computation at the beginning of the post was only correct since the two paths from to were completely independent.

Graph reduction

We can at least compute the reliability of series-parallel graphs whose terminals correspond with and :

  • If consists of a single edge, return that edge’s probability.
  • Otherwise, is a composition of two subgraphs, whose reliabilities we recursively compute. Then:
    • If is a sequential composition of graphs, return the product of their reliabilities.
    • If is a parallel composition of two graphs with reliabilities and , return .

In the second case, having a parallel composition of graphs ensures that there are no shared edges between them, so and are indeed independent.

Of course, many interesting graphs are not series-parallel. The simplest graph for which the above does not work looks like this:

Suppose all the edges have probability . Can you find the reliability of this network?

More in a future post!

References

Dolan, Stephen. 2013. “Fun with Semirings: A Functional Pearl on the Abuse of Linear Algebra.” In ACM SIGPLAN Notices, 48:101–10. 9. ACM.

Lehmann, Daniel J. 1977. “Algebraic Structures for Transitive Closure.” Theoretical Computer Science 4 (1). Elsevier: 59–76.

O’Connor, Russell. 2011. “A Very General Method for Computing Shortest Paths.” http://r6.ca/blog/20110808T035622Z.html.

Penaloza, Rafael. 2005. “Algebraic Structures for Transitive Closure.” http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.7650.


Categories: Offsite Blogs

Journal of Functional Programming - Call for PhDAbstracts

haskell-cafe - Tue, 04/05/2016 - 9:34am
If you or one of your students recently completed a PhD in the area of functional programming, please submit the dissertation abstract for publication in JFP: simple process, no refereeing, deadline 30th April 2016. Best wishes, Graham ============================================================ CALL FOR PHD ABSTRACTS Journal of Functional Programming Deadline: 30th April 2016 http://tinyurl.com/jfp-phd-abstracts ============================================================ PREAMBLE: Many students complete PhDs in functional programming each year. As a service to the community, the Journal of Functional Programming publishes the abstracts from PhD dissertations completed during the previous year. The abstracts are made freely available on the JFP website, i.e. not behind any paywall. They do not require any transfer of copyright, merely a license from the author. A dissertation is eligible for inclusion if parts of it have or could have appeared in JFP, that is, if it is in the general area of f
Categories: Offsite Discussion

Journal of Functional Programming - Call for PhD Abstracts

General haskell list - Tue, 04/05/2016 - 9:34am
If you or one of your students recently completed a PhD in the area of functional programming, please submit the dissertation abstract for publication in JFP: simple process, no refereeing, deadline 30th April 2016. Best wishes, Graham ============================================================ CALL FOR PHD ABSTRACTS Journal of Functional Programming Deadline: 30th April 2016 http://tinyurl.com/jfp-phd-abstracts ============================================================ PREAMBLE: Many students complete PhDs in functional programming each year. As a service to the community, the Journal of Functional Programming publishes the abstracts from PhD dissertations completed during the previous year. The abstracts are made freely available on the JFP website, i.e. not behind any paywall. They do not require any transfer of copyright, merely a license from the author. A dissertation is eligible for inclusion if parts of it have or could have appeared in JFP, that is, if it is in the general area of f
Categories: Incoming News

Call for papers for David Turner's Festschrift issue ofJUCS

General haskell list - Tue, 04/05/2016 - 9:07am
Friends David Turner was one of the two people who changed my life by introducing me to functional programming (*). David designed and implemented a succession of functional languages, Sasl, KRC, and Miranda, that made lazy functional programming into a tool you could use to get work done. They all used SK-combinator reduction in their implementations, a technique of irresistibly simple beauty, invented by Curry and Feys, but refined and popularised by David. For David’s 70th birthday, the Journal of Universal Computer Science is running a special Festschrift issue on “Functional programming: past, present, and future” in David’s honour. The Call for Papers is attached. Here’s the timetable. · 1 July 2016: Paper submissions. · 1 September 2016: Author notification. · 1 October, 2016: Revised version due. · 15 October 2016: Final notification. · 30 October 2016: Camera Ready Copy. Do consider submitting a paper. Simon (*) Arthur Norman w
Categories: Incoming News

I can no longer maintain containers

libraries list - Mon, 04/04/2016 - 12:18am
Hi all, I am writing to let you know that I am no longer able to maintain the containers package. I have enjoyed working on containers for several years, but I can no longer find the time needed for the job (with two little kids and building a house). I am not sure what is the best future of the containers package -- it could go to CLC, or it could get a new maintainer. If you look at the commit logs and on the github issues/requests, you will find out that David Feuer has a thorough understanding of the package (notably Data.Sequence) and has been competently moderating the issues/requests for some time now, so he would be the first choice. (I did not contact him sooner, so it is surprise for him as well -- sorry, David :-) Could I humbly ask David/CLC members/anyone for comments? Cheers, Milan Straka
Categories: Offsite Discussion

Names for Data.Sequence pattern synonyms

libraries list - Sun, 04/03/2016 - 1:07am
Milan Straka and I agree that we want Data.Sequence to offer pattern synonyms to make it more convenient to work with the ends of sequences. I wanted to check with everyone here what names to use. Relevant names already exposed: 1. <|, |>, and empty for cons, snoc, and empty 2. data ViewL a = EmptyL | a :< Seq a, and the equivalent on the right. I suggested Empty, :<<, and :>> as the pattern synonyms, the latter chosen for the relative convenience of the double tap. Milan suggested (correctly, I suspect) that the greater clarity of Empty, :<|, and :|> is worth the price in typing. _______________________________________________ Libraries mailing list Libraries< at >haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Categories: Offsite Discussion

A better type signature for `forM_`

libraries list - Fri, 04/01/2016 - 12:21am
Hi all, I was recently faced with some unexpected behaviour from a piece of code that type checks and has zero warnings (even with -Wall). The code is below (and depends on the hashtables package). The error was using the <$> operator instead of the =<< operator. Using the former, it just builds up a list of IO actions that never get run. As pointed out to me on IRC (thanks pjdeport), chaning the type signature of `forM_` to forM_' :: (Monad m, Foldable t) => t a -> (a -> m ()) -> m () would have resulted in an error. Yes, this change would break existing code (breaking code would require an explicit `void $` inside the `forM_`) but does anyone else think this is a good idea? Erik import Control.Monad import qualified Data.HashTable.IO as HT type EvenCache = HT.BasicHashTable Int Bool main :: IO () main = do ht <- buildTable xs <- HT.toList ht putStrLn $ "cache: length " ++ show (length xs) buildTable :: IO EvenCache buildTable = do ht <- HT.new forM_ pairs $ \ (k,v) -
Categories: Offsite Discussion

Sponsored: The 3 Week Diet

del.icio.us/haskell - Fri, 03/25/2016 - 2:00am
8 Rules of Fat Loss. Warning: Fast Results! Click Here to Watch Video...
Categories: Offsite Blogs

New gtk2hs 0.12.4 release

gtk2hs - Wed, 11/21/2012 - 12:56pm

Thanks to John Lato and Duncan Coutts for the latest bugfix release! The latest packages should be buildable on GHC 7.6, and the cairo package should behave a bit nicer in ghci on Windows. Thanks to all!

~d

Categories: Incoming News