- Haskell-Cafe - Haskell.org

Space efficiency problem
by Adrian Victor CRISCIU 12 Nov '04

12 Nov '04

Hi, This may be silly, but I tried to code a simmulated annealing method to solve the travelling salesman prblem, by adapting the algorithm described in "Numerical Recipes in C". The problem is that there are so many iterations, that the program gets killed (kill -9) by the system. I use the State monad to code the optimisation algorithm, and a simple configurations generator for generating the each path. After profiling with -hc, the heap profile shows that the top-level function of the algorithm uses about 40Mb of heap space. How can I improve this awful program? The optimisation algorithm is coded as simmann = untilM theEnd refine path0 untilM :: (Monad m) => (m a -> m Bool) -> (a -> m a) -> m a -> m a untilM p f m0 = do isOver <- p m0 if isOver then m0 else untilM p f (m0 >>= f) theEnd tests if the current temperature has reached the lower limit, and refine produces a new path via a random modification on the current one. What can I do to get this running? It seems to eat up all the available space. I coded this previously in C, with destructive update of the state and path, but in Haskell, with recursion, this seems to be hoplessly inefficient. I use ghc-6.2.1 on a Slackware box based on kernel 2.4.18 with glibc 2.2.5 Thanks for your time! Adrian.

4 4

Re: [Haskell] Re: About Random Integer without IO
by Graham Klyne 12 Nov '04

12 Nov '04

At 00:10 12/11/04 +0100, karczma wrote: >But it was MUCH more important to repeat the same >sequence, e.g., after making fast some nice fractal sketch, I relaunched >the program with bigger size/precision, but exploiting the same random >sequence. I repeat, such is my philosophy. I agree. I've used similar randomization techniques for software testing, having similar requirements for repeatability. (E.g., finding a seed that generates an error after several million iterations, with a specific iteration number, and then re-running the test to enable tracing at exactly the required iteration number.) #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

Re: [Haskell] Re: About Random Integer without IO
by Clive Brettingham-Moore 12 Nov '04

12 Nov '04

This really really should have moved to haskell-cafe as previously suggested (sending to both with this in mind); apologies for being a little confising to haskell-cafe This isn't a language design issue, it is a FAQ, or at best a nebulous conceptual debate (speaking of which, has anyone got something more specific than http://www.haskell.org/hawiki/ThatAnnoyingIoType) This question comes up again and again with Haskell newbies - the answer is of course you can't - not maybe, not sometimes, not sort of, but no. What you can do is confine the IO-ness at the outermost layer of the program - by seeding a psudo-random list at program initialization, as both solutions suggested - giving the original question the benefit of the doubt, we'll assume this was what the questioner wanted. Suggesting parameters is not an escape - it is exactly the same as using /dev/random in that they are also IO, weaker IO but still IO (getArgs:: IO [String], though there are counter arguments); besides, reproducability was not a requirement mentioned or implied by the original question (though relevent, not actually haskell specific.. haskell-cafe, again). Chaotic is not the same as Random (Jerzy you obviously know this, but please be clear about it, don't add to the confusion). Chaotic algoritms are used as a 'random-extender'. Random only happens when you seed you algorithm with a non-deterministic value (ie random). karczma wrote: > noise). I generated random fractals, etc. It didn't cost me anything to > put different initializations by hand on every run when I wanted to have > different behaviour. But it was MUCH more important to repeat the same > sequence, e.g., after making fast some nice fractal sketch, I relaunched > the program with bigger size/precision, but exploiting the same random > sequence. I repeat, such is my philosophy. Yours is easier, since you are > just discussing, most probably you never used RN for a serious work. If > I am wrong, I apologize. > > Jerzy K. I have to say this.. SERIOUS WORK?! I don't know what Thomas does, but I'm working with security at the moment, and a "serious" random program with default constant seeding strikes me as serious and not in a good way. Overridable seeding sure, if the application demands it, but not broken by default. It's not random; it may be alright for screensavers, but it's not a good coding habit. Clive (Sorry, pet peeve)

1 0

Re: [Haskell-cafe] One-shot? (was: Global variables and stuff)
by Adrian Hey 11 Nov '04

11 Nov '04

