- Haskell-Cafe - Haskell.org

How to give unique name/id to nodes outside any monad ?
by minh thu 09 Jan '09

09 Jan '09

Hi, I'd like to process some kind of graph data structure, say something like data DS = A [DS] | B DS DS | C. but I want to be able to discover any sharing. Thus, in b = B a a where a = A [C], if I want to malloc a similar data structure, I have to handle to the node representing B two times the same pointer (the one returned after allocating A [C]). To discover sharing, I thought it would be necessary to give unique name to node and then compare them while traversing the graph. I could give the name by hand but it would be cumbersome. But at least it would not require any monad for the bookkeeping of ungiven names. Is it possible to give those names automatically but outside any monad ? Thanks, Thu

6 15

Blitting one IOUArray into another
by Bueno, Denis 09 Jan '09

09 Jan '09

Hi all, I'm seeing a lot of unexpected memory allocation with some simple code that copies the contents of one vector (IOUArray Int Int64) into another of the same type and dimensions. In particular, profiling reveals that `copyInto' is allocating oodles and oodles of memory. My small test case creates two 50000-element arrays and performs 10000 copies from one into the other. Since the elements are Int64s and the arrays are unboxed, each array should be 50000 elements * 8 bytes per element = 400,000 bytes and so the arrays should only take 800,000 bytes total. I understand there's some overhead for thunks and whatnot, but the profiler reported allocation is around 40 billion bytes. And almost all of that allocation is in my copying function, not in main (main allocates the arrays). I've attached two versions of the code, just for comparison. The only difference is the way the copying is done. One calls `getBounds' to figure out the bounds, and one is given the bounds for copying. They're both about the same speed and allocation (originally I was using IOUArray Int64 Int64, and there was a much greater allocation difference between the two versions; but that went away. Oh well). So, does anyone know why copying takes so much allocation? I expect there is _some_ way to just move memory from one array to another, like a memcpy -- how can I do that? Denis

6 8

Re: State Monad - using the updated state
by John Lato 09 Jan '09

09 Jan '09

It sounds like you've got the monadic solution figured out, so that's good. Even though I would recommend using State (or StateT if necessary), I wanted to be sure this question was answered. > ranq1List :: (Word64 -> a ) -> Word64 -> [a] > ranq1List converter state = converter newState : ranq1List converter > newState > where > newState = ranq1Increment state > > > One more question on this - the other concern I had with the recursive list > approach was that although lazy evaluation prevents me generating numbers > before I 'ask' for them, I figured that if I was going to be asking for say > 10 million over the course of one simulation, that although I request them > one by one, over hours or even days, at the end of the simulation I will > still have a list of 10 million word64s - each of which I could throw away > within minutes of asking for it. This seemed like huge memory bloat, and > thus probably I was taking the wrong approach. This "memory bloat" is a space leak. In general they are to be avoided. GHC's garbage collection is quite efficient, so if you structure your program properly the space will be reclaimed after the values are used. Values will only be collected if they cannot be referenced from live code (just like Java, Python, C#, or other languages with GC). If you are able to structure your code like this: doSomething :: [Word64] -> IO () doSomething (rand:rands) = do someIO rand otherIO rand ... if endFlag then return () else doSomething rands main = do let rands = ranq1List id 1 doSomething rands you won't have a space leak. The head of the list is used within doSomething, while only the tail is passed in the recursion. At the time of the recursive call to doSomething, the head 'rand' value is no longer accessible by any running code, so it can be GC'd. Contrast that with this version (somewhat contrived): doSomething2 :: [Word64] -> Int -> IO () -- the Int is an index into the list. doSomething2 rands i = do let rand = rands !! i someIO rand otherIO rand ... if endFlag then return () else doSomething2 rands (i + 1) This version is Really Bad. Firstly the entire list is passed on each recursion. Every element remains within scope, so nothing is GC'd. That's the space leak. There's another big problem: the current random value is computed by traversing from the head of the list. As the index value grows, it takes progressively longer to traverse the list to retrieve the current value. (N.B. I haven't tested these specific examples, but I think I'm right.) Cheers, John Lato

1 0

Taking Exception to Exceptions
by Immanuel Litzroth 09 Jan '09

09 Jan '09

I'm trying to use the new (for me at least) extensible exceptions and I am little amazed that I cannot get catch, try or mapException to work without telling them which exceptions I want to catch. What is the rationale behind this? How does bracket manage to catch all exceptions? What should onException do? Is there some example code that uses these exceptions, or better documentation? Thanks in advance, Immanuel

5 5

HookedBuildInfo and Cabal
by John Goerzen 09 Jan '09

09 Jan '09

Hi Brian & everyone, Got this bug report, which appears to be related to your autoconf patch. Did you test it on Windows? As a more general question, how can one use Cabal to detect PostgreSQL paths in a way that works with both GHC 6.8 and 6.10? The commit here was: commit 57c723873b020643b9062941a2ece130cd0f36c6 Author: Brian Bloniarz <phunge0(a)hotmail.com> Date: Fri Dec 26 14:33:43 2008 -0500 Update hdbc-postgresql for GHC 6.10 & Cabal 1.6. This switches over to use autoconf rathe r than Cabal hooks to detect postgres paths; there's no backwards-compatible way to use write HookedBuildInfo with Cabal 1.2 and Cabal 1.6 (see http://www.haskell.org/pipermail/glasgow-ha skell-users/2008-October/015707.html) -- John ----- Forwarded message from software-noreply(a)complete.org ----- From: software-noreply(a)complete.org Date: Thu, 08 Jan 2009 12:37:12 -0600 Subject: [HDBC PostgreSQL driver - Bug #131] Throw exception when use data type "timpstamp without time zone" Issue #131 has been updated by Benjamin Cao. by the way, I cannot configure 1.1.6.0.0 successfully on my windows OS because of the Expr command(which is a linux command, even if I got a windows version of it, it keep crash on windows.) The function isFixedPointUnderConversionToLocalTime in 1.1.6.0.0 is the same. So I think it should be a same issue on 1.1.6.0.0 ---------------------------------------- Bug #131: Throw exception when use data type "timpstamp without time zone" http://software.complete.org/software/issues/show/131 Author: Benjamin Cao Status: New Priority: Normal Assigned to: Category: Target version: 1.1.4.1.0 Resolution: The database is like CREATE TABLE test ( "name" character varying(200) NOT NULL, "time" timestamp with time zone, timenotz timestamp without time zone, CONSTRAINT test_pkey PRIMARY KEY (name) ) WITH (OIDS=FALSE); ALTER TABLE test OWNER TO postgres; when call st <- prepare c "select name,time, timenotz from test" execute st [] Will get this error: Time.toClockTime: timezone offset out of range So I modified the function in statement.hsc to: isFixedPointUnderConversionToLocalTime calTime = do let hasError = False calTime' <- Control.Exception.catch (toLocalCalTime calTime) (\_->do let hasError = True return calTime) if hasError then return False else return $ eqParts calTime calTime' ---------------------------------------- You have received this notification because you have either subscribed to it, or are involved in it. To change your notification preferences, please click here: http://software.complete.org/software/my/account ----- End forwarded message -----

2 1

State Monad - using the updated state
by Phil 08 Jan '09

08 Jan '09

Hi, I¹m a newbie looking to get my head around using the State Monad for random number generation. I¹ve written non-monad code that achieves this no problem. When attempting to use the state monad I can get what I know to be the correct initial value and state, but can¹t figure out for the life of me how to then increment it without binding more calls there and then. Doing several contiguous calls is not what I want to do here and the examples I¹ve read all show this (using something like liftM2 (,) myRandom myRandom). I want to be able to do: Get_a_random_number < a whole load of other stuff > Get the next number as defined by the updated state in the first call <some more stuff> Get another number, and so on. I get the first number fine, but am lost at how to get the second, third, forth etc without binding there and then. I just want each number one at a time where and when I want it, rather than saying give 1,2,10 or even n¹ numbers now. I¹m sure it¹s blindly obvious! Note: I¹m not using Haskell¹s built in Random functionality (nor is that an option), I¹ll spare the details of the method I¹m using (NRC¹s ranq1) as I know it works for the non-Monad case, and it¹s irrelevent to the question. So the code is: ranq1 :: Word64 -> ( Double, Word64 ) ranq1 state = ( output, newState ) where newState = ranq1Increment state output = convert_to_double newState ranq1Init :: Word64 -> Word64 ranq1Init = convert_to_word64 . ranq1Increment . xor_v_init -- I¹ll leave the detail of how ranq1Increment works out for brevity. I know this bit works fine. Same goes for the init function it¹s just providing an initial state. -- The Monad State Attempt getRanq1 :: State Word64 Double getRanq1 = do state <- get let ( randDouble, newState ) = ranq1 state put newState return randDouble _________ And then in my main _________ -- 124353542542 is just an arbitrary seed main :: IO() main = do let x = evalState getRanq1 (ranq1Init 124353542542) print (x) As I said this works fine; x gives me the correct first value for this sequence, but how do I then get the second and third without writing the giveMeTenRandoms style function? I guess what I want is a next() type function, imperatively speaking. Many thanks for any help, Phil.

4 4

"Inconsistency" in support for phantom types?
by DavidA 08 Jan '09

08 Jan '09

Hi, I have run into what appears to be an inconsistency in the support for using phantom types to parameterize other types. Here's an example (don't pay too much attention to the maths, it's just there to motivate the example). I want to define types for the finite fields with 2, 3 and 5 elements (clock arithmetic modulo 2, 3 or 5). {-# OPTIONS_GHC -fglasgow-exts #-} class IntegerAsType a where value :: a -> Integer -- three phantom types: data T2 instance IntegerAsType T2 where value _ = 2 data T3 instance IntegerAsType T3 where value _ = 3 data T5 instance IntegerAsType T5 where value _ = 5 newtype Fp n = Fp Integer deriving (Eq,Ord) -- our three finite field types: type F2 = Fp T2 type F3 = Fp T3 type F5 = Fp T5 -- Show and Num instances instance Show (Fp n) where show (Fp x) = show x instance IntegerAsType n => Num (Fp n) where Fp x + Fp y = Fp $ (x+y) `mod` value (undefined :: n) negate (Fp 0) = 0 negate (Fp x) = Fp $ value (undefined :: n) - x Fp x * Fp y = Fp $ (x*y) `mod` value (undefined :: n) fromInteger m = Fp $ m `mod` value (undefined :: n) Now, we can also define a Fractional instance, using the extended Euclid algorithm (given at the end) -- n must be prime instance IntegerAsType n => Fractional (Fp n) where recip 0 = error "Fp.recip 0" recip (Fp x) = let p = value (undefined :: n) (u,v,1) = extendedEuclid x p -- so ux+vp = 1. (We know the gcd is 1 as p prime) in Fp $ u `mod` p Now, the problem I've run into is, what do I do if I want to define a function parameterised over the phantom types, but without doing it as part of a type class instance? For example, suppose that I had just wanted to define "inv" as a synonym for "recip": inv :: IntegerAsType n => Fp n -> Fp n inv 0 = error "Fp,inv 0" inv (Fp x) = let p = value (undefined :: n) (u,v,1) = extendedEuclid x p in Fp $ u `mod` p "inv" has exactly the same code as "recip", but now the IntegerAsType constraint is part of the type signature, rather than an instance constraint. It seems that this means that the constraint is not available to the code during compilation, because when I try to compile this I get Ambiguous type variable `n' in the constraint: `IntegerAsType n' arising from a use of `value' at Test.hs:52:21-42 Probable fix: add a type signature that fixes these type variable(s) It seems to me highly desirable that this code should compile as expected, just as the recip code compiles. Is it a bug in GHC, or a missing language feature, or is there a "better" way to do what I'm trying to do? Thanks, David -- extendedEuclid a b returns (u,v,d) such that u*a + v*b = d extendedEuclid a b | a >= 0 && b >= 0 = extendedEuclid' a b [] where extendedEuclid' d 0 qs = let (u,v) = unwind 1 0 qs in (u,v,d) extendedEuclid' a b qs = let (q,r) = quotRem a b in extendedEuclid' b r (q:qs) unwind u v [] = (u,v) unwind u v (q:qs) = unwind v (u-v*q) qs

4 3

Re: [Haskell-cafe] Defining methods generically for a class
by Jeff Heard 08 Jan '09

08 Jan '09

That's probably the best thing to do, yes. The purpose of doing so was for Data.List.delete, but I see now there's a Data.List.deleteBy, so I can use the regionEquals function as my equality predicate. On Thu, Jan 8, 2009 at 12:26 PM, Martijn van Steenbergen <martijn(a)van.steenbergen.nl> wrote: > Hi Jeff, > > Jeff Heard wrote: >> >> instance Region a => Eq a where >> regiona == regionb = all $ zipWith (==) (bounds regiona) (bounds >> regionb) > > If you want to be Haskell98 compliant, why not define regionEquals :: Region > a => a -> a -> Bool as above and use that everywhere instead of (==)? > > If you insist on using the overloaded (==), then in Haskell98 you will need > to define individual Eq instances for all your custom region types. However, > you can simply define (==) = regionEquals for all those types. > > Hope this helps, > > Martijn. >

1 0

Fwd: [Haskell-cafe] Defining methods generically for a class
by Jeff Heard 08 Jan '09

08 Jan '09

---------- Forwarded message ---------- From: Jeff Heard <jefferson.r.heard(a)gmail.com> Date: Thu, Jan 8, 2009 at 12:26 PM Subject: Re: [Haskell-cafe] Defining methods generically for a class To: Cristiano Paris <frodo(a)theshire.org> Not really... I'm not testing if each of the items a are equal, but rather that in the context of them being a Region, they are equal.As long "dim" (which is in the class) can be defined, then equality is defined over all types Region. On Thu, Jan 8, 2009 at 12:16 PM, Cristiano Paris <frodo(a)theshire.org> wrote: > On Thu, Jan 8, 2009 at 6:04 PM, Jeff Heard <jefferson.r.heard(a)gmail.com> wrote: >> ... >> How do I declare all Regions to be Eqs without putting it in the class >> body (since I define a function over all Regions that is independent >> of datatype that is an instance of Region)? > > Would this be a solution? > > class Eq a => Region a where > ... > > Cristiano >

1 0

Defining methods generically for a class
by Jeff Heard 08 Jan '09

08 Jan '09

I have the following class: class Region a where numDimensions :: a -> Int dim :: Int -> a -> (Double,Double) merge :: a -> a -> a and several ancillary methods defined, the most importance of which is: bounds :: Region a => a -> [(Double,Double)] bounds r = take (numDimensions r) . map dim . iterate (+1) $ 0 Let's say that I want all Regions to also be of class Eq, where regiona == regionb = all $ zipWith (==) (bounds regiona) (bounds regionb) How do I declare all Regions to be Eqs without putting it in the class body (since I define a function over all Regions that is independent of datatype that is an instance of Region)? Is it merely: instance Region a => Eq a where regiona == regionb = all $ zipWith (==) (bounds regiona) (bounds regionb) -- Jeff

3 2