- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] [Haskell-beginners] Graph Coloring Library?
by KC 14 Jul '12

14 Jul '12

This may help: - use hMatrix to find the eigenvalues of the adjacency matrix Then by the following theorems: "An upper bound on the chromatic number in terms of eigenvalues was discovered by Wilf(1967). Chromatic Number(G) <= 1 + lambda_1(G) Hoffman (1977) discovered a lower bound on the chromatic number in terms of the smallest and largest eigenvalue. Chromatic Number(G) >= 1 - (lambda_1/lambda_n) for n>=2." >From "The Mutually Beneficial Relationship of Graphs and Matrices", Richard A. Brualdi,CBMS Series,Number 115, 2011. On Fri, Jul 13, 2012 at 1:43 PM, Alec Story <avs38(a)cornell.edu> wrote: > I have a problem where I need to find the smallest k-coloring for a graph > that represents conflicts between objects. Is there a Haskell library that > will do this for me? I'm not particularly concerned about speed, and it's > unlikely that I'll generate really bad edge cases, but I'd prefer to do > something other than write the really bad try-every-case algorithm. > > -- > Alec Story > Cornell University > Biological Sciences, Computer Science 2012 > > _______________________________________________ > Beginners mailing list > Beginners(a)haskell.org > http://www.haskell.org/mailman/listinfo/beginners > > -- -- Regards, KC

1 0

ANNOUNCE: hspec-1.3.0
by Simon Hengel 14 Jul '12

14 Jul '12

Hi, hspec-1.3.0 is out [1]. This release comes with two major new features: - BDD-style combinators to make assertions [2] - Automatic test discovery [3] Test.Hspec now exports parts of the monadic API and the new BDD-style combinators. You can use Test.Hspec.Core as a drop-in replacement for legacy code. The full release notes are here at [4]. A basic introduction to Hspec is at [5]. Feedback is very welcome! Cheers, Simon [1] http://hackage.haskell.org/package/hspec [2] https://github.com/sol/hspec-expectations#readme [3] https://github.com/hspec/hspec/tree/master/hspec-discover#readme [4] https://github.com/hspec/hspec/blob/master/CHANGES.markdown [5] http://hspec.github.com/

1 0

Re: [Haskell-cafe] [Haskell-beginners] Graph Coloring Library?
by KC 14 Jul '12

14 Jul '12

On Hackage there is the Graphalyze package but it doesn't seem to do vertex coloring. Are you talking about undirected graphs? On Sat, Jul 14, 2012 at 12:23 PM, Alec Story <avs38(a)cornell.edu> wrote: > I'd prefer an exact solution, but it doesn't have to be particularly > performant (this is research code). > > The graphs are pretty small in general, all my test cases will have < 10 > nodes, but have high connectivity. They don't have any special properties. > On Jul 14, 2012 2:50 PM, "KC" <kc1956(a)gmail.com> wrote: > >> Are you looking for an exact or approximate solution. >> >> How many nodes and edges? >> >> Any special properties that the graph has? >> >> >> On Fri, Jul 13, 2012 at 1:43 PM, Alec Story <avs38(a)cornell.edu> wrote: >> >>> I have a problem where I need to find the smallest k-coloring for a >>> graph that represents conflicts between objects. Is there a Haskell >>> library that will do this for me? I'm not particularly concerned about >>> speed, and it's unlikely that I'll generate really bad edge cases, but I'd >>> prefer to do something other than write the really bad try-every-case >>> algorithm. >>> >>> -- >>> Alec Story >>> Cornell University >>> Biological Sciences, Computer Science 2012 >>> >>> _______________________________________________ >>> Beginners mailing list >>> Beginners(a)haskell.org >>> http://www.haskell.org/mailman/listinfo/beginners >>> >>> >> >> >> -- >> -- >> Regards, >> KC >> > -- -- Regards, KC

1 0

RFCQ: The Classy Prelude: a more fully polymophic, drop-in alternative prelude http://www.yesodweb.com/blog/2012/07/classy-prelude
by Max Cantor 13 Jul '12

13 Jul '12

