- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] Criteria for determining if a recursive function can be implemented in constant memory
by Steffen Schuldenzucker 07 Jul '10

07 Jul '10

Hum. You are right and I'm probably asking the wrong questions. My original question was when it was possible to eliminate stack frames. For example, in the 'f' function from my first post, we know that none of the variables x and y will be needed after the recursive call to f, so we can just re-use the current stack frame for it, preventing f from using "additional" space for the recursion. However, stack frames are an implementation detail and I thought "constant-space" was an abstraction of my idea. Looks like it was not. On 07/06/2010 04:07 PM, Lennart Augustsson wrote: > Are you limiting your data structures to numbers? In that case, only > numbers of limited size, the answer is, of course, yes. You can > implement any such function in constant space and time. Just make a > lookup table. > > Sent from my iPad > > On Jul 6, 2010, at 6:37, Steffen Schuldenzucker > <sschuldenzucker(a)uni-bonn.de <mailto:sschuldenzucker@uni-bonn.de>> wrote: > >> >> Forwarding this message to the list. >> >> No, I didn't think about the size of integers. For now, let all >> numbers have some bounded size. >> >> -------- Original Message -------- >> Subject: Re: [Haskell-cafe] Criteria for determining if a recursive >> function can be implemented in constant memory >> Date: Tue, 6 Jul 2010 13:25:57 +1200 >> From: Richard O'Keefe <ok(a)cs.otago.ac.nz <mailto:ok@cs.otago.ac.nz>> >> To: Steffen Schuldenzucker <sschuldenzucker(a)uni-bonn.de >> <mailto:sschuldenzucker@uni-bonn.de>> >> >> >> >> On Jul 6, 2010, at 12:23 AM, Steffen Schuldenzucker wrote: >> > Given the definition of a recursive function f in, say, haskell, >> > determine if f can be implemented in O(1) memory. >> >> How are you supposed to handle integer arithmetic? >> >> If you don't take the size of integers into account, >> then since a Turing machine can do any computation, >> it can run a Haskell interpreter, and since a Turing >> machine's tape can be modelled by a single integer >> (or more conveniently by two), any Haskell function >> can be implemented in O(1) Integers. >> >> If you do take the size of integers into account, >> then >> pow2 n = loop n 1 >> where loop 0 a = a >> loop (m+1) a = loop m (a+a) >> requires O(n) memory. >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org <mailto:Haskell-Cafe@haskell.org> >> http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

cabal and ghc disagree on the name of the module Main
by robin morisset 07 Jul '10

07 Jul '10

Hello, I have the following directories set : Project/ Project/Language Project/Language/Copilot/ in Project there is the copilot.cabal file. in Project/Language/Copilot there are a bunch of .hs files, including Main.hs All the modules in these files are named Language.Copilot.NameOfTheFile for cabal to work. My issue happened when I chose to add a Main.hs, containing Language.Copilot.Main and to try to compile it with ghc --make. I got the error message "output was redirected with -o, but no output will be generated because there is no Main module." So I replaced Language.Copilot.Main by Main. ghc was happy, but cabal sent me the following error message : "File name does not match module name: Saw: `Main' Expected: `Language.Copilot.Main'" So I finally kept the Language.Copilot.Main module name, and tried to use the -main-is ghc option. The result was an unreadable linker error message : "/usr/lib/ghc-6.12.1/libHSrtsmain.a(Main.o): In function `main': (.text+0x10): undefined reference to `ZCMain_main_closure' /usr/lib/ghc-6.12.1/libHSrtsmain.a(Main.o): In function `main': (.text+0x18): undefined reference to `__stginit_ZCMain' collect2: ld returned 1 exit status" Does anyone know what this last message mean, and how to make both cabal and ghc happy with my module name ? Thank you in advance, Robin

2 2

Canonical Graphviz code
by Ivan Miljenovic 06 Jul '10

06 Jul '10