On Thursday 11 Nov 2004 6:36 am, Judah Jacobson wrote: > AFAIKS, the definition of "once" that I gave uses unsafePerformIO in a > perfectly sound manner; namely, the creation of a top-level MVar. It > only becomes unsafe if certain "optimizations" are performed; but > then, that's also true for the SafeIO proposal (as I understand it). That's the trouble with unsafePerformIO. Haskell is supposed to be a purely functional language and the compiler will assume all functions are pure. As soon as you use unsafePerformIO to create something that isn't a function you're in grave danger, even if it "looks safe" at the local level, it still isn't a function and the damage can't be contained at the local level. It's only really OK if it still is a function despite the use of unsafePerformIO (which is possible, but often hard to be sure about). > Yeah, perhaps it hasn't been said so much before. :-) You noted > several days ago that oneShot (a variant of my "once") can be defined > using top-level mutable variables. I was just pointing out that the > converse is true: top-level mutable variables can be emulated using I'm not too sure about that. But I guess the devil's in the detail, so until that's been thrashed out I'll reserve judgement. > Again, I would assume that any translation of (x <- someAction) needs > to have a prohibition on CSE, inlining, etc on the RHS; there's > nothing special to once here. Yes, but the trouble is in Haskell if you have x = y that really means any occurance of x can be replaced by y (and vice-versa) without changing the meaning of the program (subject to scoping rules of course). You're right that your once solution and the (x <- someAction) both have the same problem. But the difference is the compiler doesn't know that with the once solution because you've told it that.. myRef = once (newIORef 'a') ..and it will believe you. > I disagree that this only works for newIORef. Consider (in ghci): Well no, of course newIORef isn't the *only* case where it works :-) But I thought the point you were making was that the once guaranteed that the resulting value was independent of when it got reduced (presumably for any action). This isn't generally true, any more than it would be true for the x <- someAction solution if some action can be *any* IO monadic operation. That's why the proposal to use a restricted monad was put forward I.E. an "IO monad" which was not capable of doing any real IO. In principle at least, with the SafeIO/CIO monads the resulting initial value could be determined at compile time, which is exactly what we want I think (same intial value for every program run). Regards -- Adrian Hey

2 1

RE: [Haskell-cafe] FiniteMap-like module for unordered keys?
by Simon Marlow 11 Nov '04

11 Nov '04

On 10 November 2004 10:54, Graham Klyne wrote: > At 23:25 09/11/04 +0100, Remi Turk wrote: >>> (I looked at Data.HashTable, but I couldn't figure why it needs to >>> be implemented in the IO monad, except to optimize the internal >>> implementation. Also, it's not clear to me how it behaves when a >>> key is inserted that already exists.) >> A hash-table becomes rather useless without mutable state AFAICS. >> Without it, one might almost just as well use a list of pairs... >> Actually, some kind of freezeHashTable may be useful, and >> a HashTable in the ST monad is definitely useful: I guess patches >> are welcome.. > > I can see why using (something like) a state monad might be useful, > but not why it needs to be an IO monad, unless there's some fairly > low-down optimization being performed. > > (I'm not asking for this, BTW, just commenting on the apparent lack. > For my application, I am using a list of pairs, as I expect these > tables to be relatively small.) There is no good reason that Data.HashTable needs to be in the IO monad, other than that's where I wanted to use it and having two versions (or using lots of stToIO) would have been a pain. The performance of ST & IO are the same. Long ago, when IO exceptions were implemented explicitly in the IO monad, IO used to be less efficient than ST. Cheers, Simon

1 0

FiniteMap-like module for unordered keys?
by Graham Klyne 11 Nov '04

11 Nov '04

Is there a module that provides functionality similar to that of Data.FiniteMap for keys that do not have a defined ordering relation? (I looked at Data.HashTable, but I couldn't figure why it needs to be implemented in the IO monad, except to optimize the internal implementation. Also, it's not clear to me how it behaves when a key is inserted that already exists.) #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

6 7

ANNOUNCE: Haskell Communities & Activities Report (7th ed., November 2004)
by Andres Loeh 10 Nov '04

10 Nov '04

