Re: [Haskell-cafe] ordNub
Apologies. I was being lazy. Here's a stable version: import qualified Data.HashSet as S hashNub :: (Ord a) => [a] -> [a] hashNub l = go S.empty l where go _ [] = [] go s (x:xs) = if x `S.member` s then go s xs else x : go (S.insert x s) xs Which, again, will probably be faster than the one using Ord, and I can't think of any cases where I'd want the one using Ord instead. I may just not be creative enough, though. - Clark On Mon, Jul 15, 2013 at 12:46 AM, Brandon Allbery wrote: > On Sun, Jul 14, 2013 at 7:54 AM, Clark Gaebel wrote: >> >> Oops sorry I guess my point wasn't clear. >> >> Why ord based when hashable is faster? Then there's no reason this has to >> be in base, it can just be a > > Did the point about "stable" fly overhead? > > -- > brandon s allbery kf8nh sine nomine associates > allber...@gmail.com ballb...@sinenomine.net > unix, openafs, kerberos, infrastructure, xmonadhttp://sinenomine.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] What have happened to haskell.org?
On URL http://haskell.org/ I get starting Apache page and 404 on http://haskell.org/hoogle/ URL with starting www - http://www.haskell.org/ seems to be working but http://www.haskell.org/hoogle/ responds with some ELF file. Kind regards, Kirill Zaborsky ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Compiling haskell-platform-2013.2.0.0 fails
Hello, I'm attempting to compile haskell-platform on an Arch Linux system. It fails very soon after invoking 'make': Configuring HUnit-1.2.5.2... Setup: Use of GHC's environment variable GHC_PACKAGE_PATH is incompatible with Cabal. Use the flag --package-db to specify a package database (it can be used multiple times). If it makes a difference, I'm using GHC 7.6.3 from the Arch package repo. The envar GHC_PACKAGE_PATH mentioned in the error message is unset. Thanks for any help, Roger This electronic communication is governed by the terms and conditions at http://www.mun.ca/cc/policies/electronic_communications_disclaimer_2012.php ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What have happened to haskell.org?
On Mon, Jul 15, 2013 at 07:19:12AM -0700, Kirill Zaborsky wrote: > http://www.haskell.org/hoogle/ responds with some ELF file. After running "strings" on it, it does seem to be (at least part of) the hoogle binary. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Hoogle website not working?
Hi cafe, I'm seeing a binary executable file every time I try to access haskell.org/hoogle. I don't know if the maintainers are aware of this. Cheers. Ivan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] OpenGL extensions survey results
Hi, here are the results of the recent OpenGL extensions survey: https://github.com/bsl/opengl-extensions-survey If I did anything dumb, please send me mail or a pull request. Thanks to everyone who contributed! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Hoogle problems?
I've just tried using Hoogle, but either get a 404 not found (http://haskell.org/hoogle/) or else I find I get a ELF 64-bit LSB executable being downloaded If I search using Google and click on the first link (shown as www.haskell.org/hoogle/ I get the following (spaces deliberately added to make it less dangerous) https://www.goo gle.com/url?sa=t&rct=j&q=&esrc=s&sou rce=web&cd=1&cad=rja&ved=0CC8QFjAA&url=http%3A%2F%2Fwww.haskell.org%2Fhoogle%2F&ei=y_njUdZAhY 7sBsGpgNAK&usg=AFQjCNFljq5Oyb4LT7VF-I5MUotq512AQg&sig2 =SVRE_6nF3bhho7-NKqEaCw&bvm=bv.487 05608,d.ZGU Using Mac OS X 10.6, Chrome and Safari Is it me, or is there a wider problem ? Andrew Butterfield Tel: +353-1-896-2517 Fax: +353-1-677-2204 Lero@TCD, Head of Foundations & Methods Research Group Director of Teaching and Learning - Undergraduate, School of Computer Science and Statistics, Room G.39, O'Reilly Institute, Trinity College, University of Dublin http://www.scss.tcd.ie/Andrew.Butterfield/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Database conectivity in Haskell. HDBC-3 or something.
Hello, haskellers. I has made some rework of HDBC, if you are interested follow the link http://s9gf4ult.github.io/hdbc/Database-HDBC.html So, why did I made this ? Because I did not found good enough (inside and outside) common interface for database connectivity. What I mean is flexible and simple interface, supporting arbitrary precision values and providing convenient and minimalistic interface for just query execution. In ''roadmap'' in the documentation you can see, that I think, that Haskell must have such interface which must become the conveient base for other high-level interfaces, such as Persistent and HaskellDB. Other languages, like Python goes this way, so why we must not ? I dont know will this patches accepted to main HDBC repository or not. I will fork HDBC under another name if necessary. The patches are: https://github.com/s9gf4ult/hdbc https://github.com/s9gf4ult/hdbc-postgresql There is just PostgreSQL driver for now, but I plan to write some other drivers as well. Any help and pull requests are welcome. My question is: what do you think about all of this? Do you think this is good idea or this is not necessary for now? I just want to notify the community about this and maybe find support. Discuss. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ordNub
Hey Jason, would you mind giving a short idea of what the point of Bird's implementation is / from what properties it is derived? Also, running the QuickCheck tests you added, it doesn't give the same output (order) as nub. On 15/07/13 13:26, Jason Dagit wrote: > Richard Bird has a book, "Pearls of Functional Algorithm Design" that > is meant to teach a form of deriving algorithms from the properties we > ask of them. In this book, he gives a possible derivation of ordNub, > simply called nub in the book, following the methodology he is > teaching. He notes in the text that this derivation feels more > complicated than it ought. > > Here is his version: http://lpaste.net/87625 > > I just sent you a pull request to add that one and S.toList . > S.fromList that was suggested in this thread. I don't think those two > implementations are faster than the others but it's nice to have them > for completeness. > > Jason > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Workshop on Termination (deadline: July 22)
Dear all. Still one week to go: submit your results and questions on all things related to termination and bounded resource consumption (of user programs, of type checkers, etc.) to the Workshop on Termination. We are specifically encouraging contributions from the Haskell (and Agda, and Idris) community. - Johannes. # 13th International Workshop on Termination (WST) ( full CfP see http://www.imn.htwk-leipzig.de/WST2013/ ) Centro Residenziale Universitario di Bertinoro (near Bologna, Italy). submission: July 22, 2013 notification: July 25, 2013 final version: August 10, 2013 workshop: August 29 - 31, 2013 The Workshop on Termination traditionally brings together, in an informal setting, researchers interested in all aspects of termination, whether this interest be practical or theoretical, primary or derived. The workshop also provides a ground for cross-fertilisation of ideas from term rewriting and from the different programming language communities. The friendly atmosphere enables fruitful exchanges leading to joint research and subsequent publications. signature.asc Description: OpenPGP digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ordNub
On Sun, Jul 14, 2013 at 7:54 AM, Clark Gaebel wrote: > Oops sorry I guess my point wasn't clear. > > Why ord based when hashable is faster? Then there's no reason this has to > be in base, it can just be a > Did the point about "stable" fly overhead? -- brandon s allbery kf8nh sine nomine associates allber...@gmail.com ballb...@sinenomine.net unix, openafs, kerberos, infrastructure, xmonadhttp://sinenomine.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hoogle problems?
Yes, I get the same error as you do. It was working the last time I looked at it, a couple of weeks ago. On Mon, Jul 15, 2013 at 2:35 PM, Andrew Butterfield < andrew.butterfi...@scss.tcd.ie> wrote: > I've just tried using Hoogle, but either get a 404 not found > (http://haskell.org/hoogle/) or else I find I get a ELF 64-bit > LSB executable being downloaded > > If I search using Google and click on the first link > (shown as www.haskell.org/hoogle/ > I get the following (spaces deliberately added to make it less dangerous) > https://www.goo > gle.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CC8QFjAA&url=http%3A%2F% > 2Fwww.haskell.org%2Fhoogle%2F&ei=y_njUdZAhY > 7sBsGpgNAK&usg=AFQjCNFljq5Oyb4LT7VF-I5MUotq512AQg&sig2 > =SVRE_6nF3bhho7-NKqEaCw&bvm=bv.487 05608,d.ZGU > > Using Mac OS X 10.6, Chrome and Safari > > Is it me, or is there a wider problem ? > > Andrew Butterfield Tel: +353-1-896-2517 Fax: +353-1-677-2204 > Lero@TCD, Head of Foundations & Methods Research Group > Director of Teaching and Learning - Undergraduate, > School of Computer Science and Statistics, > Room G.39, O'Reilly Institute, Trinity College, University of Dublin > http://www.scss.tcd.ie/Andrew.Butterfield/ > > > > ___ > 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] What have happened to haskell.org?
The web site is migrating. IRC says: Topic for #haskell: haskell.org in the middle of migration; expect turbulence; use www.haskell.org On Mon, Jul 15, 2013 at 6:19 PM, Kirill Zaborsky wrote: > On URL http://haskell.org/ I get starting Apache page and 404 on > http://haskell.org/hoogle/ > URL with starting www - http://www.haskell.org/ seems to be working but > http://www.haskell.org/hoogle/ responds with some ELF file. > > Kind regards, > Kirill Zaborsky > > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > -- Sincerely yours, -- Daniil -- Sincerely yours, -- Daniil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hoogle problems?
The web site is migrating. IRC says: Topic for #haskell: haskell.org in the middle of migration; expect turbulence; use www.haskell.org On Mon, Jul 15, 2013 at 5:35 PM, Andrew Butterfield wrote: > I've just tried using Hoogle, but either get a 404 not found > (http://haskell.org/hoogle/) or else I find I get a ELF 64-bit > LSB executable being downloaded > > If I search using Google and click on the first link > (shown as www.haskell.org/hoogle/ > I get the following (spaces deliberately added to make it less dangerous) > https://www.goo gle.com/url?sa=t&rct=j&q=&esrc=s&sou > rce=web&cd=1&cad=rja&ved=0CC8QFjAA&url=http%3A%2F%2Fwww.haskell.org%2Fhoogle%2F&ei=y_njUdZAhY > 7sBsGpgNAK&usg=AFQjCNFljq5Oyb4LT7VF-I5MUotq512AQg&sig2 > =SVRE_6nF3bhho7-NKqEaCw&bvm=bv.487 05608,d.ZGU > > Using Mac OS X 10.6, Chrome and Safari > > Is it me, or is there a wider problem ? > > Andrew Butterfield Tel: +353-1-896-2517 Fax: +353-1-677-2204 > Lero@TCD, Head of Foundations & Methods Research Group > Director of Teaching and Learning - Undergraduate, > School of Computer Science and Statistics, > Room G.39, O'Reilly Institute, Trinity College, University of Dublin > http://www.scss.tcd.ie/Andrew.Butterfield/ > > > > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe -- Sincerely yours, -- Daniil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ordNub
On Sun, Jul 14, 2013 at 4:20 AM, Niklas Hambüchen wrote: > tldr: nub is abnormally slow, we shouldn't use it, but we do. > > > As you might know, Data.List.nub is O(n²). (*) > > As you might not know, almost *all* practical Haskell projects use it, > and that in places where an Ord instance is given, e.g. happy, Xmonad, > ghc-mod, Agda, darcs, QuickCheck, yesod, shake, Cabal, haddock, and 600 > more (see https://github.com/nh2/haskell-ordnub). > > I've taken the Ord-based O(n * log n) implementation from yi using a Set: > > ordNub :: (Ord a) => [a] -> [a] > ordNub l = go empty l > where > go _ [] = [] > go s (x:xs) = if x `member` s then go s xs > else x : go (insert x s) xs > > > and put benchmarks on > http://htmlpreview.github.io/?https://github.com/nh2/haskell-ordnub/blob/1f0a2c94a/report.html > (compare `nub` vs `ordNub`). Richard Bird has a book, "Pearls of Functional Algorithm Design" that is meant to teach a form of deriving algorithms from the properties we ask of them. In this book, he gives a possible derivation of ordNub, simply called nub in the book, following the methodology he is teaching. He notes in the text that this derivation feels more complicated than it ought. Here is his version: http://lpaste.net/87625 I just sent you a pull request to add that one and S.toList . S.fromList that was suggested in this thread. I don't think those two implementations are faster than the others but it's nice to have them for completeness. Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hoogle problems?
OK, but why does it need to go down for migration? On Mon 15 Jul 2013 23:52:02 SGT, Daniel F wrote: > The web site is migrating. > IRC says: Topic for #haskell: haskell.org in the middle of migration; > expect turbulence; use www.haskell.org ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Non-recursive let [Was: GHC bug? Let with guards loops]
The IDE still works for Windows, but it isn't actively developed anymore (though bugs and minor annoyances are still being fixed). For Mac and Linux we now have a command line tool that uses the IDE's codebase. Personally, I just use vim (of course you can use any editor you prefer; vim comes with syntax colouring for Clean out of the box) for coding and then use a new CLI tool called CPM (Clean Project Manager) to build my project. This tool will be included by default with the next Clean release. I doubt the IDE will be resurrected on Mac and Linux, because it is just too much work to port Object IO (the GUI library) to those platforms and our own Mac/Linux users strongly prefer their own editors over the IDE anyway. For people that prefer a non-CLI workflow, we are actually looking into making a web-based IDE in iTasks (although it doesn't have a very high priority at the moment).The OS dependency for dynamics stems from the fact that the Clean dynamics are quite a bit more powerful than Haskell's. For example, using dynamics, it is possible to send arbitrary functions to another Clean application, which can then dynamically link these functions in at runtime and immediately execute them. It doesn't even need to be the same program, which Cloud Haskell does require (and theoretically, it can even be another OS). This advanced dynamic linking feature requires intimate knowledge of the target OS' binary representation. (I would actually really like to see Haskell's dynamics system to become as powerful as Clean's; it also supports polymorphism, for example)On Jul 15, 2013, at 04:31 AM, "Richard A. O'Keefe" wrote: On 13/07/2013, at 11:27 PM, J. Stutterheim wrote:- they then abandoned the Macintosh world forWindows. The Mac IDE was killed off; there isnow an IDE for Windows but not MacOS or Linux.The good news is that the latest version of Clean[2] and its code generator[3] now works fine again on 64 bit Mac OS X Is that still the command-line tools, or has the IDE been resurrected? - other major features remain Windows-onlyThe bad news is that this is true to some extend; the dynamics system is still largely Windows-only. However, this is the only language feature I can think of that really is Windows-only. I have never been able to understand why there should be ANY OS-dependency in the dynamics feature. - the available books about Clean are way out ofdate, several drafts of other books remainincomplete.- the documentation (like the Report) has always beenrather amateurish and incomplete. Certainlycompared with the Haskell documentation.An iTasks book is actually in the works, which will contain a fair bit of Clean (although it is not a dedicated Clean book). There are also concrete plans to update the language manual soon-ish. Not to be offensive, because after saying "Denk U" I have no more Dutch words I can use, but it would really pay to find a native speaker of English to give the manual a final polish.- there is nothing to compare with the Haskell Platform.Actually, yes there is[4]. A misundertanding. "Nothing to compare with" is idiomatic for "nothing of comparable size to". Yes, you _can_ compare the Clean Platform with the Haskell Platform; it's a lot smaller. It can be described as a mix between Haskell Platform and a mini Hackage-like repository. There is no such thing as a Clean alternative to cabal install, though.Keep in mind that there is only a handful of people working on Clean, while Haskell has a huge community in comparison. Haskell has always benefited from - openness - multiple implementations - documentation ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Homotopy Type Theory IRC Channel
Hello, I know there are many haskellers interested in dependent type theory so I wanted to mention that there is now an IRC channel on freenode for discussing Homotopy Type Theory (HoTT), e.g., the recent book, possible implementations, dependent type theory in general, etc. The channel is ##hott (NOTE the *two* hashes!) and you can connect directly through freenode's web interface if you don't already have a client: https://webchat.freenode.net/?channels=%23%23hott Currently we have around 50 members but the more the merrier! If you don't know much about IRC but would like to learn more: * http://www.irchelp.org — how IRC works, software clients, FAQs, and other info * http://freenode.net — info about the freenode IRC network specifically Cheers, Darin Morrison ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] [GSoC] Interactive-diagrams GSoC progress report
Hello everyone, I am participating in Haskell.org's Google Summer of Code, working on the interactive-diagrams [1] project. The mid-term evaluations are approaching and I am doing some writeup on the work I did so far: http://parenz.wordpress.com/2013/07/15/interactive-diagrams-gsoc-progress-report/ A beta-version of the site is also available to the public: http://paste.hskll.org Please note that this is not a final product and you may experience cryptic error messages, some downtime. The security is pretty tight though :) Any suggestions/comments are welcome. [1] https://google-melange.appspot.com/gsoc/proposal/review/google/gsoc2013/difrumin/1 -- Sincerely yours, -- Daniil Frumin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] partially indeterminate?
Hi. For learning, I was doing the "phone words" problem, where a function translates the digits of a phone number into all possible words. I am trying to connect this idea to the idea of list comprehensions / list monads (sort of the same thing, yes?) I know it is easy to do this: w = do two <- "ABC" three <- "DEF" four <- "GHI" -- and the other digits [[two, three, two, four]] -- for example But what if you don't know in advance what the digits will be? I'm not sure how to insert that deterministic component into this idea. So far, I have a framework like so: p dx = do undefined where m = map (\d -> case d of 2 -> "ABC" 3 -> "DEF" 4 -> "GHI" 5 -> "JKL" 6 -> "MNO" 7 -> "PRS" 8 -> "TUV" 9 -> "WXY" otherwise -> show d) dx I would appreciate any guidance. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ordNub
In my tests, using unordered-containers was slightly slower than using Ord, although as the number of repeated elements grows unordered-containers appears to have an advantage. I'm sure the relative costs of comparison vs hashing would affect this also. But both are dramatically better than the current nub. Has anyone looked at Bart's patches to see how difficult it would be to apply them (or re-write them)? On Mon, Jul 15, 2013 at 8:43 PM, Clark Gaebel wrote: > Apologies. I was being lazy. Here's a stable version: > > import qualified Data.HashSet as S > > hashNub :: (Ord a) => [a] -> [a] > hashNub l = go S.empty l > where > go _ [] = [] > go s (x:xs) = if x `S.member` s then go s xs > else x : go (S.insert x s) xs > > Which, again, will probably be faster than the one using Ord, and I > can't think of any cases where I'd want the one using Ord instead. I > may just not be creative enough, though. > > > - Clark > > On Mon, Jul 15, 2013 at 12:46 AM, Brandon Allbery > wrote: > > On Sun, Jul 14, 2013 at 7:54 AM, Clark Gaebel > wrote: > >> > >> Oops sorry I guess my point wasn't clear. > >> > >> Why ord based when hashable is faster? Then there's no reason this has > to > >> be in base, it can just be a > > > > Did the point about "stable" fly overhead? > > > > -- > > brandon s allbery kf8nh sine nomine > associates > > allber...@gmail.com > ballb...@sinenomine.net > > unix, openafs, kerberos, infrastructure, xmonad > http://sinenomine.net > > ___ > 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] ordNub
On 16 July 2013 11:46, John Lato wrote: > In my tests, using unordered-containers was slightly slower than using Ord, > although as the number of repeated elements grows unordered-containers > appears to have an advantage. I'm sure the relative costs of comparison vs > hashing would affect this also. But both are dramatically better than the > current nub. > > Has anyone looked at Bart's patches to see how difficult it would be to > apply them (or re-write them)? If I understand correctly, this function is proposed to be added to Data.List which lives in base... but the proposals here are about using either Sets from containers or HashSet from unordered-containers; I thought base wasn't supposed to depend on any other package :/ > > > > On Mon, Jul 15, 2013 at 8:43 PM, Clark Gaebel wrote: >> >> Apologies. I was being lazy. Here's a stable version: >> >> import qualified Data.HashSet as S >> >> hashNub :: (Ord a) => [a] -> [a] >> hashNub l = go S.empty l >> where >> go _ [] = [] >> go s (x:xs) = if x `S.member` s then go s xs >> else x : go (S.insert x s) xs >> >> Which, again, will probably be faster than the one using Ord, and I >> can't think of any cases where I'd want the one using Ord instead. I >> may just not be creative enough, though. >> >> >> - Clark >> >> On Mon, Jul 15, 2013 at 12:46 AM, Brandon Allbery >> wrote: >> > On Sun, Jul 14, 2013 at 7:54 AM, Clark Gaebel >> > wrote: >> >> >> >> Oops sorry I guess my point wasn't clear. >> >> >> >> Why ord based when hashable is faster? Then there's no reason this has >> >> to >> >> be in base, it can just be a >> > >> > Did the point about "stable" fly overhead? >> > >> > -- >> > brandon s allbery kf8nh sine nomine >> > associates >> > allber...@gmail.com >> > ballb...@sinenomine.net >> > unix, openafs, kerberos, infrastructure, xmonad >> > http://sinenomine.net >> >> ___ >> 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 > -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com http://IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ordNub
On Tue, Jul 16, 2013 at 10:31 AM, Ivan Lazar Miljenovic < ivan.miljeno...@gmail.com> wrote: > On 16 July 2013 11:46, John Lato wrote: > > In my tests, using unordered-containers was slightly slower than using > Ord, > > although as the number of repeated elements grows unordered-containers > > appears to have an advantage. I'm sure the relative costs of comparison > vs > > hashing would affect this also. But both are dramatically better than > the > > current nub. > > > > Has anyone looked at Bart's patches to see how difficult it would be to > > apply them (or re-write them)? > > If I understand correctly, this function is proposed to be added to > Data.List which lives in base... but the proposals here are about > using either Sets from containers or HashSet from > unordered-containers; I thought base wasn't supposed to depend on any > other package :/ > That was one of the points up for discussion: is it worth including a subset of Set functionality to enable a much better nub in base? Is it even worth having Data.List.nub if it has quadratic complexity? As an alternative, Bart's proposal was for both including ordNub in containers and an improved nub (with no dependencies outside base) in Data.List. Unfortunately the patches are quite old (darcs format), and I don't know how they'd apply to the current situation. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Non-recursive let [Was: GHC bug? Let with guards loops]
On 15/07/2013, at 8:23 PM, J. Stutterheim wrote: > The OS dependency for dynamics stems from the fact that the Clean dynamics > are quite a bit more powerful than Haskell's. For example, using dynamics, it > is possible to send arbitrary functions to another Clean application, which > can then dynamically link these functions in at runtime and immediately > execute them. It doesn't even need to be the same program, which Cloud > Haskell does require (and theoretically, it can even be another OS). This > advanced dynamic linking feature requires intimate knowledge of the target > OS' binary representation. There is no obvious reason why it should. Imagine a programming language implementation where a function is compiled to some abstract representation (like Kistler's Juice) and a native representation is added on loading or on first use. For Oberon, Kistler found that transmitting compressed abstract syntax trees and generating native code on reception took less time and yielded better code than sending native code. Even when reading from a local disc, loading compressed ASTs and generating native code on the fly was faster than a conventional dynamic linker. A major issue here, of course, is that "Windows" could be 32-bit or 64-bit, x86 or ARM, and even if you restrict attention to one of these combinations, there are things like exactly what SIMD instructions are available. > (I would actually really like to see Haskell's dynamics system to become as > powerful as Clean's; it also supports polymorphism, for example) Perhaps you could say something about the following problem: I have a data structure that includes some functions. These functions use version X of module M. I send that data structure to another application, which is using version Y of module M, where Y /= X. What happens? This is the primary reason why Erlang has not imitated Kali Scheme, which could also send functions. For that matter, what happens if the function is sent to another application (on a remote machine) that doesn't have _any_ version of module M and doesn't know where to find one? I am _not_ suggesting that these are problems that Clean could not solve or has not solved. On the contrary, I'm saying that it would be very interesting to hear how Clean has solved them. >From a security point of view, of course, failing to practice Safe Hex is a bit worrying, but proof-carrying code and signatures can go some way towards addressing that concern. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] partially indeterminate?
I will suggest an analogy to a similar (but simpler) situation.
Suppose you are adding up some numbers.
foo = let { x = 3; y = 4; z = 5 } in x + y + z
That pattern only works if you know in advance how many numbers you are
going to add.
Otherwise, you need a function that works on a whole list of numbers:
sum = foldr (+) 0
So...the short answer to your question is: use recursion. The better answer
is: use library functions that do the recursion for you. You might want to
look at foldM:
http://hackage.haskell.org/packages/archive/base/latest/doc/html/Control-Monad.html#v:foldM
-Karl
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ordNub
I'm procrastinating something else, so I wrote the patch to unordered-containers. Feel free to comment on the github link: https://github.com/tibbe/unordered-containers/pull/67 I'm still against having an Ord version, since my intuition tells me that hash-based data structures are faster than ordered ones. Someone else can write the patch, though! As a tangent, can anyone think of a data structure for which you can write an Ord instance but Hashable/Eq is impossible (or prove otherwise)? How about the converse? Regards, - Clark On Mon, Jul 15, 2013 at 10:40 PM, John Lato wrote: > On Tue, Jul 16, 2013 at 10:31 AM, Ivan Lazar Miljenovic > wrote: >> >> On 16 July 2013 11:46, John Lato wrote: >> > In my tests, using unordered-containers was slightly slower than using >> > Ord, >> > although as the number of repeated elements grows unordered-containers >> > appears to have an advantage. I'm sure the relative costs of comparison >> > vs >> > hashing would affect this also. But both are dramatically better than >> > the >> > current nub. >> > >> > Has anyone looked at Bart's patches to see how difficult it would be to >> > apply them (or re-write them)? >> >> If I understand correctly, this function is proposed to be added to >> Data.List which lives in base... but the proposals here are about >> using either Sets from containers or HashSet from >> unordered-containers; I thought base wasn't supposed to depend on any >> other package :/ > > > That was one of the points up for discussion: is it worth including a subset > of Set functionality to enable a much better nub in base? Is it even worth > having Data.List.nub if it has quadratic complexity? > > As an alternative, Bart's proposal was for both including ordNub in > containers and an improved nub (with no dependencies outside base) in > Data.List. Unfortunately the patches are quite old (darcs format), and I > don't know how they'd apply to the current situation. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ordNub
On Mon, Jul 15, 2013 at 10:31 PM, Ivan Lazar Miljenovic < ivan.miljeno...@gmail.com> wrote: > If I understand correctly, this function is proposed to be added to > Data.List which lives in base... but the proposals here are about > using either Sets from containers or HashSet from > unordered-containers; I thought base wasn't supposed to depend on any > other package :/ > As I understand it, currently we have a double proposal: simple ordNub in Data.List without external dependencies, and the other one in containers and/or unordered-containers as appropriate. -- brandon s allbery kf8nh sine nomine associates allber...@gmail.com ballb...@sinenomine.net unix, openafs, kerberos, infrastructure, xmonadhttp://sinenomine.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ordNub
On 16/07/2013, at 3:21 PM, Clark Gaebel wrote: > > I'm still against having an Ord version, since my intuition tells me > that hash-based data structures are faster than ordered ones. There are at least four different things that "an Ord version" might mean: - first sort a list, then eliminate duplicates - sort a list eliminating duplicates stably as you go (think 'merge sort', using 'union' instead of 'merge') - build a balanced tree set as you go - having a list that is already sorted, use that to eliminated duplicates cheaply. These things have different costs. For example, if there are N elements of which U are unique, the first as O(N.log N) cost, the third has O(N.log U) cost, and the fourth has O(N) cost. What I want is more often ordNubBy than ordNub, though. > Someone > else can write the patch, though! > > As a tangent, can anyone think of a data structure for which you can > write an Ord instance but Hashable/Eq is impossible (or prove > otherwise)? How about the converse? Since Ord has Eq as a superclass, and since 0 is a functionally correct hash value for anything, if you can implement Ord you can obviously implement Hashable/Eq. Whether it is *useful* to do so is another question. It turns out that it _is_ possible to define good quality hash functions on sets, but most code in the field to do so is pretty bad. (Just a modular sum or exclusive or.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ordNub
nubBy is a very good suggestion. Added! Regarding good hash functions: if your data structure is algebraic, you can derive generic and Hashable will give you a pretty good hash function: > data ADT a = C0 Int String | C1 [a] > deriving Generic > > instance Hashable a => Hashable (ADT a) It's magic! - Clark On Mon, Jul 15, 2013 at 11:35 PM, Richard A. O'Keefe wrote: > > On 16/07/2013, at 3:21 PM, Clark Gaebel wrote: >> >> I'm still against having an Ord version, since my intuition tells me >> that hash-based data structures are faster than ordered ones. > > There are at least four different things that "an Ord version" might > mean: > > - first sort a list, then eliminate duplicates > - sort a list eliminating duplicates stably as you go >(think 'merge sort', using 'union' instead of 'merge') > - build a balanced tree set as you go > - having a list that is already sorted, use that to >eliminated duplicates cheaply. > > These things have different costs. For example, if there are N > elements of which U are unique, the first as O(N.log N) cost, > the third has O(N.log U) cost, and the fourth has O(N) cost. > > What I want is more often ordNubBy than ordNub, though. > >> Someone >> else can write the patch, though! >> >> As a tangent, can anyone think of a data structure for which you can >> write an Ord instance but Hashable/Eq is impossible (or prove >> otherwise)? How about the converse? > > Since Ord has Eq as a superclass, and since 0 is a functionally > correct hash value for anything, if you can implement Ord you > can obviously implement Hashable/Eq. Whether it is *useful* to > do so is another question. > > It turns out that it _is_ possible to define good quality hash > functions on sets, but most code in the field to do so is pretty bad. > (Just a modular sum or exclusive or.) > > ___ > 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] ordNub
On 16 July 2013 10:31, Ivan Lazar Miljenovic wrote: > On 16 July 2013 11:46, John Lato wrote: >> In my tests, using unordered-containers was slightly slower than using Ord, >> although as the number of repeated elements grows unordered-containers >> appears to have an advantage. I'm sure the relative costs of comparison vs >> hashing would affect this also. But both are dramatically better than the >> current nub. >> >> Has anyone looked at Bart's patches to see how difficult it would be to >> apply them (or re-write them)? > > If I understand correctly, this function is proposed to be added to > Data.List which lives in base... but the proposals here are about > using either Sets from containers or HashSet from > unordered-containers; I thought base wasn't supposed to depend on any > other package :/ This discussion (on -cafe@) is just about what course of action to take; adding such functions to containers or unordered-containers would not require a libraries@ proposal. Conrad. > >> >> >> >> On Mon, Jul 15, 2013 at 8:43 PM, Clark Gaebel wrote: >>> >>> Apologies. I was being lazy. Here's a stable version: >>> >>> import qualified Data.HashSet as S >>> >>> hashNub :: (Ord a) => [a] -> [a] >>> hashNub l = go S.empty l >>> where >>> go _ [] = [] >>> go s (x:xs) = if x `S.member` s then go s xs >>> else x : go (S.insert x s) xs >>> >>> Which, again, will probably be faster than the one using Ord, and I >>> can't think of any cases where I'd want the one using Ord instead. I >>> may just not be creative enough, though. >>> >>> >>> - Clark >>> >>> On Mon, Jul 15, 2013 at 12:46 AM, Brandon Allbery >>> wrote: >>> > On Sun, Jul 14, 2013 at 7:54 AM, Clark Gaebel >>> > wrote: >>> >> >>> >> Oops sorry I guess my point wasn't clear. >>> >> >>> >> Why ord based when hashable is faster? Then there's no reason this has >>> >> to >>> >> be in base, it can just be a >>> > >>> > Did the point about "stable" fly overhead? >>> > >>> > -- >>> > brandon s allbery kf8nh sine nomine >>> > associates >>> > allber...@gmail.com >>> > ballb...@sinenomine.net >>> > unix, openafs, kerberos, infrastructure, xmonad >>> > http://sinenomine.net >>> >>> ___ >>> 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 >> > > > > -- > Ivan Lazar Miljenovic > ivan.miljeno...@gmail.com > http://IvanMiljenovic.wordpress.com > > ___ > 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