Graphviz (http://graphviz.org/) has the option to convert provided Dot code for visualising a graph into a canonical form. For example, take the sample Dot code: ---- | digraph foo { | a [color=blue]; | subgraph cluster_bar { | a [label="hi!"] | b [color=blue, label="bye!"]; | b -> c; | } | a -> b; | a -> c; | c -> d; | d [color=red] `---- Calling "dot -Tcanon" on this produces: ,---- | digraph foo { | node [label="\N"]; | subgraph cluster_bar { | a [label="hi!", color=blue]; | b [label="bye!", color=blue]; | b -> c; | a -> b; | a -> c; | } | d [color=red]; | c -> d; | } `---- Note in particular the following: * The addition of the top-level "node [label="\N"]" attribute; this happens automatically even if all nodes have their own custom label. * The two `a' nodes are merged into the inner-most cluster/subgraph that they are defined in (since they represent the same node). * The attributes for `b' are re-ordered. * The "a -> b" and "a -> c" edges are shifted into the cluster, since all of the related nodes are in that cluster (note that the `c' node is implicitly defined there since an edge involving it is defined there). * The "c -> d" edge is shifted to being _after_ the definition of the `d' node (in fact, in each grouping all nodes are defined before edges). I've recently thought up a way that I can duplicate this functionality (in terms of what it does, not necessarily the actual output) in my graphviz library (http://hackage.haskell.org/package/graphviz) however I'm not sure how closely to follow what Graphviz does. What would the community prefer out of the following (including a mixture, such as options 2 and 3): 1) Match Graphviz's output as much as possible (note that the ordering of the attributes won't happen this way, since I'll be sorting them alphabetically rather than working out Graphviz's arcane rules). 1a) As with 1), but don't worry about defining extra attributes such as "node [label="\N"]". 2) Explicitly define nodes that are only mentioned in edges (e.g. actually define a `c' node, even if it doesn't have any extra attributes). Note that this already happens if such an edge is specified inside a different cluster than the already known node is in; in that case then the stand-alone node is defined in the cluster its edge is defined in, and the actual edge is moved into the outer context that combines the two clusters. 2a) As with 2), but define all edges in the overall graph rather than grouping them internally inside clusters, etc. 3) Group common attributes together as much as possible (e.g. inside the bar cluster, define another subgroup which has a top-level attribute "node [color=blue]" and define the `a' and `b' nodes in there). Not sure how well this will work with edges though, and is probably not possible in conjunction with option 2a). This is a bit tricky and subtle: if `a' and `b' are already in such a subgraph, but an edge specifying one of them is defined _before_ the subgraph is defined, then that node will have an explicit color attribute defined of "" (i.e. empty string), though I would classify this as a bug. 4) As an alternate to option 3), remove all explicit top-level node and edge attributes and move them all to the affected node and edge definitions themselves; this may require option 2). I'm also willing to hear and consider other possible variants; however, I'm only going to code (at most) one. -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com IvanMiljenovic.wordpress.com

4 6

ANNOUNCE: ghc-gc-tune: a tool for analyzing the impact of GC flags
by Don Stewart 06 Jul '10

06 Jul '10

Inspired by a comment by Simon Marlow on Stack Overflow, about the time and space tradeoffs we make with garbage collection, particularly with a generational GCs, I wrote a small program, ghc-gc-tune, to traverse the garbage collector variable space, to see the relationship between settings and program performance. Given a program, it will show you an (optionally interactive) graph of how -A and -H flags to the garbage collector affect performance. http://donsbot.wordpress.com/2010/07/05/ghc-gc-tune-tuning-haskell-gc-setti… Feedback and patches welcome! -- Don

5 6

CGI differences FastCGI
by Jonas Fager 06 Jul '10

06 Jul '10

Hi. This is probably "I must be blind department" I have a very basic strip down echo cgi that runs with apache2. When I try to modfi it to be a FastCGI instead and run it with spawn-fcgi with nginx It don't behave as expected. I suppose that the line that don't get any data is mn <- getInputFPS "file" when running under FastGCI. So is the code wrong? or have I missed something with the setup? I can run the example of fastcgi provided in http://mult.ifario.us/p/wiring-haskell-into-a-fastcgi-web-server with no problem. Description: Ubuntu 10.04 LTS 2.6.32-22-generic-pae #36-Ubuntu SMP The Glorious Glasgow Haskell Compilation System, version 6.12.1 +++++ import Control.Concurrent import Network.CGI -- import Network.FastCGI import Text.Html import qualified Data.ByteString.Lazy as BS import qualified Data.ByteString.Lazy.Char8 as BS8 import Control.Monad (liftM) import Data.Maybe (fromJust) import Char import Data.List import System.Time import qualified Data.ByteString.Char8 as C import Text.JSON.Generic import Text.JSON insertthis fb = do let f = BS8.unpack fb return (f) fileForm = form ! [method "post", enctype "multipart/form-data"] << [textfield "file", submit "" "Upload"] saveFile cont = do r<-liftIO $ insertthis cont return $ paragraph << ("Inserted " ++ (show r)) page t b = header << thetitle << t +++ body << b test :: CGI CGIResult test = do setHeader "Content-Type" "text/html; charset=utf-8" mn <- getInputFPS "file" h <- maybe (return fileForm) saveFile mn output $ renderHtml $ page "Upload" h main = runCGI $ handleErrors test --main= runFastCGI $ handleErrors test +++++

2 1

Subtype polymorphism in Haskell
by Simon Courtenage 06 Jul '10

06 Jul '10

Hi, I am porting a C++ program to Haskell. My current task is to take a class hierarchy and produce something equivalent in Haskell, but I don't seem to be able to get a grip on how type classes and instances contribute to the solution. Can anyone enlighten me? Roughly, the class hierarchy in C++ is of the form class A { public: virtual int do_x(int,int) = 0; }; class B { public: int do_x(int x,int y) { ...} }; class C { public: int do_x(int x,int y) { ...} }; Any help would be greatly appreciated. Thanks Simon courtenage(a)gmail.com

7 9

Criteria for determining if a recursive function can be implemented in constant memory
by Steffen Schuldenzucker 06 Jul '10

06 Jul '10

Dear Cafe, since a little discussion with my tutor I am wondering how the following problem can be solved and if it is decidable: Given the definition of a recursive function f in, say, haskell, determine if f can be implemented in O(1) memory. First I thought the solution would be "check if f is tail-recursive". However, consider the following definition: > -- for the sake of uniformity > if' c t e = if c then t else e > > f :: (Num a) => a -> a -> a > f x y = if' (x <= 0) y $ > if' (x >= 2) (f (x-2) (y+1)) (f (x-1) y) (I don't really care what this function computes as long as it terminates, which is obvious) Although ghc will probably not perform this optimization, f can be realized in O(1) mem: // trying to duplicate f's structure as closely as possible double f( double x, double y ) { START: if ( x <= 0 ) return y; else { if ( x >= 2 ) { x = x - 2; y = y + 1; goto START; } else { x = x - 1; y = y; goto START; } } } It is crucial that (the second) if' does not use both of its last two arguments, but only one. If we replace the second if' by, say > g :: (Num a) => c -> a -> a -> a > g c t e = if' c (t + e) (t - e) , then we have to compute *both* (f (x-2) (y+1)) and (f (x-1) y), and x and y have to be kept in memory during the call to (f (x-2) (y+1)), therefore f cannot be implemented in constant memory. (read: I haven't found a way which does not radically alter f's structure). So, does someone know how to solve this or can prove that it can't be solved? Best regards, Steffen

