ij 2017-02-01 05:53:28
I succeeded in slowing down regex-tdfa by matching "aaaaaaaaaaaaaaaaaaa" with /a*(a*)a*/. Question is why? Whichever branch will work, so shouldn't it just pick the first and be done with it?
roxxik 2017-02-01 05:55:33
aren't finite automaton guaranteed to run in O(n) ?
osa1 2017-02-01 05:55:56
speaking of regex I was wondering just yesterday what happens if I use a regex like a*a in alex and try to tokenize "aaaaaaaaaa"
phadej 2017-02-01 05:56:58
roxxik: matching yes, grouping no
phadej 2017-02-01 05:57:13
roxxik: i.e. /a*a*a*/ would be linear
tsahyt 2017-02-01 05:57:26
How does the Eq instance on STRefs work? Is it like a pointer equality or something?
tsahyt 2017-02-01 05:57:40
it's defined as isTrue# (sameMutVar# v1# v2#)
roxxik 2017-02-01 05:57:52
phadej: finite automatons only do matching ;)
tsahyt 2017-02-01 05:57:59
oh wait, it actually has a comment above too. It is pointer equality then
phadej 2017-02-01 05:58:30
tsahyt: would be great to turn it into haddock comment
tsahyt 2017-02-01 05:58:35
agreed
phadej 2017-02-01 05:58:42
tsahyt: could you make a PR to ghc :)
ongy 2017-02-01 05:59:12
there's a paper about the entire STM stuff that's pretty nice to read, which explains it aswell. But I'm not sure how much of that is outdated these days
tsahyt 2017-02-01 05:59:14
they accept PRs on github now, I could actually do that
merijn 2017-02-01 05:59:23
tsahyt: Pointer equality on the ref, yes
tsahyt 2017-02-01 05:59:24
I'll write it on my todo list
merijn 2017-02-01 05:59:38
ongy: I think most of it still applies
phadej 2017-02-01 06:01:03
ij: not sure whether tdfa has guarantees, that /a*/ is the longest match, so your example should have empty string as the capture
phadej 2017-02-01 06:01:40
ij: but i'm not sure how tdfa works, whether it's backtracking or something smarter
ij 2017-02-01 06:03:55
* should be greedy, I think.
glguy 2017-02-01 06:04:59
phadej: It's "tagged" dfa, so not backtracking
glguy 2017-02-01 06:05:40
ij: You could post the code that shows the slowdown you've observed
ij 2017-02-01 06:05:57
It's just matching with =~.
ij 2017-02-01 06:06:27
Do you think the code will be enlightening in this case?
glguy 2017-02-01 06:06:33
ij: Perhaps you're just not actually using TDFA
glguy 2017-02-01 06:06:55
I think it's more likely that your code is wrong than that your example slows down the regex-tdfa package
ij 2017-02-01 06:07:55
Sigh... Here's the code: http://sprunge.us/bHfI It's a little dense and I could refactor it one day.
glguy 2017-02-01 06:09:50
ij: =~ doesn't appear in that code
ij 2017-02-01 06:10:25
Regex TDFA doesn't include subtitution, so I stole a module from hledger code. http://sprunge.us/IKTO
glguy 2017-02-01 06:10:41
You can explore in GHCi and see that: getAllTextMatches (replicate 1000 'a' =~ "a*(a*)a*") :: [String]
glguy 2017-02-01 06:10:43
runs without delay
ij 2017-02-01 06:16:04
getAllTextMatches (replicate 1000 'a' =~ (concat $ take 30 $ repeat ("a*(a*)*" :: String))) :: [String]
ph88 2017-02-01 06:24:28
lol http://yannesposito.com/Scratch/fr/blog/Helping-avoid-Haskell-Success/
jophish 2017-02-01 06:27:32
"Explain that they should never use a binary distribution of GHC!"
jophish 2017-02-01 06:28:03
"Also explain them that in order to be able to handle lib dependencies correctly they MUST first learn Nix!" -- I can get behind this
ongy 2017-02-01 06:37:37
bootstrapping ghc from a C compiler is fun!
ertes 2017-02-01 06:38:29
certainly didn't keep me away
ertes 2017-02-01 06:38:39
functional programming? hell yeah!
ertes 2017-02-01 06:38:47
functional deployment? TAKE MY MONEY!