I'd like to share Michael Snoyman's Classy Prelude: http://www.yesodweb.com/blog/2012/07/classy-prelude . The basic gist of the work is that many of the standard prelude functions are made for concrete types such as [a], [(a,b)], and [Char] but can be much more polymorphic. While this complicates error messages and makes learning Haskell more difficult, we believe experienced Haskellers will benefit from the added polymorphism. Note that we aren't saying that the standard Prelude should be replaced, rather we are offering this as a drop-in alternative. Note that it reexports most of the standard Prelude types so it should be very low impact to switch over. We love to hear your comments. Note however, that this is a RFCQ with the 'C' standing for constructive.. Thanks, Max

1 0

Monads with "The" contexts?
by Takayuki Muranushi 13 Jul '12

13 Jul '12

tl;dr: Is there any way to pass the Supercombinator level names (the names in haskell source codes with zero indent) as context to a Monad so that it will read from "The" context? Hello, everyone. I'm thinking of representing our knowledge about our life, the universe and everything as Haskell values. I'd also like to address the uncertainties in our knowledge. The uncertainties are usually continuous (probabilistic distributions) but that's another story. Please forget about it for a while. We learned that List is for nondeterministic context. > earthMass, sunMass, marsMass :: [Double] Let's pretend that there are large uncertainty in our knowledge of the Earth mass. > earthMass = [5.96e24, 5.97e24, 5.98e24] Let's also pretend that we can measure the other bodys' masses only by their ratio to the earth mass, and the measurements have large uncertainties. > sunMass = (*) <$> [2.5e5, 3e5, 4e5] <*> earthMass > marsMass = (*) <$> [0.01, 0.1, 1.0] <*> earthMass Then, how many Mars mass object can we create by taking the sun apart? > sunPerMars :: [Double] > sunPerMars = (/) <$> sunMass <*> marsMass Sadly, this gives too many answers, and some of them are wrong because they assume different Earth mass in calculating Sun and Mars masses, which led to inconsistent calculation. *Main> length $ sunPerMars 81 We had to do this way; > sunMass' e = map (e*) [2.5e5, 3e5, 4e5] > marsMass' e = map (e*) [0.01, 0.1, 1.0] > sunPerMars' :: [Double] > sunPerMars' = do > e <- earthMass > (/) <$> sunMass' e <*> marsMass' e to have correct candidates (with duplicates.) *Main> length $ sunPerMars' 27 The use of (e <- earthMass) seems inevitable for representing that the two Earth masses are taken from the same source of nondeterminism. However, as the chain of the reasoning grows, we can easily imagine the function arguments will grow impractically large. To get the Higgs mass, we will need to feed them all the history of research that led to the measurement of it. There is "the" source of nondeterminism for Earth mass we will always use. Is there a way to represent this? For example, can we define earthMass'' , sunMass'' , marsMass'' all in separate modules, and yet have (length $ sunPerMars'' == 27) ? By the way, *Main> length $ nub $ sort sunPerMars' 16 is not 9. That's another story, I said! Thanks in advance. -- Takayuki MURANUSHI The Hakubi Center for Advanced Research, Kyoto University http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html

3 3

ghci and TH cannot: unknown symbol `stat64`
by Michael Snoyman 13 Jul '12

13 Jul '12