5 6

Re: [Haskell-beginners] upgrade Hackage show to QuickCheck 2 for lambdabot
by Antoine Latter 06 Jul '10

06 Jul '10

Including the café. On Jul 2, 2010 8:49 AM, "Mark Wright" <markwright(a)internode.on.net> wrote: Hi, I'm trying to upgrade Hackage show to QuickCheck 2, after applying the diffs below (which may not be correct, since I am a beginner), I am left which this error message: runghc ./Setup.hs build Preprocessing library show-0.3.4... Building show-0.3.4... [4 of 4] Compiling ShowQ ( ShowQ.hs, dist/build/ShowQ.o ) ShowQ.hs:104:20: Not in scope: `generate' Compilation exited abnormally with code 1 at Fri Jul 2 23:07:17 The error occurs in this method: tests :: Gen Result -> StdGen -> Int -> Int -> [[String]] -> IO String tests gen rnd0 ntest nfail stamps | ntest == 500 = done "OK, passed" ntest stamps | nfail == 1000 = done "Arguments exhausted after" ntest stamps | otherwise = case ok result of Nothing -> tests gen rnd1 ntest (nfail+1) stamps Just True -> tests gen rnd1 (ntest+1) nfail (stamp result:stamps) Just False -> return $ "Falsifiable, after " ++ show ntest ++ " tests:\n" ++ reason result where result = generate (((+ 3) . (`div` 2)) ntest) rnd2 gen (rnd1,rnd2) = split rnd0 The QuickCheck 1 generate method is near the bottom this page: http://hackage.haskell.org/packages/archive/QuickCheck/1.2.0.0/doc/html/Tes… but I can not find generate in QuickCheck 2. I am wondering if you have any ideas on how to fix it? I'm trying to package lambdabot on Solaris. I have already packaged the Haskell Platform and about 90 packages, they are in: http://pkgbuild.sourceforge.net/spec-files-extra/ Thanks very much, Mark here are the diffs: goanna% diff -wc show-0.3.4-orig/ShowQ.hs show-0.3.4/ShowQ.hs *** show-0.3.4-orig/ShowQ.hs Wed Jan 20 11:24:11 2010 --- show-0.3.4/ShowQ.hs Fri Jul 2 23:07:13 2010 *************** *** 12,22 **** --- 12,25 ---- import qualified Test.SmallCheck (smallCheck, Testable) import Test.QuickCheck + import Test.QuickCheck.Arbitrary import Data.Char import Data.List import Data.Word import Data.Int import System.Random + import Control.Exception (evaluate) + import Test.QuickCheck.Property (ok, stamp) type T = [Int] type I = Int *************** *** 23,36 **** --- 26,45 ---- instance Arbitrary Char where arbitrary = choose (minBound, maxBound) + + instance CoArbitrary Char where coarbitrary c = variant (ord c `rem` 4) instance Arbitrary Word8 where arbitrary = choose (minBound, maxBound) + + instance CoArbitrary Word8 where coarbitrary c = variant (fromIntegral ((fromIntegral c) `rem` 4)) instance Arbitrary Ordering where arbitrary = elements [LT,EQ,GT] + + instance CoArbitrary Ordering where coarbitrary LT = variant 1 coarbitrary EQ = variant 2 coarbitrary GT = variant 0 *************** *** 37,42 **** --- 46,53 ---- instance Arbitrary Int64 where arbitrary = sized $ \n -> choose (-fromIntegral n,fromIntegral n) + + instance CoArbitrary Int64 where coarbitrary n = variant (fromIntegral (if n >= 0 then 2*n else 2*(-n) + 1)) instance (Integral a, Arbitrary a) => Arbitrary (Ratio a) where *************** *** 48,53 **** --- 59,65 ---- else (b % a) else (a % b) + instance (Integral a, CoArbitrary a) => CoArbitrary (Ratio a) where coarbitrary m = variant (fromIntegral $ if n >= 0 then 2*n else 2*(-n) + 1) where n = numerator m *************** *** 87,93 **** Just False -> return $ "Falsifiable, after " ++ show ntest ++ " tests:\n" ! ++ unlines (arguments result) where result = generate (((+ 3) . (`div` 2)) ntest) rnd2 gen (rnd1,rnd2) = split rnd0 --- 99,105 ---- Just False -> return $ "Falsifiable, after " ++ show ntest ++ " tests:\n" ! ++ reason result where result = generate (((+ 3) . (`div` 2)) ntest) rnd2 gen (rnd1,rnd2) = split rnd0 goanna% _______________________________________________ Beginners mailing list Beginners(a)haskell.org http://www.haskell.org/mailman/listinfo/beginners

