February 2013 - Haskell-Cafe

Thunks and GHC pessimisation
by Tom Ellis 25 Feb '13

25 Feb '13

To avoid retaining a large lazy data structure in memory it is useful to hide it behind a function call. Below, "many" is used twice. It is hidden behind a function call so it can be garbage collected between uses. That's good. When compiling with "-O" it seems that GHC 7.4.1 decides to keep it in memory anyway. That's bad. (I can't read core so I don't know exactly what's going on). Replacing one of the "many" in "twice" with "different_many" makes everything fine again. Is this considered a bug in GHC? Is it a known bug? It is incredibly concerning that GHC would perform this kind of pessimisation. Tom % cat thunkfail.hs {-# OPTIONS_GHC -fno-warn-unused-binds #-} import Data.List million :: Int million = 10 ^ (6 :: Int) many :: () -> [Int] many () = [1..million] different_many :: () -> [Int] different_many () = [1..million] twice :: (Int, Int) twice = (foldl' (+) 0 (many ()), foldl' (+) 0 (many ())) main :: IO () main = print twice % ghc -fforce-recomp -Wall -Werror -rtsopts thunkfail.hs && ./thunkfail +RTS -M5M [1 of 1] Compiling Main ( thunkfail.hs, thunkfail.o ) Linking thunkfail ... (1784293664,1784293664) % ghc -O -fforce-recomp -Wall -Werror -rtsopts thunkfail.hs && ./thunkfail +RTS -M5M [1 of 1] Compiling Main ( thunkfail.hs, thunkfail.o ) Linking thunkfail ... Heap exhausted; Current maximum heap size is 5242880 bytes (5 MB); use `+RTS -M<size>' to increase it.

3 5

Tournament knock out
by Xinyu LIU 25 Feb '13

25 Feb '13

Hi, Tournament knock out is explained in [1] by Knuth. The limitation is that it can only handle the sequence of the length 2^m for some integer m. When the champion element is removed, it was replaced with negative infinity. Typically negative infinity is represented by a predefined big negative number. Although heap sort solves all these limitation, I found tournament knock out itself can work out. Here is the Haskell code: data Infinite a = NegInf | Only a | Inf deriving (Eq, Show, Ord) only (Only x) = x data Tr a = Empty | Br (Tr a) a (Tr a) deriving Show key (Br _ k _ ) = k wrap x = Br Empty (Only x) Empty branch t1 t2 = Br t1 (min (key t1) (key t2)) t2 fromList :: (Ord a) => [a] -> Tr (Infinite a) fromList = build . (map wrap) where build [] = Empty build [t] = t build ts = build $ pair ts pair (t1:t2:ts) = (branch t1 t2):pair ts pair ts = ts pop (Br Empty _ Empty) = Br Empty Inf Empty pop (Br l k r) | k == key l = let l' = pop l in Br l' (min (key l') (key r)) r | k == key r = let r' = pop r in Br l (min (key l) (key r')) r' top = only . key tsort :: (Ord a) => [a] -> [a] tsort = sort' . fromList where sort' Empty = [] sort' (Br _ Inf _) = [] sort' t = (top t) : (sort' $ pop t) The detailed explanation can be found at: https://github.com/liuxinyu95/AlgoXY/blob/algoxy/preview/ssort-en.pdf?raw=t… [1]. Donald E. Knuth. The art of computer programming, Volume 3, sorting and searching. Larry, LIU Xinyu https://sites.google.com/site/algoxy/ https://github.com/liuxinyu95/AlgoXY

1 0

Re: [Haskell-cafe] Parser left recursion
by wren ng thornton 24 Feb '13

24 Feb '13

On 2/24/13 7:56 AM, Kim-Ee Yeoh wrote: > On Sun, Feb 24, 2013 at 7:47 PM, Roman Cheplyaka <roma(a)ro-che.info> wrote: > >> Or perhaps you meant that the production itself, when interpreted as a >> definition, is corecursive? > > I was merely thrown off by your mention of "well-founded" and the assertion > that you're left with a "strictly smaller" input. I don't see any of this. But the problem here really is an issue of well-foundedness rather than productivity. Consider the grammar, A ::= epsilon | A B B ::= ...whatever... In order to use this grammar as-is, when processing a string we must be able to magically determine how many times to recurse in order to get our epsilon. This is magic because the correct number of times to recurse is defined by the rest of the string--- which we haven't looked at! Proof theoretically speaking, this is the same as magically knowing when to use the inductive hypothesis vs when to bottom out at a base case. Using this grammar as-is, the recursive descent parser always decides to use the inductive hypothesis. Hence, infinite loop. It should be apparent that this isn't an issue with left-recursion (when reading the string from right to left), because on left-recursion we're always consuming some of the string, and therefore the input string is getting smaller on each recursive call, and therefore it is guaranteed that we will eventually run out of string, at which point we can backtrack as necessary. The problem with right-recursion is that we never know when to stop recurring. If we stop at some arbitrary point, well maybe the parse will end up failing when it could've succeeded if only we had recursed a bit further. But recursive descent doesn't allow the kind of backtracking that would be required to exhaust the search space for right-recursion. -- Live well, ~wren

1 0

presentation on Diffusion of Innovation mentioning several times Haskell
by Luc TAESCH 24 Feb '13

24 Feb '13

Just found an Interesting presentation mixing Diffusion of Innovation with Social Patterns, mentioning several times Haskell. Good introduction to a mix of techniques for whoever interested in Haskell proselytism, and go to market strategy, http://www.taesch.com/haskell/go-to-market/introduction-to-diffusion-of-inn…

1 0

Install qtHaskell 1.1.4 using Visual Studio 2010 and GHC 7.4.2
by leonardo davinci 24 Feb '13

24 Feb '13

I am trying to install qtHaskell in Windows. I have Qt 4.8.4 (the Visual Studio 2010 version). I am following the section <<2.3.2 Windows Manual Installation>> from the userGuide of qtHaskell. I set the path as described I added the line to qt.cabal, I changed dir to qws I gave qmake -recursive and then instead of mingw32-make I gave nmake which is the equivalent for VS2010. After the compilation process finished with success I switched back to root directory of qtHaskell and I gave "runhaskell Setup.hs configure --ghc" and I took the message: "Setup.hs:1:12: Warning: -fglasgow-exts is deprecated: Use individual extensions instead Configuring qt-1.1.4... " After that I gave the command: "runhaskell Setup.hs makefile" and I got the message: "Setup.hs:1:12: Warning: -fglasgow-exts is deprecated: Use individual extensions instead unrecognised command: makefile (try --help)" Any help in order to continue? Thank in advance

1 0

Munich Haskell Meeting
by Heinrich Hördegen 24 Feb '13

24 Feb '13

Dear all, please note that our monthly Haskell get-together is scheduled on Wed, 27th Feb 2013 at 19h30 at Cafe Puck in Munich, Germany. If you plan to join, please go to http://www.haskell-munich.de/dates and click the button. Everyone interested in functional programming is welcome! I wish everyone of you, joining or not, a nice week, Heinrich

1 0

Fixing undeduceable instance ==> overlapping instance
by Michael Orlitzky 24 Feb '13

24 Feb '13

I'm trying to write a determinant function that works on matrices parameterized by their dimensions (Peano naturals). If I declare the following, -- Define a class so that we get a different determinant function -- on the base/recursive cases. class (Eq a, Ring.C a) => Determined m a where determinant :: (m a) -> a -- Base case, 1x1 matrices instance (Eq a, Ring.C a) => Determined (Mat (S Z) (S Z)) a where determinant m = m !!! (0,0) -- Recursive case, (n+2) x (n+2) matrices. instance (Eq a, Ring.C a, Arity n) => Determined (Mat (S (S n)) (S (S n))) a where determinant m = ... -- Recursive algorithm, the i,jth minor has dimension -- (n+1) x (n+1). foo bar (determinant (minor m i j)) I get an error stating that I'm missing an instance: Could not deduce (Determined (Mat (S n) (S n)) a) ... Clearly, I *have* an instance for that case: if n == Z, then it's the base case. If not, it's the recursive case. But GHC can't figure that out. So maybe if I define a dummy instance to make it happy, it won't notice that they overlap? instance (Eq a, Ring.C a) => Determined (Mat m m) a where determinant _ = undefined No such luck: >>> let m = fromList [[1,2],[3,4]] :: Mat2 Int >>> determinant m Overlapping instances for Determined (Mat N2 N2) Int arising from a use of `determinant' Matching instances: instance (Eq a, Ring.C a) => Determined (Mat m m) a -- Defined at Linear/Matrix2.hs:353:10 instance (Eq a, Ring.C a, Arity n) => Determined (Mat (S (S n)) (S (S n))) a ... I even tried generalizing the (Mat m m) instance definition so that OverlappingInstances would pick the one I want, but I can't get that to work either. Is there some way to massage this?

2 2

Need urgent help with Network.tls
by C K Kashyap 24 Feb '13

24 Feb '13

Hi, I am trying to use Haskell to download email/attachments from gmail. For which I am exploring Network.TLS. I got this sample from the net that connects to gmail smtp and works just fine - http://hpaste.org/82890 However, when I modify it a bit to try to connect to imap, it simply does not work. To debug, I tried to connect to a webserver, even that seems to not work. I modified the function as follows. emailGmail2 = do let host = "localhost" let port = 443 let params = defaultParamsClient{pCiphers = ciphers} g <- RNG.makeSystem h <- connectTo host (PortNumber (fromIntegral port)) hSetBuffering h LineBuffering cWrite h "GET / HTTP/1.0" cWrite h "" cWaitFor h "ABCD" con <- contextNewOnHandle h params g handshake con bye con And I get a "BAD request" response from the server - Can some please give me a sample code that uses Network.TLS to connect to a imap.google.com (or even a webserver for that matter)? Regards, Kashyap

5 11

Re: [Haskell-cafe] Type checking the content of a string
by Corentin Dupont 23 Feb '13

23 Feb '13

Finally, I solved the problem using typeOf instead of interpret: cr :: QuasiQuoter cr = QuasiQuoter { quoteExp = quoteRuleFunc} quoteRuleFunc :: String -> Q TH.Exp quoteRuleFunc s = do res <- runIO $ runInterpreter $ do setImports ["Prelude", "Language.Nomyx.Expression"] typeOf s case res of Right "RuleFunc" -> [| s |] Right _ -> fail $ "Rule doesn't typecheck" Left e -> fail $ show e I don't know really why, but now it's working very well! On Sat, Feb 23, 2013 at 7:56 PM, Daniel Gorín <jcpetruzza(a)gmail.com> wrote: > Hi Corentin, > > I've never used TH, but from what I understand, trying to combine hint and > TH would be redundant (even if it worked): whatever String you can evaluate > using hint, you can evaluate it directly in TH. Is this not the case? > > Cheers, > Daniel > > On Feb 23, 2013, at 6:53 PM, Corentin Dupont wrote: > > > Hi Daniel, > > Did you already tried to use Hint in a QuasiQuote? This would come handy > to check at compile time the validity of some strings... > > However I have the error hereunder. > > The duplicate symbol found in the object file is in fact the first > symbol in this file. So I guess GHCi tries to load it twice... > > Best, > > Corentin > > > > > > On Sat, Feb 23, 2013 at 12:03 AM, Corentin Dupont < > corentin.dupont(a)gmail.com> wrote: > > I'm trying to load my interpreter in the Q monad: > > > > cr :: QuasiQuoter > > cr = QuasiQuoter { quoteExp = quoteRuleFunc} > > > > quoteRuleFunc :: String -> Q TH.Exp > > quoteRuleFunc s = do > > res <- runIO $ runInterpreter $ do > > setImports ["Prelude", "Language.Nomyx.Rule", > "Language.Nomyx.Expression", "Language.Nomyx.Test", > > "Language.Nomyx.Examples", "GHC.Base", "Data.Maybe"] > > interpret s (as :: RuleFunc) > > case res of > > Right _ -> [| s |] > > Left e -> fail $ show e > > > > > > However, I always obtain an error during compilation: > > > > ... > > Loading package XXX ... linking ... done. > > > > > > GHCi runtime linker: fatal error: I found a duplicate definition for > symbol > > __stginit_ghczm7zi4zi1_DsMeta > > whilst processing object file > > /usr/lib/ghc/ghc-7.4.1/libHSghc-7.4.1.a > > This could be caused by: > > * Loading two different object files which export the same symbol > > * Specifying the same object file twice on the GHCi command line > > * An incorrect `package.conf' entry, causing some object to be > > loaded twice. > > GHCi cannot safely continue in this situation. Exiting now. Sorry. > > > > > > I vaguely understand that the interpreted modules are conflicting with > the compiled ones... > > > > > > > > On Fri, Feb 22, 2013 at 11:51 PM, Corentin Dupont < > corentin.dupont(a)gmail.com> wrote: > > Great! That seems very powerful. So you can do what you want during > compilation, readin files, send data over the network? > > Other question, in my example how can I halt the compilation if a test > program is wrong? > > > > > > On Fri, Feb 22, 2013 at 8:30 PM, Francesco Mazzoli <f(a)mazzo.li> wrote: > > At Fri, 22 Feb 2013 19:43:51 +0100, > > Corentin Dupont wrote: > > > Hi Adam, > > > that looks interresting. I'm totally new to TH and QuasiQuotes, though. > > > Can I run IO in a QuasiQuoter? I can run my own interpreter. > > > > Yes, you can: > > < > http://hackage.haskell.org/packages/archive/template-haskell/2.8.0.0/doc/ht… > >. > > > > Francesco > > > > > > > >

1 0

Type checking the content of a string
by Corentin Dupont 23 Feb '13

23 Feb '13

Hi all, I have a program able to read another program as a string, and interpret it (using Hint). I'd like to make unit tests, so I have a file "Test.hs" containing a serie of test programs as strings. However, how could I be sure that these test program are syntactically valid, at compile time? Those programs should have the type "RuleFunc". I tried some TH: printProg :: Q Exp -> String printProg p = unsafePerformIO $ do expr <- runQ p return $ pprint expr myTest = printProg [| <my test program> :: RuleFunc |] But it's not very satisfatory yet. When pretty printing TH changes the program quite a bit and my interpreter cannot compile it due to scoping problems. I'd like to have my test program copied back as is. Is it possible? Any other solutions? Thanks a lot! Corentin

4 7