Re: [Haskell-cafe] '#' in literate haskell
John MacFarlane wrote: Can anyone explain why ghc does not treat the following as a valid literate haskell program? - test.lhs # This is a test foo = reverse . words I believe this is an artifact of ghc trying to parse cpp style line number information: foo.lhs # 123 foo.foo t = will print this error: foo.foo:124:6: parse error on input `' Bertram ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cabal
Thomas Schilling wrote: Cabal-the-install-tool (package cabal-install) is actually a different program that sits on top of Cabal-the-library, and it is in fact what really provides the real advantages. Together with Hackage this is what provides the killer feature of cabal install foo, however it relies on the building features and meta-data of Cabal. As I understand it, that's also a seperate download. (Whereas the cabal library comes with GHC.) One day, if I feel hard-core enough, I might try this tool. (Assuming it works on Windows...) It sounds potentially useful. (Although most actual packages typically have one, maybe two dependencies that aren't already installed, if that.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Go Haskell! - array libraries
On 30/11/2008, at 11:36, Don Stewart wrote: Should mutable arrays have list-like APIs? All the usual operations, just in-place and destructive where appropriate? I don't know. To be honest, I don't think that the term mutable array describes a single data structure. For instance, one of the central questions which unveils a whole bunch of design possibilities is: can mutable arrays be concatenated and how does that work if yes? Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Go Haskell! - array libraries
Should mutable arrays have list-like APIs? All the usual operations, just in-place and destructive where appropriate? I don't know. To be honest, I don't think that the term mutable array describes a single data structure. For instance, one of the central questions which unveils a whole bunch of design possibilities is: can mutable arrays be concatenated and how does that work if yes? wrt the first part: within a pure functional language, mutable arrays are something I (am forced to) choose when the implementation is unable to see some essential optimization opportunities in the way I am using immutable arrays; whenever I am forced to go down that route, I'd at least like to have an equivalent set of operations. The move from immutable arrays to mutable arrays is painful enough as it is. So the suggested design criterion would be: as uniform an API as possible, just that immutable arrays cannot make some essential performance guarantees and some operations sit a little uncomfortably in a librart where those guarantees are important. wrt the second part: I'm not sure whether you'll be able to choose a single one of those design possibilities as the only one (perhaps the concatenation is about simpler code, so virtual concatenation would be sufficient and copying possible, but perhaps the goal was locality, so copying would be needed, or perhaps a mixture of both, and the limited disruption in locality is less expensive than the cost of copying, ..), so you might want to expose several of them, with a separate way of selecting a default or I-don't-care choice (imilar to why you have several array libs at present, just that there should be a common API and documentation of design alternatives/rationales;-). -- Btw, it would really be nice if packages took a hint from academic publishing: good papers are expected not only (a) to provide new content, but also (b) to position that content wrt related work and (c) to make explicit what the new contributions/goals are. As forks have become more common on hackage, perhaps .cabal files could be extended with two fields, pointing to related packages (this is more specific than category, linking to packages that might be used instead or in combination with the current package) and giving the rationale/high-lights for the package in text form. In the meantime, it would be great if all packages came with good old README files, which should be linked from the .cabal-based package descriptions on hackage, covering all those useful bits of information that are not yet covered in .cabal files, and giving an overview of what the package is about if the package does not have its own webspace (as is often the case). That would improve on the current situation, where sometimes all one has to go on is the package name and a one-liner description. Random example: looking at hackage package categories, I'd look for array libraries under 'data structures', but they are actually spread over 'data structures', 'data', and 'maths' (perhaps others?). Once I've found one, say 'vector' or 'uvector', what do the package descriptions tell me about the packages and their relation, or their relative advantages? The descriptions are brief, the home pages are actually home repositories, the haddocks seem to have details only, no overview, and from the references/authors/uvector README, one might think these are actually the same library, sequential libs spun off from the same data-parallelism project; only that the haddock details suggest that these libraries are quite different. How? Why? What other alternatives are there? Note that I'm not attacking any specific packages, I would just encourage all package authors to try and see their packages from the perspective of a hackage user: what information does the user look for, what information does the package description offer? -- While we're on the topic: hackage has grown so much and so rapidly, that it might be worthwhile to have a hackage editor, not in the sense of accepting/rejecting packages (not wanted at present), nor in the sense of objective quality measurements (that is in the process of being automated, according to Duncan), but in the sense of trying to guarantee a subjectively useful overall presentation (category organisation, finding and putting side-by-side related packages despite different names/categories, suitability of package descriptions, getting package authors to talk, etc.). And no, I'm not volunteering!-) But I would imagine that someone might find this a useful way of contributing. Such a hackage editor would also be able to give the Haskell Community Report editor a hand by summarizing hackage activity/trends and highlighting interesting projects that the HCAR editor might want to solicit reports for. From my own time as HCAR editor, I recall finding and chasing interesting projects as well as deciding how to structure the toolslibraries sections as
Re: [Haskell-cafe] Compilers
Hi Daniel, On Sun, Nov 30, 2008 at 08:31:15 -0500, [EMAIL PROTECTED] wrote: [EMAIL PROTECTED]:~/lhc darcs get --partial http://code.haskell.org/lhc Invalid repository: http://code.haskell.org/lhc darcs failed: failed to fetch: http://code.haskell.org/lhc/_darcs/inventory ExitFailure 1 There's a hashed_inventory in lhc/_darcs, but no inventory. Is that a darcs2 vs. darcs1 incompatibility and I'm just screwed or is the repo broken? There are two issues here. One is that the LHC repository is indeed a darcs 2 repository and you appear to have darcs 1 on your machine. I think upgrading to darcs 2 would be a very good idea, and I'm sure the darcs community would be happy to help you with this. The second issue is that our forward-compatibility detector was likely buggy in darcs 1.0.9. The response darcs 1.0.9 should have given you was something like this: darcs failed: Can't understand repository format: hashed darcs failed: Can't understand repository format: darcs-2 Unfortunately, the relationship between hashed and darcs 2 repositories is slightly confusing. Basically you need a darcs 2 client if you see hashed_inventory, but it does not necessarily mean there is an incompatibility. I hope that the following snippet from the darcs 2.1.0 release announcement can help clear this up: What should I do? - Upgrade! Binary versions should be available shortly, either from your favourite package distributor or by third party contributors. Other than installing the new darcs, no action is required on your part to perform this upgrade. Darcs 2, including this particular version, is 100% compatible with your pre-existing repositories. If you have not done so already, you should consider using the hashed repository format in place of your current old-fashioned repositories. This format offers greater protection against accidental corruption, better support for case insensitive file systems. It also provides some very nice performance features, including lazy fetching of patches and a global cache (both optional). If darcs 1 compatibility is not a concern, you could also upgrade your repositories all the way to the darcs 2 format. In addition to the robustness and performance features above, this gives you the improved merging semantics and conflicts handling that give darcs 2 its name. More details about upgrading to darcs 2 here: http://wiki.darcs.net/index.html/DarcsTwo Another clarification - To be clear, we say that hashed repositories are backward-compatible. This means that darcs 2 clients can pull and push patches between them and old-fashioned repostiories. On the other hand, interacting with the hashed repositories themselves requires a darcs 2 client. Thanks! -- Eric Kow http://www.nltg.brighton.ac.uk/home/Eric.Kow PGP Key ID: 08AC04F9 signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Permutations
OK, so here's something just for fun: Given a list of items, find all possible *unique* permutations of that list. (E.g., the input list is explicitly _allowed_ to contain duplicates. The output list should not contain any duplicate permutations.) I've found one simple way to do this, but I'm sure there are multiple valid approaches. So let's see what people come up with. ;-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Permutations
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On Nov 30, 2008, at 9:03 AM, Andrew Coppin wrote: OK, so here's something just for fun: Given a list of items, find all possible *unique* permutations of that list. (E.g., the input list is explicitly _allowed_ to contain duplicates. The output list should not contain any duplicate permutations.) I've found one simple way to do this, but I'm sure there are multiple valid approaches. So let's see what people come up with. ;-) Seems a bit easy, I think. Data.List.permutations . nub -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.8 (Darwin) iEYEARECAAYFAkkyuesACgkQye5hVyvIUKn1bQCgwEOBQsDg7L2O6JneaMROZUtw AXwAnjkUOBFTjkf2G41BBG4++tFjpRzn =a1z/ -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Permutations
Am Sonntag, 30. November 2008 16:03 schrieb Andrew Coppin: OK, so here's something just for fun: Given a list of items, find all possible *unique* permutations of that list. (E.g., the input list is explicitly _allowed_ to contain duplicates. The output list should not contain any duplicate permutations.) I've found one simple way to do this, but I'm sure there are multiple valid approaches. So let's see what people come up with. ;-) Needs an Ord constraint: inserts :: [a] - [a] - [[a]] inserts [] ys = [ys] inserts xs [] = [xs] inserts xs@(x:xt) ys@(y:yt) = [x:zs | zs - inserts xt ys] ++ [y:zs | zs - inserts xs yt] uniquePermutations :: Ord a = [a] - [[a]] uniquePermutations = foldr (concatMap . inserts) [[]] . group . sort The (group . sort) part could be done with just an Eq constraint, but much less efficiently. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Permutations
On Sun, Nov 30, 2008 at 9:06 AM, Jake Mcarthur [EMAIL PROTECTED] wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On Nov 30, 2008, at 9:03 AM, Andrew Coppin wrote: OK, so here's something just for fun: Given a list of items, find all possible *unique* permutations of that list. (E.g., the input list is explicitly _allowed_ to contain duplicates. The output list should not contain any duplicate permutations.) I've found one simple way to do this, but I'm sure there are multiple valid approaches. So let's see what people come up with. ;-) Seems a bit easy, I think. Data.List.permutations . nub That is not what he meant. Given: [1,1,2,2] The results should be: [1,1,2,2] [1,2,2,1] [2,2,1,1] [1,2,1,2] [2,1,2,1] [2,1,1,2] Assuming I didn't miss any... Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Permutations
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On Nov 30, 2008, at 10:17 AM, Luke Palmer wrote: On Sun, Nov 30, 2008 at 9:06 AM, Jake Mcarthur [EMAIL PROTECTED] wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On Nov 30, 2008, at 9:03 AM, Andrew Coppin wrote: OK, so here's something just for fun: Given a list of items, find all possible *unique* permutations of that list. (E.g., the input list is explicitly _allowed_ to contain duplicates. The output list should not contain any duplicate permutations.) I've found one simple way to do this, but I'm sure there are multiple valid approaches. So let's see what people come up with. ;-) Seems a bit easy, I think. Data.List.permutations . nub That is not what he meant. Given: [1,1,2,2] The results should be: [1,1,2,2] [1,2,2,1] [2,2,1,1] [1,2,1,2] [2,1,2,1] [2,1,1,2] Assuming I didn't miss any... Oh, I see. Okay, I see why that would be an interesting exercise then. Thanks for clearing that up. - - Jake -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.8 (Darwin) iEYEARECAAYFAkkyvlkACgkQye5hVyvIUKmMcwCgwQVbIB2IIV4yuS004K+JtGpw b2YAoI9PihnG/R7W9Kl4884tgwPwOrYb =MfCa -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Permutations
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On Nov 30, 2008, at 10:17 AM, Luke Palmer wrote: On Sun, Nov 30, 2008 at 9:06 AM, Jake Mcarthur [EMAIL PROTECTED] wrote: Seems a bit easy, I think. Data.List.permutations . nub That is not what he meant. Given: [1,1,2,2] The results should be: [1,1,2,2] [1,2,2,1] [2,2,1,1] [1,2,1,2] [2,1,2,1] [2,1,1,2] Heh, after a couple more seconds of thought, reversing the two composed functions fixes it: nub . permutations Of course, neither my previous nonsolution nor this solution are efficient for long lists, but I think it serves as a decent reference implementation at least. - - Jake -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.8 (Darwin) iEYEARECAAYFAkkyv2wACgkQye5hVyvIUKmjBwCfSYebuPUNSqENppJG9sVxy+wB ehYAoJjEY9M2o8ZqgN7R5pQ9x2PF54Ew =ipuT -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Permutations
Jake Mcarthur wrote: Seems a bit easy, I think. Data.List.permutations . nub Damnit, I specifically looked through Data.List to see if a permutation function exists... how did I miss that?! o_O (Hoogle didn't find it either.) Well either way, it's still entertaining to find ways to implementing it yourself. ;-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers
Am Sonntag, 30. November 2008 15:57 schrieb Eric Kow: Hi Daniel, On Sun, Nov 30, 2008 at 08:31:15 -0500, [EMAIL PROTECTED] wrote: [EMAIL PROTECTED]:~/lhc darcs get --partial http://code.haskell.org/lhc Invalid repository: http://code.haskell.org/lhc darcs failed: failed to fetch: http://code.haskell.org/lhc/_darcs/inventory ExitFailure 1 There's a hashed_inventory in lhc/_darcs, but no inventory. Is that a darcs2 vs. darcs1 incompatibility and I'm just screwed or is the repo broken? There are two issues here. One is that the LHC repository is indeed a darcs 2 repository Yes, and as Austin told me, it was updated to darcs-2 format yesterday or the day before (depending on time-zone), so one might just consider it bad timing, except and you appear to have darcs 1 on your machine. I think upgrading to darcs 2 would be a very good idea, and I'm sure the darcs community would be happy to help you with this. I am now a proud owner of darcs-2.1.2, the source distribution built without problems :), make test said All tests successful! three times :D Sorry to deprive you of the pleasure of helping. I had problems with a darcs-2 prerelease earlier, that's why I was pessimistic about getting darcs-2 to work on my old system, the binary wouldn't work because it needed newer libs than I have (and updating those would wreak havoc on other components), and the one from the darcs repo needed a newer autoconf than I have, yay for source releases. The second issue is that our forward-compatibility detector was likely buggy in darcs 1.0.9. The response darcs 1.0.9 should have given you was something like this: darcs failed: Can't understand repository format: hashed darcs failed: Can't understand repository format: darcs-2 I've always found darcs' predictive powers somewhat lacking. Seriously, it might be a good idea to have an error message like darcs failed: Can't understand repository format, may be new format or broken. because that would give a starting point for resolving the problem (darcs-2 was conspicuous enough here that I thought of that possibility, but maybe darcs users not suscribed to the relevant lists wouldn't). Unfortunately, the relationship between hashed and darcs 2 repositories is slightly confusing. Basically you need a darcs 2 client if you see hashed_inventory, but it does not necessarily mean there is an incompatibility. I hope that the following snippet from the darcs 2.1.0 release announcement can help clear this up: What should I do? - Upgrade! Binary versions should be available shortly, either from your favourite package distributor or by third party contributors. Please, do not drop source distributions anyone, binaries tend to work on a much smaller set of systems, source can build against more library versions. Cheers, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers
On Sat, Nov 29, 2008 at 05:10:24PM -0800, Don Stewart wrote: Oh golly. I never put DrIFT on cabal, apparently whomever tried to cabalize it didn't include the ghc driver script, and also appeared to just drop the documentation from the package altogether. It is things like that that make it very hard to get behind cabal, why was DrIFT crippled just so it can be put on cabal? If cabal wasn't powerful enough to compile DrIFT, and we already had a perfectly good way of compiling it, why the need to shoehorn it in and cause this problem? sigh. Sounds like a problem with the packaging of DrIFT for Hackage, not with Cabal per se. This can happen if the package author doesn't do the conversion from ad-hoc make systems to cabal -- metadata that was implicit in autoconf+make can be lost. This is indicative of problems with some factions of the cabal community in general though. That somehow the idea of getting a package into cabal was more important than the package actually working. Like it or not, the cabal project has accumulated some supporters who have an agenda where promoting cabal is more important than the actual value of cabal to a project. This has made for a very hostile enviornment to be a developer in. Perhaps the DrIFT maintainer could package it correctly, so that it can be used with the ~1000 other libraries on Hackage. DrIFT is maintained by me and already can be used with the ~1000 other libraries on hackage. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Permutations
import Data.List eqPerms [] = [[]] eqPerms xs = [x:xt | x - nub xs, xt - eqPerms $ delete x xs] On 30 Nov 2008, at 18:03, Andrew Coppin wrote: OK, so here's something just for fun: Given a list of items, find all possible *unique* permutations of that list. (E.g., the input list is explicitly _allowed_ to contain duplicates. The output list should not contain any duplicate permutations.) I've found one simple way to do this, but I'm sure there are multiple valid approaches. So let's see what people come up with. ;-) ___ 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] Permutations
Am Sonntag, 30. November 2008 17:29 schrieb Andrew Coppin: Jake Mcarthur wrote: Seems a bit easy, I think. Data.List.permutations . nub Damnit, I specifically looked through Data.List to see if a permutation function exists... how did I miss that?! o_O (Hoogle didn't find it either.) Seems to be new, Data.List in 6.8.3 doesn't have it. Well either way, it's still entertaining to find ways to implementing it yourself. ;-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers
On Sat, Nov 29, 2008 at 09:00:48PM -0500, Brandon S. Allbery KF8NH wrote: On 2008 Nov 29, at 20:02, John Meacham wrote: Oh golly. I never put DrIFT on cabal, apparently whomever tried to cabalize it didn't include the ghc driver script, and also appeared to just drop the documentation from the package altogether. It is things like that that make it very hard to get behind cabal, why was DrIFT crippled just so it can be put on cabal? If cabal wasn't powerful enough to compile DrIFT, and we already had a perfectly good way of compiling it, why the need to shoehorn it in and cause this problem? sigh. Blaming Cabal for Audrey doing a quick-and-dirty translation (because she didn't have a whole lot of time to spend online and wasn't really familiar with Cabal or Hackage) is just digging for excuses. Hmm? This wasn't done by Audrey, all the hackage/cabal stuff she has done for my projects has been with my blessing. (and thanks) And creating a crippled version of something you wrote and passing it off as the original, in a way that clearly breaks things for other people definitely is something to get upset about. And no, that is not a technical problem with cabal itself, but it does make me worry about the motivations of some in the project when that sort of breakage seemed like a good idea to someone. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell, successing crossplatform API standart
Haxr provides a basic implementation of the XML-RPC protocol, and while it looks like it doesn' t build on 6.10 at the moment, getting it to build shouldn't be a problem, and although it doesn't appear to be under active development, it does seem to be getting maintenance uploads. [1] These days, however, web services seem to be moving towards a RESTful model with a JSON layer and there are plenty of JSON libraries on hackage, which you could just throw over the fastCGI bindings. Alternately you could try JSON over one of the really lightweight haskell web servers, such as shed [2] or lucu [3]. If you go the latter route, I'd love to hear how it went. [1] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/haxr [2] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/httpd- shed [3] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Lucu Regards, Sterl ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Permutations
Daniel Fischer wrote: Am Sonntag, 30. November 2008 17:29 schrieb Andrew Coppin: Jake Mcarthur wrote: Seems a bit easy, I think. Data.List.permutations . nub Damnit, I specifically looked through Data.List to see if a permutation function exists... how did I miss that?! o_O (Hoogle didn't find it either.) Seems to be new, Data.List in 6.8.3 doesn't have it. Ah, I see. That'll be why my copy of GHC 6.8.2 doesn't have it! :-D ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers
On Sun, Nov 30, 2008 at 17:45:55 +0100, Daniel Fischer wrote: I am now a proud owner of darcs-2.1.2, the source distribution built without problems :), make test said All tests successful! three times :D Sorry to deprive you of the pleasure of helping. :-) darcs failed: Can't understand repository format: hashed darcs failed: Can't understand repository format: darcs-2 I've always found darcs' predictive powers somewhat lacking. Seriously, it might be a good idea to have an error message like This was just a bug in darcs. The feature has been there for a while, but was not sufficiently well tested. Anyway, it's been fixed since May. darcs failed: Can't understand repository format, may be new format or broken. I think we would welcome some kind of patch to rephrase the messages above to hint that that the reason it could not understand these format elements was because they may be new. Upgrade! Binary versions should be available shortly, either from your favourite package distributor or by third party contributors. Please, do not drop source distributions anyone, binaries tend to work on a much smaller set of systems, source can build against more library versions. The darcs team will always release a source tarball on its releases (the next one scheduled for mid January) Cheers, -- Eric Kow http://www.nltg.brighton.ac.uk/home/Eric.Kow PGP Key ID: 08AC04F9 signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Permutations
First line is necessary, because the second line is written in assumption that the first element of a permutation does really exist. On 30 Nov 2008, at 19:49, Andrew Coppin wrote: Miguel Mitrofanov wrote: eqPerms [] = [[]] eqPerms xs = [x:xt | x - nub xs, xt - eqPerms $ delete x xs] Well, that's one way... ;-) I'm still not precisely sure why the first line must exist, but it seems no matter which way round you do it, that line is needed. Probably due to some subtlety of the list monad... I'm not sure how efficient using the delete function is, but this version definitely has the virtues of brevity and readbility. ___ 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
[Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
On 11/23/08 13:52, Luke Palmer wrote: 2008/11/23 Larry Evans [EMAIL PROTECTED]: http://www.muitovar.com/monad/moncow.xhtml#list contains a cross function which calculates the cross product of two lists. That attached does the same but then used cross on 3 lists. Naturally, I thought use of fold could generalize that to n lists; however, I'm getting error: You should try writing this yourself, it would be a good exercise. To begin with, you can mimic the structure of cross in that tutorial, but make it recursive. After you have a recursive version, you might try switching to fold or foldM. The type of the function will not involve tuples, since they can be arbitrary length (dynamic-length tuples are not supported in Haskell; we use lists for that). cross :: [[a]] - [[a]] However, list's contain elements all of the same type. What the following boost post: http://thread.gmane.org/gmane.comp.lib.boost.devel/182797/focus=182915 demonstrated was, AFAICT, the c++ template metaprogramming counterpart to the moncow haskell cross. Now, AFAICT, the boost vault directory: http://www.boostpro.com/vault/index.php?PHPSESSID=ab51206c9d980155d142f5bcef8e00eedirection=0order=directory=Template%20Metaprogramming in the cross_nproduct_view_test.zip, contains what I'm looking for in haskell. I'm guessing that: templateclass Row, class Columnstruct row_view; corresponds to the haskell tuple type (row,column) I'm trying to confirm that by printing out the typename in a formated form, but I'm having trouble doing that at the moment: http://preview.tinyurl.com/66x4nx Is there some version of haskell, maybe template haskell, that can do that, i.e. instead of: cross::[[a]] - [[a]] have: crossn::[a0]-[a1]-...-[an] - [(a0,a1,...,an)] ? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
On Sun, Nov 30, 2008 at 10:25 AM, Larry Evans [EMAIL PROTECTED] wrote: Is there some version of haskell, maybe template haskell, that can do that, i.e. instead of: cross::[[a]] - [[a]] have: crossn::[a0]-[a1]-...-[an] - [(a0,a1,...,an)] Ah yes! This is straightforward usage of the list monad. I suggest applicative notation: import Control.Applicative (,,,) $ xs0 * xs1 * xs2 * xs3 Or alternatively: import Control.Monad liftM4 (,,,) xs0 xs1 xs2 xs3 (I would have used liftA4, but it's not defined. The definition looks a lot like the first example :-) This notation seems a bit magical, but you can build what you want using a simple binary cross: cross :: [a] - [b] - [(a,b)] It's just kind of a pain (you build [(a,(b,(c,d)))] and then flatten out the tuples). The applicative notation is a neat little trick which does this work for you. If you're asking whether crossn, as a single function which handles arbitrarily many arguments, can be defined, the short answer is no. I dare you to come up with a case in which such function adds more than cursory convenience. The long answer is yes, but you don't want to. It involves mad typeclass hackery, and it doesn't buy you very much. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
On Sun, Nov 30, 2008 at 9:30 AM, Luke Palmer [EMAIL PROTECTED] wrote: cross :: [a] - [b] - [(a,b)] It's just kind of a pain (you build [(a,(b,(c,d)))] and then flatten out the tuples). The applicative notation is a neat little trick which does this work for you. It seems to me like this would all be easy if (a,b,c,d) was sugar for (a,(b,(c,d))), and I can't see a disadvantage to that. --Max ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Go Haskell! - array libraries
On Sunday 30 November 2008 6:28:29 am Roman Leshchinskiy wrote: On 30/11/2008, at 11:36, Don Stewart wrote: Should mutable arrays have list-like APIs? All the usual operations, just in-place and destructive where appropriate? I don't know. To be honest, I don't think that the term mutable array describes a single data structure. For instance, one of the central questions which unveils a whole bunch of design possibilities is: can mutable arrays be concatenated and how does that work if yes? I don't know about concatenation, but it is useful for them to be able to be zipped. For instance: schwartz f arr = do keys - cloneWith f arr pairs - zip keys arr sortBy (comparing fst) pairs (cloneWith should construct a new array where new[i] = f (old[i])) is a mutable sort of arr using the comparison compare e e' = compare (f e) (f e') caching the results of f for each element. This, obviously, takes advantage of the fact that sorting the zipped array mutably updates the underlying (original) arrays. On the other hand, I could see such an operation easily leading to bugs if it slips your mind that changing one array can effect another (maybe it should be called unsafeZip :)). -- Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
On 2008 Nov 30, at 12:43, Max Rabkin wrote: On Sun, Nov 30, 2008 at 9:30 AM, Luke Palmer [EMAIL PROTECTED] wrote: cross :: [a] - [b] - [(a,b)] It's just kind of a pain (you build [(a,(b,(c,d)))] and then flatten out the tuples). The applicative notation is a neat little trick which does this work for you. It seems to me like this would all be easy if (a,b,c,d) was sugar for (a,(b,(c,d))), and I can't see a disadvantage to that. No disadvantage aside from it making tuples indistinguishable from lists. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [EMAIL PROTECTED] system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED] electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
On Sun, 30 Nov 2008, Brandon S. Allbery KF8NH wrote: On 2008 Nov 30, at 12:43, Max Rabkin wrote: It seems to me like this would all be easy if (a,b,c,d) was sugar for (a,(b,(c,d))), and I can't see a disadvantage to that. No disadvantage aside from it making tuples indistinguishable from lists. No, they'd still have statically known length and be heterogenous, it would just change some strictness properties. Ganesh ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Permutations
Daniel Fischer wrote: Needs an Ord constraint: inserts :: [a] - [a] - [[a]] inserts [] ys = [ys] inserts xs [] = [xs] inserts xs@(x:xt) ys@(y:yt) = [x:zs | zs - inserts xt ys] ++ [y:zs | zs - inserts xs yt] Heh, I came up with basically the same thing. I'd call this function 'merges' - it returns all possibilities for merging two given lists. uniquePermutations :: Ord a = [a] - [[a]] uniquePermutations = foldr (concatMap . inserts) [[]] . group . sort Which can also be written as uniquePermutations = foldM merges [] . group . sort Bertram ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
On 11/30/08 11:30, Luke Palmer wrote: On Sun, Nov 30, 2008 at 10:25 AM, Larry Evans [EMAIL PROTECTED] wrote: Is there some version of haskell, maybe template haskell, that can do that, i.e. instead of: cross::[[a]] - [[a]] have: crossn::[a0]-[a1]-...-[an] - [(a0,a1,...,an)] Ah yes! This is straightforward usage of the list monad. I suggest applicative notation: import Control.Applicative (,,,) $ xs0 * xs1 * xs2 * xs3 Or alternatively: import Control.Monad liftM4 (,,,) xs0 xs1 xs2 xs3 (I would have used liftA4, but it's not defined. The definition looks a lot like the first example :-) This notation seems a bit magical, but you can build what you want using a simple binary cross: cross :: [a] - [b] - [(a,b)] It's just kind of a pain (you build [(a,(b,(c,d)))] and then flatten out the tuples). The applicative notation is a neat little trick which does this work for you. Thanks Luke. I'll try that. If you're asking whether crossn, as a single function which handles arbitrarily many arguments, can be defined, the short answer is no. I dare you to come up with a case in which such function adds more than cursory convenience. The following post: http://thread.gmane.org/gmane.comp.lib.boost.devel/182797 shows at least one person that would find it useful, at least in c++. Of course maybe it would be less useful in haskell. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
On Sun, Nov 30, 2008 at 10:43 AM, Max Rabkin [EMAIL PROTECTED] wrote: On Sun, Nov 30, 2008 at 9:30 AM, Luke Palmer [EMAIL PROTECTED] wrote: cross :: [a] - [b] - [(a,b)] It's just kind of a pain (you build [(a,(b,(c,d)))] and then flatten out the tuples). The applicative notation is a neat little trick which does this work for you. It seems to me like this would all be easy if (a,b,c,d) was sugar for (a,(b,(c,d))), and I can't see a disadvantage to that. This is a tricky and subtle question, actually. It has to do with the lifting of tuples; those two types have different domains. For example, the element in the latter: (1,(2,_|_)) Has no corresponding element in the former (there is (1,2,_|_,_|_), but that corresponds to (1,(2,(_|_,_|_))) ). Now, if tuples in Haskell were unlifted, meaning (_|_,_|_) = _|_, then there would be no issue. But that has far-reaching consequences in the language design, among which the seq function would have to be eliminated (many people would not be opposed to this). Also usage of unlifted tuples can cause subtle space leaks. Now, what all this domain theory has to do with practical issues, I'm not sure. But you can't just do a slick replacement, because it changes properties of programs that did not know the difference. Frankly, I would prefer what you propose as well (actually, I would prefer it to mean (a,(b,(c,(d,(), but it's the same idea). But the change is difficult and requires thought. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
Tuples would still be distinguishable from lists, since cons changes their type: (b,c,d) and (a,b,c,d) would have different types, while [b,c,d] and [a,b,c,d] wouldn't. On 30 Nov 2008, at 20:48, Brandon S. Allbery KF8NH wrote: On 2008 Nov 30, at 12:43, Max Rabkin wrote: On Sun, Nov 30, 2008 at 9:30 AM, Luke Palmer [EMAIL PROTECTED] wrote: cross :: [a] - [b] - [(a,b)] It's just kind of a pain (you build [(a,(b,(c,d)))] and then flatten out the tuples). The applicative notation is a neat little trick which does this work for you. It seems to me like this would all be easy if (a,b,c,d) was sugar for (a,(b,(c,d))), and I can't see a disadvantage to that. No disadvantage aside from it making tuples indistinguishable from lists. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [EMAIL PROTECTED] system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED] electrical and computer engineering, carnegie mellon university KF8NH ___ 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
[Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
On 11/30/08 12:04, Larry Evans wrote: [snip] The following post: http://thread.gmane.org/gmane.comp.lib.boost.devel/182797 shows at least one person that would find it useful, at least in c++. Of course maybe it would be less useful in haskell. One thing that maybe confusing things is that the c++ template code calculated a crossproduct of types, not values. The haskell code: cross::[[a]]-[[a]] calculate a cross product of values. Sorry if that was unclear. I was trying to use haskell to guide me in doing something similar with c++ template metaprogramming. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
On Sun, Nov 30, 2008 at 11:04 AM, Larry Evans [EMAIL PROTECTED] wrote: The following post: http://thread.gmane.org/gmane.comp.lib.boost.devel/182797 shows at least one person that would find it useful, at least in c++. Of course maybe it would be less useful in haskell. The line: typedef boost::mpl::vector T1Variants, T2Variants, T3Variants TT; Has the number of lists hard-coded as 3, and does not abstract over it. This corresponds to the 3 in liftA3, or the number of *s in the expression. Abstracting over the number and types of arguments is something neither C++ nor Haskell is very good at. But in order to be able to do any abstraction using such a variable-argument function, the type systems of these languages would have to increase in complexity by quite a lot. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
Am Sonntag, 30. November 2008 19:04 schrieb Larry Evans: If you're asking whether crossn, as a single function which handles arbitrarily many arguments, can be defined, the short answer is no. I dare you to come up with a case in which such function adds more than cursory convenience. The following post: http://thread.gmane.org/gmane.comp.lib.boost.devel/182797 shows at least one person that would find it useful, at least in c++. Of course maybe it would be less useful in haskell. And having genericCross xs1 xs2 being able to be [(x,y) | x - xs1, y - xs2] \xs3 - cross3 xs1 xs2 xs3 \xs3 xs4 - cross4 xs1 xs2 xs3 xs4 ... would open up the possibility for a great number of bugs, I believe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
On 11/30/08 12:27, Luke Palmer wrote:
On Sun, Nov 30, 2008 at 11:04 AM, Larry Evans [EMAIL PROTECTED] wrote:
The following post:
http://thread.gmane.org/gmane.comp.lib.boost.devel/182797
shows at least one person that would find it useful, at least in
c++. Of course maybe it would be less useful in haskell.
The line:
typedef boost::mpl::vector T1Variants, T2Variants, T3Variants TT;
Has the number of lists hard-coded as 3, and does not abstract over
it. This corresponds to the 3 in liftA3, or the number of *s in
the expression.
Abstracting over the number and types of arguments is something
neither C++ nor Haskell is very good at. But in order to be able to
do any abstraction using such a variable-argument function, the type
systems of these languages would have to increase in complexity by
quite a lot.
Luke
True, but if you look at the cross_nproduct_view template:
{--cut here--
template
class Domains
struct
cross_nproduct_view
: fold
Domains
, cross_product_one
, cross_product_viewarg2,arg1
::type
{
};
}--cut here--
You'll see Domains can be an mpl::vector of any
length. The cross_nproduct_view_test.cpp tests
with a 3 element Domains:
typedef
mpl::vector
mpl::range_cint,0,4
, mpl::range_cint,100,103
, mpl::range_cint,2000,2002
domains;
The cross_nproduct_view template and test driver
are found in the cross_nproduct_view.zip file here:
http://preview.tinyurl.com/5ar9g4
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] manipulating predicate formulae
Hi, Are there any Haskell libraries around for manipulating predicate formulae? I had a look on hackage but couldn't spot anything. I am generating complex expressions that I'd like some programmatic help in simplifying. Cheers, Ganesh ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cabal
andrewcoppin: Thomas Schilling wrote: Cabal-the-install-tool (package cabal-install) is actually a different program that sits on top of Cabal-the-library, and it is in fact what really provides the real advantages. Together with Hackage this is what provides the killer feature of cabal install foo, however it relies on the building features and meta-data of Cabal. As I understand it, that's also a seperate download. (Whereas the cabal library comes with GHC.) One day, if I feel hard-core enough, I might try this tool. (Assuming it works on Windows...) It sounds potentially useful. (Although most actual packages typically have one, maybe two dependencies that aren't already installed, if that.) *if* .. *might* .. *assuming* .. *potentially* .. *maybe* .. *if*.. You could have built it by now! Source: http://hackage.haskell.org/packages/archive/cabal-install/0.6.0/cabal-install-0.6.0.tar.gz Dependencies that aren't in core: http://hackage.haskell.org/packages/archive/HTTP/3001.1.5/HTTP-3001.1.5.tar.gz http://hackage.haskell.org/packages/archive/zlib/0.5.0.0/zlib-0.5.0.0.tar.gz Note the last one assumes you have zlib the C library installed. This should be straight forward to obtain. Enjoy. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers
john: On Sat, Nov 29, 2008 at 09:00:48PM -0500, Brandon S. Allbery KF8NH wrote: On 2008 Nov 29, at 20:02, John Meacham wrote: Oh golly. I never put DrIFT on cabal, apparently whomever tried to cabalize it didn't include the ghc driver script, and also appeared to just drop the documentation from the package altogether. It is things like that that make it very hard to get behind cabal, why was DrIFT crippled just so it can be put on cabal? If cabal wasn't powerful enough to compile DrIFT, and we already had a perfectly good way of compiling it, why the need to shoehorn it in and cause this problem? sigh. Blaming Cabal for Audrey doing a quick-and-dirty translation (because she didn't have a whole lot of time to spend online and wasn't really familiar with Cabal or Hackage) is just digging for excuses. Hmm? This wasn't done by Audrey, all the hackage/cabal stuff she has done for my projects has been with my blessing. (and thanks) And creating a crippled version of something you wrote and passing it off as the original, in a way that clearly breaks things for other people definitely is something to get upset about. And no, that is not a technical problem with cabal itself, but it does make me worry about the motivations of some in the project when that sort of breakage seemed like a good idea to someone. Looks like it was packaged by gwern when he was trawling the archives finding releases that weren't on Hackage -- and yes, several of the things he uploaded were incorrectly packages in some way or another. If I grab drift from Hackage though, $ cabal install drift Resolving dependencies... Configuring DrIFT-2.2.3... Preprocessing executables for DrIFT-2.2.3... Building DrIFT-2.2.3... Linking dist/build/DrIFT/DrIFT ... Installing executable(s) in /home/dons/.cabal/bin And it runs well enough for the other projects I've used it on. $ DrIFT -V Version DrIFT-2.2.3 Is the cabal distribution just missing extra scripts? There's a fine line between packaging in the distro sense, that cabal does (where only metadata is added), and an actual fork. In this case, it looks like only metadata was added, so it's no different to any number of distro packages. Are you interested in ensuring the cabal file accurately describes the package as you wish it to be installed? -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cabal
Am Sonntag, 30. November 2008 20:46 schrieb Don Stewart: andrewcoppin: Thomas Schilling wrote: Cabal-the-install-tool (package cabal-install) is actually a different program that sits on top of Cabal-the-library, and it is in fact what really provides the real advantages. Together with Hackage this is what provides the killer feature of cabal install foo, however it relies on the building features and meta-data of Cabal. As I understand it, that's also a seperate download. (Whereas the cabal library comes with GHC.) One day, if I feel hard-core enough, I might try this tool. (Assuming it works on Windows...) It sounds potentially useful. (Although most actual packages typically have one, maybe two dependencies that aren't already installed, if that.) *if* .. *might* .. *assuming* .. *potentially* .. *maybe* .. *if*.. You could have built it by now! Source: http://hackage.haskell.org/packages/archive/cabal-install/0.6.0/cabal-insta ll-0.6.0.tar.gz Dependencies that aren't in core: http://hackage.haskell.org/packages/archive/HTTP/3001.1.5/HTTP-3001.1.5.tar .gz http://hackage.haskell.org/packages/archive/zlib/0.5.0.0/zlib-0.5.0.0.tar.g z Note the last one assumes you have zlib the C library installed. This should be straight forward to obtain. Not even necessary, it comes with its own for windows: if !os(windows) -- Normally we use the the standard system zlib: extra-libraries: z else -- However for the benefit of users of Windows (which does not have zlib -- by default) we bundle a complete copy of the C sources of zlib-1.2.3 c-sources: cbits/adler32.c cbits/compress.c cbits/crc32.c cbits/deflate.c cbits/gzio.c cbits/infback.c cbits/inffast.c cbits/inflate.c cbits/inftrees.c cbits/trees.c cbits/uncompr.c cbits/zutil.c Enjoy. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cabal
daniel.is.fischer: Am Sonntag, 30. November 2008 20:46 schrieb Don Stewart: andrewcoppin: Thomas Schilling wrote: Cabal-the-install-tool (package cabal-install) is actually a different program that sits on top of Cabal-the-library, and it is in fact what really provides the real advantages. Together with Hackage this is what provides the killer feature of cabal install foo, however it relies on the building features and meta-data of Cabal. As I understand it, that's also a seperate download. (Whereas the cabal library comes with GHC.) One day, if I feel hard-core enough, I might try this tool. (Assuming it works on Windows...) It sounds potentially useful. (Although most actual packages typically have one, maybe two dependencies that aren't already installed, if that.) *if* .. *might* .. *assuming* .. *potentially* .. *maybe* .. *if*.. You could have built it by now! Source: http://hackage.haskell.org/packages/archive/cabal-install/0.6.0/cabal-insta ll-0.6.0.tar.gz Dependencies that aren't in core: http://hackage.haskell.org/packages/archive/HTTP/3001.1.5/HTTP-3001.1.5.tar .gz http://hackage.haskell.org/packages/archive/zlib/0.5.0.0/zlib-0.5.0.0.tar.g z Note the last one assumes you have zlib the C library installed. This should be straight forward to obtain. Not even necessary, it comes with its own for windows: if !os(windows) -- Normally we use the the standard system zlib: extra-libraries: z else -- However for the benefit of users of Windows (which does not have zlib -- by default) we bundle a complete copy of the C sources of zlib-1.2.3 c-sources: cbits/adler32.c cbits/compress.c cbits/crc32.c cbits/deflate.c cbits/gzio.c cbits/infback.c cbits/inffast.c cbits/inflate.c cbits/inftrees.c cbits/trees.c cbits/uncompr.c cbits/zutil.c Even easier. Now there's no excuse for the ifs and buts and maybes. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cabal
On Sun, 30 Nov 2008, Don Stewart wrote: *if* .. *might* .. *assuming* .. *potentially* .. *maybe* .. *if*.. You could have built it by now! Source: http://hackage.haskell.org/packages/archive/cabal-install/0.6.0/cabal-install-0.6.0.tar.gz Dependencies that aren't in core: http://hackage.haskell.org/packages/archive/HTTP/3001.1.5/HTTP-3001.1.5.tar.gz http://hackage.haskell.org/packages/archive/zlib/0.5.0.0/zlib-0.5.0.0.tar.gz Note the last one assumes you have zlib the C library installed. This should be straight forward to obtain. I have extended this description and put it to http://haskell.org/haskellwiki/Cabal-Install Maybe you like to add a pointer in cabal-install.cabal/Homepage field to this page. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cabal
On Sun, 30 Nov 2008, Don Stewart wrote: lemming: Maybe you like to add a pointer in cabal-install.cabal/Homepage field to this page. Good idea. Duncan? After I finished that article, I also found: http://hackage.haskell.org/trac/hackage/wiki/CabalInstall ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Permutations
Jake Mcarthur wrote: Heh, after a couple more seconds of thought, reversing the two composed functions fixes it: nub . permutations Of course, neither my previous nonsolution nor this solution are efficient for long lists, but I think it serves as a decent reference implementation at least. Consider the following list: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2] Somebody just pointed out to me that this list has 87,178,291,200 permutations, of which 14 are unique. O_O ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] getRandom in HAppS-State (Was: ANNOUNCE: gitit 0.2 release)
[Re-sending to the list, sorry for the doubled mail, John] Hi John, Am Samstag, den 08.11.2008, 12:32 -0800 schrieb John MacFarlane: I've uploaded an early version of gitit, a Haskell wiki program, to HackageDB. Gitit uses HAppS as a webserver, git for file storage, pandoc for rendering the (markdown) pages, and highlighting-kate for highlighted source code. looking through your code, I see this: newSession :: (MonadState AppState (Ev (t GHC.Conc.STM)), MonadTrans t, Monad (t GHC.Conc.STM)) = SessionData - Ev (t GHC.Conc.STM) SessionKey newSession u = do key - getRandom setSession key u return key for a project of mine, I had so solve a similar problem, and first I used this way, but I’m wondering: The event is serialized without the random seed (I think), so when your app crashes and the event log is re-done, you might get a different key? Or does is getRandom function somehow deterministical? My solution was to pass a RNG into my function: addNewIssue :: MonadState State m = StdGen - m Issue and then use gen - liftIO $ newStdGen i - update $ AddNewIssue gen But maybe I’m worring too much... what do you think? Greetings, Joachim -- Joachim nomeata Breitner mail: [EMAIL PROTECTED] | ICQ# 74513189 | GPG-Key: 4743206C JID: [EMAIL PROTECTED] | http://www.joachim-breitner.de/ Debian Developer: [EMAIL PROTECTED] signature.asc Description: Dies ist ein digital signierter Nachrichtenteil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell, successing crossplatform API standart
s.clover: Haxr provides a basic implementation of the XML-RPC protocol, and while it looks like it doesn' t build on 6.10 at the moment, getting it to build shouldn't be a problem, and although it doesn't appear to be under active development, it does seem to be getting maintenance uploads. [1] These days, however, web services seem to be moving towards a RESTful model with a JSON layer and there are plenty of JSON libraries on hackage, which you could just throw over the fastCGI bindings. Alternately you could try JSON over one of the really lightweight haskell web servers, such as shed [2] or lucu [3]. If you go the latter route, I'd love to hear how it went. [1] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/haxr [2] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/httpd- shed [3] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Lucu Yes, I'd love to see some experience reports about the light web servers. And anyone who's tried the Amazon or CouchDB or other non-traditional storage bindings, http://hackage.haskell.org/cgi-bin/hackage-scripts/package/CouchDB http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hS3 Also, HAppS is making a serious push these days, in particular, via gitit, http://lhc.seize.it/ (the lhc homepage is gitit running in happs) And HAppS has become far more available since stabilising. Maybe it is time for a Haskell for the Web collection. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: ANN: Real World Haskell, now shipping
Ahn, Ki Yung wrote: Andrew Coppin 쓴 글: Then again, one day I sat down and tried to draw a diagram of the essential concepts, techniques and syntax of Haskell and how they're related... The result looked like alphabet soup! It's not clear how you start to explain anything without immediately needing to explain 20 other things you just used to explain the first thing. (Somebody commented recursive tutorials for a recursive language. It was meant as an insult, but I actually kinda like it...) Given that that's the case, I'm not really sure that I could do any better than the Three Kings, so maybe I should just shuffle off and keep my comments to myself. :-/ If one needs introductory Haskell programming tutorial explaining about the language concepts from first principles, then one should read a textbook written for that purpose such as Programming in Haskell. Real World Haskell is a collection of practical tips and know-hows to get things done at work rather than a step-by-step Haskell tutorial. And I believe that many other O'Reilly books are like that. Quoting the introduction: What will you need to know before reading this book? We expect that you already know how to program, but if you've never used a functional language, that's fine. Seems like it's intended to be useful to people who don't know any Haskell at all. And indeed, the subject matter of the opening chapters strongly reinforces this impression. Certainly this doesn't look like a book aimed at Haskell experts who are just looking for tips on how to solve real world problems. (Although no doubt the authors intended it for their benefit as well.) Unfortunately, the organisation isn't the clearest. But then, given that I've yet to come up with anything better myself, we should probably leave it at that... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
Larry Evans wrote: The haskell code: cross::[[a]]-[[a]] calculate a cross product of values. Now if you allow the elements of that function's argument list to be possibly infinite lists and you still want to eventually yield every possible cross product, you get a very nice problem... Martijn. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
On Sun, Nov 30, 2008 at 2:07 PM, Martijn van Steenbergen [EMAIL PROTECTED] wrote: Larry Evans wrote: The haskell code: cross::[[a]]-[[a]] calculate a cross product of values. Now if you allow the elements of that function's argument list to be possibly infinite lists and you still want to eventually yield every possible cross product, you get a very nice problem... Solved by control-monad-omega (not really a monad). The other nice one problem is allowing the argument itself to be infinite (you have to require all of the lists to be nonempty). Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: ANN: Real World Haskell, now shipping
andrewcoppin: Ahn, Ki Yung wrote: Andrew Coppin 쓴 글: Then again, one day I sat down and tried to draw a diagram of the essential concepts, techniques and syntax of Haskell and how they're related... The result looked like alphabet soup! It's not clear how you start to explain anything without immediately needing to explain 20 other things you just used to explain the first thing. (Somebody commented recursive tutorials for a recursive language. It was meant as an insult, but I actually kinda like it...) Given that that's the case, I'm not really sure that I could do any better than the Three Kings, so maybe I should just shuffle off and keep my comments to myself. :-/ If one needs introductory Haskell programming tutorial explaining about the language concepts from first principles, then one should read a textbook written for that purpose such as Programming in Haskell. Real World Haskell is a collection of practical tips and know-hows to get things done at work rather than a step-by-step Haskell tutorial. And I believe that many other O'Reilly books are like that. Quoting the introduction: What will you need to know before reading this book? We expect that you already know how to program, but if you've never used a functional language, that's fine. Seems like it's intended to be useful to people who don't know any Haskell at all. And indeed, the subject matter of the opening chapters strongly reinforces this impression. Certainly this doesn't look like a book aimed at Haskell experts who are just looking for tips on how to solve real world problems. (Although no doubt the authors intended it for their benefit as well.) Indeed, we assume you know how to program, or you're one of the many Haskellers looking for that final 15%. Unfortunately, the organisation isn't the clearest. But then, given that I've yet to come up with anything better myself, we should probably leave it at that... I gather you've only briefly looked at the online draft? The structure is based on the plan we stated 12 months ago, http://www.realworldhaskell.org/blog/2007/05/23/real-world-haskell-its-time/ Namely, cover the major techniques used to write serious, real-world Haskell code, so that programmers can just get to work in the language. Each major domain has a chapter or two, and we build upon earlier chapters in later ones. The book is explicitly fast-paced, so perhaps that's what you're noticing. We explicitly weren't going to leave the getting things done' part to page 711. And the response has been ridiculously positive, see, e.g. the Amazon reviews, The text is incredibly readable and straightforward. It's set up for those who already know how to program imperatively (e.g. C++/Java/C, etc), and takes those readers deep into Haskell functional programming. http://www.amazon.com/review/product/0596514980/ref=dp_db_cm_cr_acr_txt?_encoding=UTF8showViewpoints=1 If the coverage is too varied or too fast for your taste, perhaps one of the slower-paced intros such as Graham's recent book, Programming in Haskell would be more appropriate. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
You can have seq and lifted tuples, but the implementation of seq requires parallel evaluation. -- Lennart On Sun, Nov 30, 2008 at 7:00 PM, Luke Palmer [EMAIL PROTECTED] wrote: On Sun, Nov 30, 2008 at 10:43 AM, Max Rabkin [EMAIL PROTECTED] wrote: On Sun, Nov 30, 2008 at 9:30 AM, Luke Palmer [EMAIL PROTECTED] wrote: cross :: [a] - [b] - [(a,b)] It's just kind of a pain (you build [(a,(b,(c,d)))] and then flatten out the tuples). The applicative notation is a neat little trick which does this work for you. It seems to me like this would all be easy if (a,b,c,d) was sugar for (a,(b,(c,d))), and I can't see a disadvantage to that. This is a tricky and subtle question, actually. It has to do with the lifting of tuples; those two types have different domains. For example, the element in the latter: (1,(2,_|_)) Has no corresponding element in the former (there is (1,2,_|_,_|_), but that corresponds to (1,(2,(_|_,_|_))) ). Now, if tuples in Haskell were unlifted, meaning (_|_,_|_) = _|_, then there would be no issue. But that has far-reaching consequences in the language design, among which the seq function would have to be eliminated (many people would not be opposed to this). Also usage of unlifted tuples can cause subtle space leaks. Now, what all this domain theory has to do with practical issues, I'm not sure. But you can't just do a slick replacement, because it changes properties of programs that did not know the difference. Frankly, I would prefer what you propose as well (actually, I would prefer it to mean (a,(b,(c,(d,(), but it's the same idea). But the change is difficult and requires thought. Luke ___ 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
[Haskell-cafe] The Knight's Tour: solutions please
Lee Pike forwarded the following: Solving the Knight's Tour Puzzle In 60 Lines of Python http://developers.slashdot.org/article.pl?sid=08/11/30/1722203 Seems that perhaps (someone expert in) Haskell could do even better? Maybe even parallelize the problem? :) So, team, anyone want to implement a Knight's Tour solver in a list monad/list comprehension one liner? These little puzzles are made for fast languages with backtracking monads Post solutions to the wiki.. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Instances that shouldn't overlap
Ryan Ingram wrote: A common mistake (and a confusing bit about typeclasses) is that whether or not the constraints on an instance apply are irrelevant. Specifically, the code instance (Applicative f, Eq a) = AppEq f a means that, given any types f and a, I can tell you how to make them an instance of AppEq. But I also ask you to please add the constraints Applicative f and Eq a. That is to say, only the stuff on the right of the = apply when determining whether an instance applies. Or perhaps a simpler way of explaining it is that (metasyntactically) for the class: class CLASS a1 ... an where f1 :: t1 ... fn :: tn the instance declaration: instance CONTEXT a1 ... an = CLASS a1 ... an where f1 :: t1 ... fn :: tn means *exactly*: instance CLASS a1 ... an where f1 :: CONTEXT a1 ... an = t1 ... fn :: CONTEXT a1 ... an = tn The ability to add contexts to a typeclass instance is not syntactic sugar per se ---because the latter declaration would be an invalid instance of the class (allowing the syntax might permit instances where contexts are inconsistent across f1...fn)--- but it's still just a sugary way of simplifying the declaration. While the latter declaration is unbearably syntactically salted, it's straightforward for explaining this common mistake. There've been a number of proposals for different syntax to make the current arrangement less confusing to newcomers, none of which has gained widespread currency. In the fine Haskell tradition of leaving things odd until a proper solution is found, I think the correct approach is to redesign the meaning of the original declaration such that it *does* propagate the constraints at instance-selection time, rather than trying to find a nicer coat of paint for the old bikeshed. The OverlappingInstances and IncoherentInstances flags are varnish to make the current arrangement tenable, but they cover up a whole area that is ripe for research. The new type families work covers a nearby domain, but I think active context propagation deals with a different set of concerns. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] manipulating predicate formulae
Hi Ganesh, Are there any Haskell libraries around for manipulating predicate formulae? I had a look on hackage but couldn't spot anything. http://www.cs.york.ac.uk/fp/darcs/proposition/ Unreleased, but might be of interest. It simplifies propositional formulae, and can do so using algebraic laws, custom simplifications or BDDs. I don't really use this library, so if it is of interest to you, its all yours :-) Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
Luke Palmer wrote: The other nice one problem is allowing the argument itself to be infinite (you have to require all of the lists to be nonempty). I think the requirement has to be a lot stronger for that to work. If every sublist has two elements, the answer is 2^infinity lists which is uncountable. In order for the answer to be countable, you have to require that only a finite number of sublists contain more than one element, at which point you can use your omega monad again. Martijn. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cabal
On Sun, 2008-11-30 at 21:14 +0100, Henning Thielemann wrote: On Sun, 30 Nov 2008, Don Stewart wrote: lemming: Maybe you like to add a pointer in cabal-install.cabal/Homepage field to this page. Good idea. Duncan? After I finished that article, I also found: http://hackage.haskell.org/trac/hackage/wiki/CabalInstall I'm trying to work out what the best thing is to do with the Cabal documentation. Currently it's kind of patchy and spread over about three sites. There's the http://haskell.org/cabal website, the dev wiki and trac and the pages on the main Haskell.org wiki. I think ideally we'd have all the user documentation on the cabal website, including the docs for cabal-install. Unless people think that's a silly idea and we should just put everything on the haskellwiki system. Suggestions? Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cabal (was: Compilers)
On Sat, 2008-11-29 at 17:49 -0800, John Meacham wrote: On Sun, Nov 30, 2008 at 01:37:20AM +, Thomas Schilling wrote: So that's over 2 SLOC, but, of course, for a more powerful tool. So I presume the 4x more code remark by John was about the Makefile rules to implement something similar to the Simple build system part.) No, I was refering to 'mk'. which you can download a unix port of here: http://cminusminus.org/code.html I chose it since there are a variety of make implementations out there, and GNU make attempts to be compatible with all of them and then some. 'mk' contains a superset of the functionality (with a slightly cleaned up syntax) of what we all generally think of as portable 'make'. There's hardly any code in Cabal that corresponds to mk/make, since we call out to ghc --make. Most of the code in Cabal is for lots of other features. Of course if Cabal's Simple build system did contain more code for a dependency framework like mk or make then it'd be a lot more capable. However building a decent one is easier said than done. We don't just want to re-create make, we want something better. Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cabal
On Sun, 2008-11-30 at 10:57 +, Andrew Coppin wrote: As I understand it, that's also a seperate download. (Whereas the cabal library comes with GHC.) One day, if I feel hard-core enough, I might try this tool. (Assuming it works on Windows...) It sounds potentially useful. It will of course be bundled with the first release of the Haskell Platform. In the mean time you can get a pre-compiled binary here: http://haskell.org/~duncan/cabal/cabal.exe (Although most actual packages typically have one, maybe two dependencies that aren't already installed, if that.) My favourite example at the moment is the new hackage server which has 24 dependencies and installs nicely using cabal install. Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cabal
duncan.coutts: On Sun, 2008-11-30 at 10:57 +, Andrew Coppin wrote: As I understand it, that's also a seperate download. (Whereas the cabal library comes with GHC.) One day, if I feel hard-core enough, I might try this tool. (Assuming it works on Windows...) It sounds potentially useful. It will of course be bundled with the first release of the Haskell Platform. In the mean time you can get a pre-compiled binary here: http://haskell.org/~duncan/cabal/cabal.exe (Although most actual packages typically have one, maybe two dependencies that aren't already installed, if that.) My favourite example at the moment is the new hackage server which has 24 dependencies and installs nicely using cabal install. I'm a fan of gitit, and its 46 dependencies, that install via cabal-install. Pretty awesome. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
On Sun, Nov 30, 2008 at 3:13 PM, Martijn van Steenbergen [EMAIL PROTECTED] wrote: Luke Palmer wrote: The other nice one problem is allowing the argument itself to be infinite (you have to require all of the lists to be nonempty). I think the requirement has to be a lot stronger for that to work. If every sublist has two elements, the answer is 2^infinity lists which is uncountable. Good catch. If there are infinitely many finite lists, you can construct a searchable set of results: import Data.Searchable -- from infinite-search finiteList :: [a] - Set a finiteList = foldr1 union . map singleton cross :: Eq a = [[a]] - Set a cross = sequence . map finiteList ghci let cantor = cross (repeat [True,False]) ghci fmap (take 10) $ search cantor $ \xs - not (any (xs !!) [3..6]) Just [True,True,True,False,False,False,False,True,True,True] Which is pretty much unrelated to what we were talking about. But it's cool to show of Martin Escardo's neat stuff. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Compilers
On Sun, Nov 30, 2008 at 08:50:51AM -0800, John Meacham wrote: And creating a crippled version of something you wrote and passing it off as the original, in a way that clearly breaks things for other people definitely is something to get upset about. There was a discussion of this issue on the libraries list in June/July, resulting in an agreed policy being added to the hackage upload page, including: If a package is being maintained, any release not approved and supported by the maintainer should use a different package name. I am also willing to remove any release with an unchanged name and made without the support of the maintainer. You have made clear that the DrIFT-2.2.3 upload is in that category, so I have now removed it. Looking through, the only other package I spotted that might be such is HsASA-0.1 -- please let me know about this one, and any others I've missed. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The Knight's Tour: solutions please
G'day all.
Quoting Don Stewart [EMAIL PROTECTED]:
So, team, anyone want to implement a Knight's Tour solver in a list
monad/list comprehension one liner? These little puzzles are made for
fast languages with backtracking monads
I conjecture that any one-liner won't be efficient.
Anyway, here's my ~30 min attempt. The showBoard and main are both very
quick and dirty, and I'm sure someone can do much better.
I particularly like the fact that changing Maybe to [] will make
knightsTour return all tours starting at the upper left-hand corner,
rather than just one. Warm fuzzy things rule.
Cheers,
Andrew Bromage
module Main where
import qualified Data.Set as S
import Data.List
import Data.Function
import Control.Arrow
import Control.Monad
import System
knightsTour :: Int - Maybe [(Int,Int)]
knightsTour size
= tour [(0,0)] (S.fromAscList [ (x,y) | x - [0..size-1], y -
[0..size-1],
x /= 0 || y /= 0 ])
where
jumps = [(2,1),(1,2),(2,-1),(-1,2),(-2,1),(1,-2),(-2,-1),(-1,-2)]
tour moves@(pos:_) blank
| S.null blank = return (reverse moves)
| otherwise = msum [ tour (npos:moves) (npos `S.delete` blank) |
npos - nextPositions pos ]
where
nextPositions = map snd . sortBy (compare `on` fst) .
map (length . neighbours id) .
neighbours
neighbours (x,y) = [ npos | (x',y') - jumps,
let { npos = (x+x',y+y') }, npos `S.member` blank ]
showBoard :: Int - [(Int,Int)] - ShowS
showBoard size
= inter bdr .
map (inter ('|':) . map (shows . fst)) .
groupBy ((==) `on` fst.snd) .
sortBy (compare `on` snd) .
zip [1..]
where
bdr = ('\n':) . inter ('+':) (replicate size (replicate width '-' ++))
. ('\n':)
width = length . show $ size*size
pad s = \r - replicate (width - length (s )) ' ' ++ s r
inter sep xs = sep . foldr (.) id [ pad x . sep | x - xs ]
main :: IO ()
main = do
a - getArgs
size - case a of
[] - return 8
(s:_) - return (read s)
putStrLn $ case knightsTour size of
Nothing - No solution found.
Just b - showBoard size b
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The Knight's Tour: solutions please
ajb:
G'day all.
Quoting Don Stewart [EMAIL PROTECTED]:
So, team, anyone want to implement a Knight's Tour solver in a list
monad/list comprehension one liner? These little puzzles are made for
fast languages with backtracking monads
I conjecture that any one-liner won't be efficient.
Anyway, here's my ~30 min attempt. The showBoard and main are both very
quick and dirty, and I'm sure someone can do much better.
I particularly like the fact that changing Maybe to [] will make
knightsTour return all tours starting at the upper left-hand corner,
rather than just one. Warm fuzzy things rule.
Cheers,
Andrew Bromage
module Main where
import qualified Data.Set as S
import Data.List
import Data.Function
import Control.Arrow
import Control.Monad
import System
knightsTour :: Int - Maybe [(Int,Int)]
knightsTour size
= tour [(0,0)] (S.fromAscList [ (x,y) | x - [0..size-1], y -
[0..size-1],
x /= 0 || y /= 0 ])
where
jumps = [(2,1),(1,2),(2,-1),(-1,2),(-2,1),(1,-2),(-2,-1),(-1,-2)]
tour moves@(pos:_) blank
| S.null blank = return (reverse moves)
| otherwise = msum [ tour (npos:moves) (npos `S.delete` blank) |
npos - nextPositions pos ]
where
nextPositions = map snd . sortBy (compare `on` fst) .
map (length . neighbours id) .
neighbours
neighbours (x,y) = [ npos | (x',y') - jumps,
let { npos = (x+x',y+y') }, npos `S.member` blank ]
showBoard :: Int - [(Int,Int)] - ShowS
showBoard size
= inter bdr .
map (inter ('|':) . map (shows . fst)) .
groupBy ((==) `on` fst.snd) .
sortBy (compare `on` snd) .
zip [1..]
where
bdr = ('\n':) . inter ('+':) (replicate size (replicate width '-'
++))
. ('\n':)
width = length . show $ size*size
pad s = \r - replicate (width - length (s )) ' ' ++ s r
inter sep xs = sep . foldr (.) id [ pad x . sep | x - xs ]
main :: IO ()
main = do
a - getArgs
size - case a of
[] - return 8
(s:_) - return (read s)
putStrLn $ case knightsTour size of
Nothing - No solution found.
Just b - showBoard size b
dolio implemented a cute one based on continuations, that's also about
10x faster than the python version,
http://hpaste.org/12546#a2
-- Don
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell Weekly News: Issue 95 - November 30, 2008
--- Haskell Weekly News http://sequence.complete.org/hwn/20081130 Issue 95 - November 30, 2008 --- Welcome to issue 95 of HWN, a newsletter covering developments in the [1]Haskell community. Real World Haskell is [2]finally here! [3]Read it online, and/or [4]get your own dead tree copy. Better yet, get two copies, one for yourself and one for a friend. The fifteenth [5]Haskell Communities and Activities Report is also here---check out all the exciting stuff being worked on in the Haskell world! Announcements HCAR. Janis Voigtlaender [6]announced the 15th edition of the [7]Haskell Communities and Activities Report (HCAR) is now available! Not quite another Haskell tutorial, but Janis Voigtlaender [8]announced that he submitted his [9]Habilitation thesis last week. The first few chapters of it try to give an introduction to Haskell with emphasis on types and reasoning principles. hledger 0.2. Simon Michael [10]announced version 0.2 of [http://joyful.com/hledger hledger, a minimal haskell clone of John Wiegley's [11]ledger text-based accounting tool. darcs zlib error workaround. Eric Kow [12]outlined workarounds and future plans for a darcs bug relating to broken CRCs in gzipped patch files. You should read this if you have installed darcs 2.1.2 via the Cabal build method. Turbinado 0.2. Alson Kemp [13]announced version 0.2 of [14]Turbinado, an easy-to-use, fast web application framework. Fun with type functions. Simon Peyton-Jones [15]requests examples of compelling use cases for type functions: can you tell us about the most persuasive, fun application you've encountered, for type families or functional dependencies? Simple is good. It doesn't have to be elaborate: just something that does something useful you could not have done otherwise. Jobs PhD Positions in Language-based Security at Chalmers. Andrei Sabelfeld [16]announced the availability of [17]PhD student positions in programming language-based security in the Department of Computer Science and Engineering at Chalmers University of Technology, Sweden. The application deadline is January 30, 2009. FP Jobs. Julien Sylvestre [18]announced several new permanent positions, based in Paris, with MLstate -- an IT company whose functional programming approach to SaaS and cloud computing has been recently recognized by the French Ministry of Research Innovation Award. Blog noise [19]Haskell news from the [20]blogosphere. * Dan Piponi (sigfpe): [21]An Approach to Algorithm Parallelisation. Dan illustrates a clever, general framework for parallelizing some not-so-obviously-parallelizable algorithms, based on linear operations over rings. * Real-World Haskell: [22]First European Orders Now Landing. * Braden Shepherdson: [23]Pimp Your XMonad #3: Prompt. Braden continues his series on getting the most out of your xmonad configuration with a post describing the Prompt family of extensions. * Real-World Haskell: [24]Amazon orders now arriving. * Real-World Haskell: [25]Orders Now Arriving on the US West Coast. * Luke Palmer: [26]Relative time FRP. A new, more elegant semantics for FRP -- relative time instead of absolute time? * JP Moresmau: [27]Predictable random for testing. * Osfameron: [28]London Perl Workshop tomorrow!. * Phil Ratzsch: [29]Initial Haskell Impressions. * Chung-chieh Shan: [30]Metalinguistics. * Alex McLean: [31]Babble. A simple vocable synthesiser that runs in a web browser, written in HaXe. * Jonathan Tang: [32]Sum types vs. typeclasses. * Magnus Therning: [33]Re: Redesigning GHC's build system. Magnus's response to a recent post about redoing GHC's build system. * Real-World Haskell: [34]Real World Haskell is shipping!. * Twan van Laarhoven: [35]Knight in n, part 1: moves. Twan explores knight-move problems in Haskell. * Conal Elliott: [36]Semantic editor combinators. An elegant explanation of semantic editor combinators -- a principled framework for building up ways to edit components of structured values. * David Sankel: [37]Why is the Reactive Behavior tutorial taking so long? splitB. * Chung-chieh Shan: [38]Bowling balls. A nice solution to the bowling-ball problem in Haskell. * Cory: [39]Developing in impractical languages. * Chris Double: [40]Dynamic Compilation and Loading of Modules in Haskell. A mini-tutorial on using the GHC API. * Ashish Hanwadikar: [41]More on Haskell DSL. A Haskell DSL for replacing 'make'. * Luke Palmer: [42]Screw laziness (w.r.t. Fran semantics). Quotes of the Week * quicksilver: I ACCIDENTALLY
Re: [Haskell-cafe] Compilers
On Mon, Dec 01, 2008 at 01:02:40AM +, Ross Paterson wrote: I am also willing to remove any release with an unchanged name and made without the support of the maintainer. You have made clear that the DrIFT-2.2.3 upload is in that category, so I have now removed it. Looking through, the only other package I spotted that might be such is HsASA-0.1 -- please let me know about this one, and any others I've missed. No, that one is fine. I don't have any issues with my haskell _libraries_ being packaged up if done properly. Cabal has signifigantly more utility for libraries than programs so the scales tip in its direction more often then. Speaking of which, it would be nice if they were seperated into two different sections on hackage. A few projects that have both library and programs would be listed in both categories. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The Knight's Tour: solutions please
Here's a clean-up of my code (it even fits within the line-length limit of my mail client :)). Note that it's pretty much exactly the Python algorithm. When the Python program finds a solution, it prints the board and exits. Since that's evil IO type stuff, we noble functional folk instead set up an exit continuation using callCC, and call it when we find a solution. :) I haven't bothered testing it against the Python version, but the backtracking solution I wrote with the Logic monad (and Data.Map) took around 50% more time than this. -- Dan snip module Main where import Control.Monad.Cont import Control.Monad.ST import Data.Array.ST import Data.List import Data.Ord import Data.Ix import System.Environment type Square = (Int, Int) type Board s = STUArray s (Int,Int) Int type ChessM r s = ContT r (ST s) type ChessK r s = String - ChessM r s () successors :: Int - Board s - Square - ChessM r s [Square] successors n b = sortWith (fmap length . succs) = succs where sortWith f l = map fst `fmap` sortBy (comparing snd) `fmap` mapM (\x - (,) x `fmap` f x) l succs (i,j) = filterM (empty b) [ (i', j') | (dx,dy) - [(1,2),(2,1)] , i' - [i+dx,i-dx] , j' - [j+dy, j-dy] , inRange ((1,1),(n,n)) (i',j') ] empty :: Board s - Square - ChessM r s Bool empty b s = fmap (1) . lift $ readArray b s mark :: Square - Int - Board s - ChessM r s () mark s k b = lift $ writeArray b s k tour :: Int - Int - ChessK r s - Square - Board s - ChessM r s () tour n k exit s b | k n*n = showBoard n b = exit | otherwise = successors n b s = mapM_ (\x - do mark x k b tour n (k+1) exit x b -- failed, rollback mark x 0 b) showBoard :: Int - Board s - ChessM r s String showBoard n b = fmap unlines . forM [1..n] $ \i - fmap unwords . forM [1..n] $ \j - pad `fmap` lift (readArray b (i,j)) where k = floor . log . fromIntegral $ n*n pad i = let s = show i in replicate (k-length s) ' ' ++ s main = do (n:_) - map read `fmap` getArgs s - stToIO . flip runContT return $ (do b - lift $ newArray ((1,1),(n,n)) 0 mark (1,1) 1 b callCC $ \k - tour n 2 k (1,1) b fail No solution!) putStrLn s ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The Knight's Tour: solutions please
dan.doel: Here's a clean-up of my code (it even fits within the line-length limit of my mail client :)). Note that it's pretty much exactly the Python algorithm. When the Python program finds a solution, it prints the board and exits. Since that's evil IO type stuff, we noble functional folk instead set up an exit continuation using callCC, and call it when we find a solution. :) I haven't bothered testing it against the Python version, but the backtracking solution I wrote with the Logic monad (and Data.Map) took around 50% more time than this. I've created a wiki page, http://haskell.org/haskellwiki/The_Knights_Tour I note the LogicT version is the shortest so far. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] The Knight's Tour: solutions please
It seems the following pure functional (except for the final printout) version of the search has almost the same performance as the Dan Doel's latest version with the unboxed arrays and callCC. For the board of size 40, Dan Doel's version takes 0.047s on my computer; the version below takes 0.048s. For smaller boards, the difference is imperceptible. Interestingly, the file sizes of the compiled executables (ghc -O2, ghc 6.8.2) are similar too: 606093 bytes for Dan Doel's version, and 605938 bytes for the version below. The version below is essentially Dan Doel's earlier version. Since the problem involves only pure search (rather than committed choice), I took the liberty of substituting FBackTrack (efficient MonadPlus) for LogicT. FBackTrack can too be made the instance of LogicT; there has not been any demand for that though. import Data.List import Data.Ord import qualified Data.IntMap as Map import System.Environment import FBackTrack import Control.Monad -- Emulate the 2-dimensional map as a nested 1-dimensional map initmap n = Map.fromList $ (1,Map.singleton 1 1):[ (k,Map.empty) | k - [2..n] ] notMember (i,j) m = Map.notMember j $ Map.findWithDefault undefined i m insrt (i,j) v m = Map.update (Just . Map.insert j v) i m lkup (i,j) m = Map.findWithDefault undefined j $ Map.findWithDefault undefined i m successors n b = sortWith (length . succs) . succs where sortWith f = map fst . sortBy (comparing snd) . map (\x - (x, f x)) succs (i,j) = [ (i', j') | (dx,dy) - [(1,2),(2,1)] , i' - [i+dx,i-dx] , j' - [j+dy, j-dy] , i' = 1, j' = 1, i' = n, j' = n , notMember (i',j') b ] tour n k s b | k n*n = return b | otherwise = do next - foldl1 mplus.map return $ successors n b s tour n (k+1) next $ insrt next k b showBoard n b = unlines . map (\i - unwords . map (\j - pad $ lkup (i,j) b) $ [1..n]) $ [1..n] where k = length . show $ n*n + 1 pad i = let s = show i in replicate (k-length s) ' ' ++ s main = do (n:_) - map read `fmap` getArgs let (b:_) = runM Nothing . tour n 2 (1,1) $ initmap n putStrLn $ showBoard n b ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Combining licences
Hello, I know very little about licensing, so I'm hoping to get some advice from you guys. In the next release of Wired, I plan to include an open-source standard cell library (or rather data derived from it). This cell library has a custom license (found at the bottom of http://www.nangate.com/openlibrary). It appears to be very permissive, but it states that the license text must be included in all copies of the Library, in whole or in part, and all derivative works of the Library. Wired itself is BSD3-licensed. How do I arrange this in the package? Can I still have a BSD3 license for Wired? Where do I put the respective license texts? Any other things I should have in mind? Or perhaps it's better to put the cell library in its own package? I'm a bit reluctant to do this, because it means that Wired will be essentially useless on its own. Thanks, / Emil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