2 2

Please check your dependencies on fgl
by Ivan Miljenovic 06 Jul '10

06 Jul '10

Thomas Bereknyei are currently re-writing fgl (just about completely from scratch) and we plan to make an initial release to get feedback on the API in the next few weeks. However, I'm sending this email out now to warn people that I highly doubt any code that was written for the current version of fgl (http://hackage.haskell.org/package/fgl-5.4.2.2) will work with the new version. As such, if your code uses fgl you should ensure that the specification of the package in your .cabal file has an explicit upper bound (or indeed just set "fgl == 5.4.2.2") to avoid any problems when we release 6.0.0.0 (we're trying to avoid the problems that plagued KDE-4 by not claiming in the slightest that the initial few versions are intended for end users). I have already directly emailed the maintainers of any and all packages I could find on Hackage (using Roel van Dijk's wonderful reverse-dependency mirror at http://bifunctor.homelinux.net/~roel/hackage/packages/hackage.html) but just in case I've missed one or there's an as-yet-unreleased package somewhere in the works, here is the official "heads up". -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com IvanMiljenovic.wordpress.com

17 43

cereal vs. binary
by braver 06 Jul '10

06 Jul '10

I dump results of a computation as a Data.Trie of [(Int,Float)]. It contains about 5 million entries, with the lists of 35 or less pairs each. It takes 8 minutes to load with Data.Binary and lookup a single key. What can take so long? If I change from compressed to uncompressed (and then decode), it's the same time... It's not IO, CPU is loaded 100%. I'm now thinking of using cereal. Given I have Data.Binary in place, what needs to be changed to work with cereal? Is it binary- compatible? How can one construct a cereal instance for Data.Trie? -- Alexy

4 4