Hi all, A quick search indicates that this problem has come up in the past, but I haven't seen any solutions yet. I'm working on the next Persistent release, and one of the changes is that the included sqlite3 C library has been updated (I believe that's the trigger here). I can compile programs against persistent-sqlite, but if there's TH code involved, or I try to runghc the file, I get an error message like: test.hs: /home/ubuntu/.cabal/lib/persistent-sqlite-1.0.0/ghc-7.4.1/HSpersistent-sqlite-1.0.0.o: unknown symbol `stat64' test.hs: test.hs: unable to load package `persistent-sqlite-1.0.0' I'm running GHC 7.4.1 on Ubuntu 12.04 64-bit. Does anyone have insight into what might be causing this? Thanks, Michael

4 11

haskell.org is so fragile
by Takayuki Muranushi 13 Jul '12

13 Jul '12

Today I have observed that hackage.haskell.org/ timeout twice (in the noon and in the evening.) What is the problem? Is it that haskell users have increased so that haskell.org is overloaded? That's very good news. I am eager to donate some money if it requires server reinforcement. Sincerely, -- Takayuki MURANUSHI The Hakubi Center for Advanced Research, Kyoto University http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html

6 5

Monads with "The" contexts?
by oleg＠okmij.org 13 Jul '12

13 Jul '12

Tillmann Rendel has correctly noted that the source of the problem is the correlation among the random variables. Specifically, our measurement of Sun's mass and of Mars mass used the same rather than independently drawn samples of the Earth mass. Sharing (which supports what Functional-Logic programming calls ``call-time choice'') is indeed the solution. Sharing has very clear physical intuition: it corresponds to the collapse of the wave function. Incidentally, a better reference than our ICFP09 paper is the greatly expanded JFP paper http://okmij.org/ftp/Computation/monads.html#lazy-sharing-nondet You would also need a generalization of sharing -- memoization -- to build stochastic functions. The emphasis is on _function_: when applied to a value, the function may give an arbitrary sample from a distribution. However, when applied to the same value again, the function should return the same sample. The general memo combinator is implemented in Hansei and is used all the time. The following article talks about stochastic functions (and correlated variables): http://okmij.org/ftp/kakuritu/index.html#all-different and the following two articles show just two examples of using memo: http://okmij.org/ftp/kakuritu/index.html#noisy-or http://okmij.org/ftp/kakuritu/index.html#colored-balls The noisy-or example is quite close to your problem. It deals with the inference in causal graphs (DAG): finding out the distribution of conclusions from the distribution of causes (perhaps given measurements of some other conclusions). Since a cause may contribute to several conclusions, we have to mind sharing. Since the code works by back-propagation (so we don't have to sample causes that don't contribute to the conclusions of interest), we have to use memoization (actually, memoization of recursively defined functions).

1 0

Another topic of ghc --make/ghci differences
by Andrey Yankin 12 Jul '12

12 Jul '12

1. I wrote this: -----8<----- test.hs --- module Main where import qualified Graphics.UI.GLFW as GLFW main = do True <- GLFW.initialize print =<< GLFW.openGLProfile print =<< GLFW.getGlfwVersion print =<< GLFW.getGlVersion print "Trying to open the window" result <- GLFW.openWindow GLFW.defaultDisplayOptions print result -----8<----- 2. Compiled like this: ghc --make -o test test.hs 3. Executed: ./test DefaultProfile Version {versionBranch = [2,7,2], versionTags = []} Version {versionBranch = [0,0,0], versionTags = []} "Trying to open the window" True 4. Window appeared. 2'. Executed in GHCI like this: ghci -fno-ghci-sandbox Prelude> :l test.hs Prelude> main 3'. Get (random numbers as GLVersion): Loading package GLFW-b-0.1.0.2 ... linking ... done. DefaultProfile Version {versionBranch = [2,7,2], versionTags = []} Version {versionBranch = *[34972080,-1323041296,-1334802519]*, versionTags = []} "Trying to open the window" False 4'. Window didn't appear. What should I do to get GLFW window in ghci too? What do I do wrong?

1 1

Bad interface problem.
by Magicloud Magiclouds 12 Jul '12

12 Jul '12

Hi, This had never happened to me. And I have no idea what to do. $ cabal --upgrade-dependencies --enable-documentation --force-reinstalls --solver=topdown QuickCheck-2.5 Test/QuickCheck/All.hs:15:1: Bad interface file: /home/magicloud/.cabal/lib/template-haskell-2.6.0.0/ghc-7.4.2/Language/Haskell/TH.hi Something is amiss; requested module template-haskell-2.6.0.0:Language.Haskell.TH differs from name found in the interface file template-haskell:Language.Haskell.TH $ cabal --version cabal-install version 0.15.0 using version 1.15.0 of the Cabal library -- 竹密岂妨流水过山高哪阻野云飞 And for G+, please use magiclouds#gmail.com.

4 8