Right in time, I am pleased to announce -- on behalf of the many contributers -- that the Haskell Communities and Activities Report (7th edition, November 2004) http://www.haskell.org/communities/ is now available from the Haskell Communities home page in several formats: PDF, for screenreading as well as printing, HTML, for those of you who prefer not to deal with plugins or external viewers, and PostScript, for those of you who have nice quick printers that do not grok PDF. Many thanks go to all the people that contributed to this report, both directly, by sending in descriptions, and indirectly, by doing all the interesting things that are reported. I hope you will find it as interesting a read as we did. If you haven't encountered the Haskell Communities and Activities Reports before, you may like to know that the first of these reports was published in November 2001. Their goal is to improve the communication between the increasingly diverse groups, projects and individuals working on, with, or inspired by Haskell. The idea behind these reports is simple: Every six months, a call goes out to all of you enjoying Haskell to contribute brief summaries of your own area of work. Many of you respond (eagerly, unprompted, and well in time for the actual deadline ;) ) to the call. The editor collects all the contributions into a single report and feeds that back to the community. When we try for the next update, six months from now, you might want to report on your own work, project, research area or group as well. So, please put the following into your diaries now: ---------------------------------------- End of April 2005: target deadline for contributions to the May 2005 edition of the HC&A Report ---------------------------------------- Unfortunately, many Haskellers working on interesting projects are so busy with their work that they seem to have lost the time to follow the Haskell related mailing lists and newsgroups, and have trouble even finding time to report on their work. If you are a member, user or friend of a project so burdened, please find someone willing to make time to report and ask them to `register' with the editor for a simple e-mail reminder in the middle of April (you could point us to them as well, and we can then politely ask if they want to contribute, but it might work better if you do the initial asking). Of course, they will still have to find the ten to fifteen minutes to draw up their report, but maybe we can increase our coverage of all that is going on in the community. Feel free to circulate this announcement further in order to reach people who might otherwise not see it. Enjoy! Andres Loeh <hcar(a)haskell.org> <andres(a)cs.uu.nl> -- Haskell Communities and Activities Report (http://haskell.org/communities)

1 0

Space efficiency problem
by Adrian Victor CRISCIU 09 Nov '04

09 Nov '04

Hi, This may be silly, but I tried to code a simmulated annealing method to solve the travelling salesman prblem, by adapting the algorithm described in "Numerical Recipes in C". The problem is that there are so many iterations, that the program gets killed (kill -9) by the system. I use the State monad to code the optimisation algorithm, and a simple configurations generator for generating the each path. After profiling with -hc, the heap profile shows that the top-level function of the algorithm uses about 40Mb of heap space. How can I improve this awful program? The optimisation algorithm is coded as simmann = untilM theEnd refine path0 untilM :: (Monad m) => (m a -> m Bool) -> (a -> m a) -> m a -> m a untilM p f m0 = do isOver <- p m0 if isOver then m0 else untilM p f (m0 >>= f) theEnd tests if the current temperature has reached the lower limit, and refine produces a new path via a random modification on the current one. What can I do to get this running? It seems to eat up all the available space. I coded this previously in C, with destructive update of the state and path, but in Haskell, with recursion, this seems to be hoplessly inefficient. Thanks for your time! Adrian.

1 0

Re: [Haskell] Re: Global Variables and IO initializers
by Keean Schupke 09 Nov '04

09 Nov '04

I might really want to call the initialisation twice. If you use global variables, the library can only be initialised once... but what if I really want to use the library twice? With the state in a type passed between functions, you can have multiple different states active at once. Keean. Benjamin Franksen wrote: >Yes, whenever possible I would use this approach. Unfortunately, there are >libraries (or just modules) that need to do some IO action in order to >produce the (A)DT. In this case it _will_ make a difference how often you >call it. But then this is just how IO actions are by nature, isn't it? > >Ben > >

5 7

One-shot? (was: Global variables and stuff)
by Graham Klyne 09 Nov '04

09 Nov '04

I've not been following the Global variables debate too closely, it seeming to have something of a religious wars flavour, but I noticed that an example being proposed was how to achieve a "one shot" execution. Here's something I did when working on modifications to the HaXML parser: [[ -- Memoization of withSocketsDo to prevent multiple calls. -- (cf. http://tangentsoft.net/wskfaq/articles/lame-list.html) socketsInitialized :: Bool socketsInitialized = unsafePerformIO ( withSocketsDo ( return True ) ) ]] Does it work as I think it does? ARe there any problems I'm overlooking? #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0