Re: [Haskell-cafe] naming a data structure for weighted random selection without replacement
On Tue, Feb 19, 2008 at 1:27 PM, Isaac Dupree <[EMAIL PROTECTED]> wrote: > the "without replacement" thing is more specific. Although maybe the > design could accomodate selection-with-replacement in the same package too Once you have without-replacement, with-replacement is easy: just re-use the old structure instead of the new one. Laziness means that you don't even pay the cost of deletion. (Multiple-with-replacement takes a little more work, because you can't just re-use the multiple-without-replacement function if you want each draw to be independent.) > or RandomPool? RandomHat? OutOfAHat? :-) I'm currently leaning towards something like "Data.Random.WeightedPool". (I really love Hat and Urn, but I now think they're a little *too* cute.) Stuart ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] naming a data structure for weighted random selection without replacement
Michał Pałka wrote: On Mon, 2008-02-18 at 11:37 +, Luke Palmer wrote: On Feb 18, 2008 5:11 AM, Stuart Cook <[EMAIL PROTECTED]> wrote: A while ago I wrote a little data structure that allows weighted random selection-without-replacement from a collection of values in O(log n) time.[1] I'm now in the process of packaging it up for Hackage, but I'm looking for good names for both the type and its operations. I'm pretty sure it should have Random in the name whatever it is called. Obvious idea: How about WeightedRandom? the "without replacement" thing is more specific. Although maybe the design could accomodate selection-with-replacement in the same package too or RandomPool? RandomHat? OutOfAHat? :-) -Isaac ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] build-depends contraints in a .cabal file
Can I specify an equality constraint in the build-depends field of a .cabal file? This would say that I want one specific version (because all the rest of my packages are compiled against that version and I'm getting type-checking errors trying to install the new package). neither > build-depends: foobar = 3.0.1 or > build-depends: foobar-3.0.1 seem to work. Do I have any choices other than re-compiling everything? Thanks, Antoine ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Working with multiple time zones
Brandon S. Allbery KF8NH wrote: >> some platforms require tzset() to recognize timezone changes. I think it is something like - POSIX requires the tzset() call, but in ANSI C 98 there is no tzset() and localtime() always rechecks TZ automatically. Right? In the man page on Mac OS X Tiger (Darwin 8.11.1), it says that localtime() calls tzset() automatically if the current process has not called it yet. Which implies that it would only be called once, so I don't understand Bjorn's successful result on that platform. Don Stewart wrote: > Perhaps we should get a binding to tzset in the unix library? I agree - but to make it worthwhile, we should either: a) make things work the same on all platforms, or b) faithfully expose the underlying local platform, but make it easy (and well documented) for a program to discover what needs to be done to make things work. (Even if the information provided by System.Info is sufficient, how easy is it to use it for this?) In any case, full information or a clear pointer to it should appear in the Haddocks for Data.Time.LocalTime, System.Time, and wherever else appropriate. For comparison, Python does (a) - the behavior of localtime() and tzset() are always like POSIX, even on a platform that does otherwise. And also on Windows. This behavior is clearly described in the documentation for the time module. Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: naming a data structure for weighted random selection without replacement
Stuart Cook gmail.com> writes: > The name I have at the moment is "Pool", which I'm reasonably happy > with, but I wanted to see if I could find anything better. Asking on > #haskell got me a few responses: > > ... > > Any suggestions? How about Tombola? Brett ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Arrow combinator names
On Sun, Feb 17, 2008 at 10:37 PM, Tom Davies <[EMAIL PROTECTED]> wrote: > Are there generally accepted English language names for the arrow > combinators? > > >>> compose? Well, compose usually means something with type (a c d -> a b c -> a b d), but (>>>) has the dual type (a b c -> a c d -> a b d). So it's really "cocompose", which, of course, can be shortened to "mpose". -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: A question about "monad laws"
Wilhelm B. Kloke wrote:
> Ben Franksen <[EMAIL PROTECTED]> schrieb:
>> Wilhelm B. Kloke wrote:
>>> [EMAIL PROTECTED] <[EMAIL PROTECTED]> schrieb:
>>> I would consider a good idea if ghc would provide language support to
>>> this sort of integers.
>>
>> No need, you can do that for yourself:
>>
>> {-# LANGUAGE GeneralizedNewtypeDeriving #-}
>> newtype DInt = DInt Double deriving (Eq, Ord, Enum, Num)
>>
>> instance Show DInt where show (DInt x) = show (truncate x :: Integer)
>
> Probably you missed the point I wanted to make.
Obviously ;)
> This works only properly,
> if you can catch the Inexact Trap which indicates the overflow. The
> problem whith normal Ints is that the hardware does not support overflow
> detection. You get silent wrong results if you use an Int type which maps
> to C int, but not if it maps to C float or double with Inexact trap
> enabled. Therefore you need add runtime checks to be sure that you notice
> a possible overflow condition.
I agree completely.
Cheers
Ben
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stack overflow
On Mon, Feb 18, 2008 at 05:56:41PM +, Adrian Hey wrote: Philip Armstrong wrote: On Sun, Feb 17, 2008 at 10:01:14PM +, Adrian Hey wrote: BTW, I find this especially ironic as fromDistinctAscList is the perfect example what I was talking about in another thread (continuation passing madness caused by an irrational fear of stack use). In *some* cases, continuation passing can be quite a bit faster than other approaches IIRC. I haven't looked at this bit of code though. Can you or anyone else give an example? I think I was thinking of this: http://r6.ca/blog/20071028T162529Z.html but can't be entirely sure. Sorry! Phil -- http://www.kantaka.co.uk/ .oOo. public key: http://www.kantaka.co.uk/gpg.txt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stack overflow
Philip Armstrong wrote: On Sun, Feb 17, 2008 at 10:01:14PM +, Adrian Hey wrote: BTW, I find this especially ironic as fromDistinctAscList is the perfect example what I was talking about in another thread (continuation passing madness caused by an irrational fear of stack use). In *some* cases, continuation passing can be quite a bit faster than other approaches IIRC. I haven't looked at this bit of code though. Can you or anyone else give an example? Thanks -- Adrian Hey ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell Thrift bindings
Hi everyone, This is regarding Thrift, "a software framework for scalable cross-language services development"(1) Present in the release tarball there is some source for Haskell but no sign of a tutorial or any sample code. I'm just picking through but as a long shot does anyone have examples they could send me? I'm also looking to put together a page on haskellwiki once I'm up and running. The project seems like a fine way to sneak Haskell into existing project ;) Cheers, Dave (1) http://developers.facebook.com/thrift/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Doubting Haskell
Bryan O'Sullivan wrote: Stefan O'Rear wrote: I'll bet that breaks horribly in the not-so-corner case of /dev/tty. Actually, it doesn't. It seems to do a read behind the scenes if the buffer is empty, so it blocks until you type something. Indeed, and this is why even an unbuffered Handle needs to have a 1-character buffer, an interesting fact I discovered when implementing the I/O library. Cheers, Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stack overflow
Philip Armstrong wrote: > > On Sun, Feb 17, 2008 at 10:01:14PM +, Adrian Hey wrote: >> Philip Armstrong wrote: >>> Since no-one else has answered, I'll take a stab. >>> Obiously, you have a stack leak due to laziness somewhere >> >> I wouldn't say that was obvious, though it is certainly a >> possibility. >> >> I'm never exactly clear what people mean by a "stack leak". >> It seems some folk regard any algorithm that makes use of >> O(n) or worse stack space as a "stack leak". > > In my personal lexicon, a stack leak is one where you accumulate > unevaluated thunks on the stack. > > In this case, the combination of Data.Map not evaluating it's values > and Data.Binary being lazy is (I think) resulting in decode thunks > accumulating on the stack. > >> My opinion is that using O(n) or worse working memory when >> the job could be done in O(log n) or O(1) memory is certainly >> bad, but using O(n) stack is no worse in principle than using >> O(n) heap. But at the moment it is worse in practice with ghc, >> regretably :-( > > I'd agree with this entirely. > >>> In fact, a little experimentation has revealed that this: >>> >>> do >>>[path] <- getArgs >>>m <- liftM decode (BS.readFile path)::IO [((Int, Maybe String), Int)] >>>putStrLn . show . findMax . fromAscList $ m >>> >>> will work just fine. No extra evaluation needed at all! I'll leave it >>> to the Haskell gurus to explain what's going on... >> >> That's very interesting. Strangely if you use fromDistinctAscList >> instead (as used by the Binary instance get method) the problem >> re-appears. This is despite fromAscList making use of >> fromDistinctAscList. > > Yup. It's because (I've just realised) fromAscList is evaluating the > values returned by decode in order to build the Distinct Ascending > List to pass to fromDistinctAscList. A previous version I was going to > put up simply ran another function over the list before passing it to > the map constructor, which was not particularly elegant but also > worked. > > Data.Binary calls fromDistinctAscList to build the map, which is why > it gets into this mess. > >> BTW, I find this especially ironic as fromDistinctAscList is the perfect >> example what I was talking about in another thread (continuation passing >> madness caused by an irrational fear of stack use). > > In *some* cases, continuation passing can be quite a bit faster than > other approaches IIRC. I haven't looked at this bit of code though. > >> As to what's really going on here, I haven't figured it out and I'm not >> really inclined to try :-) > > I did try and do some profiling, but gave up when I realised that I'd > have to go sprinking SCCs around the core libraries, which would mean > recompiling Data.Map and friends... > > Heap profile graphs which assign everything to "CAF" are not very > helpful :) > > Phil > > Thanks to everyone who answered, this fixes my particular problem, and I think thanks to the comments I sort of vaguely understand what going on now. I run into this kind of esoteric laziness leaks from time to time and it's very frustrating -- I think that's about the only thing I don't like about Haskell. -- Grzegorz -- View this message in context: http://www.nabble.com/Stack-overflow-tp15479718p15543838.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] naming a data structure for weighted random selection without replacement
On Mon, 2008-02-18 at 11:37 +, Luke Palmer wrote: > On Feb 18, 2008 5:11 AM, Stuart Cook <[EMAIL PROTECTED]> wrote: > > A while ago I wrote a little data structure that allows weighted > > random selection-without-replacement from a collection of values in > > O(log n) time.[1] I'm now in the process of packaging it up for > > Hackage, but I'm looking for good names for both the type and its > > operations. > > I'm pretty sure it should have Random in the name whatever it is > called. Obvious idea: How about WeightedRandom? Michał ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] naming a data structure for weighted random selection without replacement
On Feb 18, 2008 5:11 AM, Stuart Cook <[EMAIL PROTECTED]> wrote: > A while ago I wrote a little data structure that allows weighted > random selection-without-replacement from a collection of values in > O(log n) time.[1] I'm now in the process of packaging it up for > Hackage, but I'm looking for good names for both the type and its > operations. I'm pretty sure it should have Random in the name whatever it is called. Luke > The name I have at the moment is "Pool", which I'm reasonably happy > with, but I wanted to see if I could find anything better. Asking on > #haskell got me a few responses: > > * Hat (cute, but conflicts with the program tracer) > * Bag (already way too overloaded) > * Bucket (not as suggestive as Pool) > > I have three main operations: > > * "pull" selects a random element, returning it and the remainder, but > fails if the pool is empty > * "pullN" selects /n/ distinct elements, returning them and the > remainder, but fails if the pool has too few elements > * "takeN" selects up to /n/ distinct elements, returning them and the > remainder, but returns no more elements than could be found in the > pool (analogous to Data.List.take) > > Any suggestions? > > > Stuart > > [1] Actually I delegated most of the work to the > data-structure-in-a-can that is Data.FingerTree, but that's another > story. > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] More powerful error handling
On Sun, 17 Feb 2008, Philippa Cowderoy wrote: > The nicest use would be for converting between a more specific error type > and a more general one that handles a wider range of errors - enabling us > to keep tighter track of which errors are possible in a given piece of > code. Bonus points for using it together with polymorphic variants where > rethrow becomes rather trivial. I guess it's about exception handling, not error handling, right? I thought that must be possible by plugging various exception types together, say data CustomException = IOExc IOError | NetworkExc NetworkException | ThreadExc ThreadingException Now you can turn any IOError to CustomException by wrapping it with IOExc. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] naming a data structure for weighted random selection without replacement
On Mon, 18 Feb 2008, Stuart Cook wrote: > A while ago I wrote a little data structure that allows weighted > random selection-without-replacement from a collection of values in > O(log n) time.[1] I'm now in the process of packaging it up for > Hackage, but I'm looking for good names for both the type and its > operations. Some ours ago I uploaded a package which would allow this: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/probability-0.2 You would stack a State transformer with a distribution as state and the inner monad is a Probability.Random.T. A similar example is here: http://darcs.haskell.org/probability/src/Numeric/Probability/Example/Collection.hs But maybe your concern is efficiency, and thus you need the special data structure. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Working with multiple time zones
Don Stewart wrote: Perhaps we should get a binding to tzset in the unix library? That's probably preferable to calling tzset() before every localtime_r. But perhaps we want a call that combines the putenv and the tzset, just so it exposes fewer implementation details. This is essentially an interface to the zoneinfo database rather than time functionality as such. Ideally there would be a better C interface to zoneinfo that wouldn't involve mucking around with (global) environment variables. -- Ashley Yakeley Seattle, WA ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stack overflow
On Sun, Feb 17, 2008 at 11:45:26PM +, Adrian Hey wrote: But I guess this rant is not much help to the OP :-) Can the Get Monad from Data.Binary be replaced by the one in Data.Binary.Strict.Get? Would probably require some hacking on the library I guess. Phil -- http://www.kantaka.co.uk/ .oOo. public key: http://www.kantaka.co.uk/gpg.txt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stack overflow
On Sun, Feb 17, 2008 at 10:01:14PM +, Adrian Hey wrote: Philip Armstrong wrote: Since no-one else has answered, I'll take a stab. Obiously, you have a stack leak due to laziness somewhere I wouldn't say that was obvious, though it is certainly a possibility. I'm never exactly clear what people mean by a "stack leak". It seems some folk regard any algorithm that makes use of O(n) or worse stack space as a "stack leak". In my personal lexicon, a stack leak is one where you accumulate unevaluated thunks on the stack. In this case, the combination of Data.Map not evaluating it's values and Data.Binary being lazy is (I think) resulting in decode thunks accumulating on the stack. My opinion is that using O(n) or worse working memory when the job could be done in O(log n) or O(1) memory is certainly bad, but using O(n) stack is no worse in principle than using O(n) heap. But at the moment it is worse in practice with ghc, regretably :-( I'd agree with this entirely. In fact, a little experimentation has revealed that this: do [path] <- getArgs m <- liftM decode (BS.readFile path)::IO [((Int, Maybe String), Int)] putStrLn . show . findMax . fromAscList $ m will work just fine. No extra evaluation needed at all! I'll leave it to the Haskell gurus to explain what's going on... That's very interesting. Strangely if you use fromDistinctAscList instead (as used by the Binary instance get method) the problem re-appears. This is despite fromAscList making use of fromDistinctAscList. Yup. It's because (I've just realised) fromAscList is evaluating the values returned by decode in order to build the Distinct Ascending List to pass to fromDistinctAscList. A previous version I was going to put up simply ran another function over the list before passing it to the map constructor, which was not particularly elegant but also worked. Data.Binary calls fromDistinctAscList to build the map, which is why it gets into this mess. BTW, I find this especially ironic as fromDistinctAscList is the perfect example what I was talking about in another thread (continuation passing madness caused by an irrational fear of stack use). In *some* cases, continuation passing can be quite a bit faster than other approaches IIRC. I haven't looked at this bit of code though. As to what's really going on here, I haven't figured it out and I'm not really inclined to try :-) I did try and do some profiling, but gave up when I realised that I'd have to go sprinking SCCs around the core libraries, which would mean recompiling Data.Map and friends... Heap profile graphs which assign everything to "CAF" are not very helpful :) Phil -- http://www.kantaka.co.uk/ .oOo. public key: http://www.kantaka.co.uk/gpg.txt LocalWords: fromDistinctAscList IIRC sprinking ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Re: problem with collection (container) class
Good point. Happily I improved the error message a couple of weeks ago, so it'll be better in the next release Simon | -Original Message- | From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Daniel Fischer | Sent: 08 February 2008 22:24 | To: Ben Franksen; haskell-cafe@haskell.org | Subject: Re: [Haskell-cafe] Re: problem with collection (container) class | | Am Freitag, 8. Februar 2008 22:14 schrieb Ben Franksen: | > If it's a bug then it is probably in 6.6.1 too, it just gets hidden by the | > fact that in 6.6.1 the -fglasgow-exts extensions cannot be activated | > separately. If you enable one of them, you get them all. | > | Thanks for the info, didn't know that. | | The problem was the error message, which didn't mention that each type | variable may appear only once in an instance head, which I had temporarily | forgotten. Then the message | | Leandro.hs:32:0: | Illegal instance declaration for `Container (Abb a b) a b' | (All instance types must be of the form (T a1 ... an) | where a1 ... an are distinct type *variables* | Use -XFlexibleInstances if you want to disable this.) | In the instance declaration for `Container (Abb a b) a b' | | looks rather confusing :) | | > Cheers | > Ben | > | Cheers, | Daniel | ___ | Haskell-Cafe mailing list | Haskell-Cafe@haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
