tag:blogger.com,1999:blog-6028449519062514692.post2613054836020446179..comments2023-09-11T12:02:42.908-04:00Comments on ha4: Combinatory Regular Expressions in HaskellAnonymoushttp://www.blogger.com/profile/08313802559573057206noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-6028449519062514692.post-2549504525497088772011-07-19T18:41:18.101-04:002011-07-19T18:41:18.101-04:00I have implemented state sharing, now instead of e...I have implemented state sharing, now instead of exponential I also get polynomial behavior. Micro-benchmarks seem only 10-100x slower than your regex-applicative, which makes me quite happy. Thanks!Anonymoushttps://www.blogger.com/profile/08313802559573057206noreply@blogger.comtag:blogger.com,1999:blog-6028449519062514692.post-47551117280171680562011-07-19T12:13:47.729-04:002011-07-19T12:13:47.729-04:00Right. Ideally, it would be linear, and I'm wo...Right. Ideally, it would be linear, and I'm working on that at the moment. Still, it's clearly not exponential.<br /><br />If you have tested the package with some old packages, please let me know the exact versions and I'll relax the constraints in the next release.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6028449519062514692.post-79210142111558037332011-07-19T08:35:04.378-04:002011-07-19T08:35:04.378-04:00Silly me, the time must be polynomial not exponent...Silly me, the time must be polynomial not exponential so yes that warrants a pass.Anonymoushttps://www.blogger.com/profile/08313802559573057206noreply@blogger.comtag:blogger.com,1999:blog-6028449519062514692.post-53843945309771202712011-07-18T14:33:56.578-04:002011-07-18T14:33:56.578-04:00I have GHC 6.12.3 btw and I had to relax the const...I have GHC 6.12.3 btw and I had to relax the constraint on `base` to build regex-applicative, in case this is relevant..Anonymoushttps://www.blogger.com/profile/08313802559573057206noreply@blogger.comtag:blogger.com,1999:blog-6028449519062514692.post-43400200232854928272011-07-18T14:24:28.140-04:002011-07-18T14:24:28.140-04:00Hi!
The same test you link to with n=1000 takes m...Hi!<br /><br />The same test you link to with n=1000 takes minutes to compute on my machine in GHCI.. Is it because I am missing -O2 or something? Frankly I have no idea how to benchmark Haskell.<br /><br />But you are absolutely right, not merging the states as I do in the gist above won't do at all. Now I am curious how you merge them, will read into your as soon as I get some time for that. <br /><br />Thanks,<br /><br />AAnonymoushttps://www.blogger.com/profile/08313802559573057206noreply@blogger.comtag:blogger.com,1999:blog-6028449519062514692.post-8455062314692918102011-07-17T18:24:31.480-04:002011-07-17T18:24:31.480-04:00Anton,
how did you measure it?
I ran that test a...Anton,<br /><br />how did you measure it?<br /><br />I ran that test and regex-applicative passed it. The details are here: https://github.com/feuerbach/regex-applicative/wiki/ExptestAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6028449519062514692.post-40487569933691106702011-07-17T14:37:38.840-04:002011-07-17T14:37:38.840-04:00Hi Roman,
I am still thinking about this problem ...Hi Roman,<br /><br />I am still thinking about this problem and trying it out in both ML and Haskell.<br /><br />I have also tried out your implementation in regex-applicative.<br /><br />Unfortunately it looks like your implementation (as well as all my attempts so far) have exponential behavior on testTNFA benchmark in the above gist. I will be glad to be proven otherwise since I might be measuring it wrong.<br /><br />The testTNFA benchmark comes from this article:<br /><br />http://swtch.com/~rsc/regexp/regexp1.html<br /><br />Is inevitable for our a combinatory implementation to have this exponential behavior on testTNFA I wonder..<br /><br />Otherwise your work looks really cool!Anonymoushttps://www.blogger.com/profile/08313802559573057206noreply@blogger.comtag:blogger.com,1999:blog-6028449519062514692.post-77545702644972171662011-07-17T09:16:12.294-04:002011-07-17T09:16:12.294-04:00Yes, another good test it fails is
https://gist.g...Yes, another good test it fails is<br /><br />https://gist.github.com/1087579Anonymoushttps://www.blogger.com/profile/08313802559573057206noreply@blogger.comtag:blogger.com,1999:blog-6028449519062514692.post-77906033654555720342011-07-17T06:29:13.856-04:002011-07-17T06:29:13.856-04:00I've taken a look at this. The problem here is...I've taken a look at this. The problem here is that you don't "merge" the states back. Thus, the code suffers from a combinatorial explosion.<br /><br />Example:<br />test n = run (compile $ length <$> (many $ string "a" <|> string "aa")) $ replicate n 'a'<br /><br />Test> test 20<br />Just 20<br />(0.13 secs, 18891204 bytes)<br />Test> test 22<br />Just 22<br />(0.38 secs, 44580336 bytes)<br />Test> test 24<br />Just 24<br />(1.05 secs, 112208144 bytes)<br />Test> test 25<br />Just 25<br />(1.82 secs, 179842856 bytes)<br />Test> test 26<br />Just 26<br />(2.50 secs, 289945732 bytes)<br />Test> test 27<br />Just 27<br />(4.44 secs, 467622444 bytes)<br /><br />(The code was compiled with -O2)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6028449519062514692.post-83949933564074777042011-07-16T12:10:05.573-04:002011-07-16T12:10:05.573-04:00That's funny, I was thinking on the same probl...That's funny, I was thinking on the same problem recently, and it developed into the regex-applicative package. https://github.com/feuerbach/regex-applicative<br /><br />I will also evaluate your approach and let you know what I think.Anonymousnoreply@blogger.com