raduom 2017-01-26 03:46:03
merijn aren't kd trees used to store that?
wz1000 2017-01-26 03:53:55
merijn: Wouldn't something like a quadtree do?
merijn 2017-01-26 03:54:13
wz1000: quadtrees only deal with 2 dimensional non-overlapping positions
wz1000 2017-01-26 03:54:44
merijn: You can extend them to 3 dimensions
opqdonut 2017-01-26 03:55:12
octtrees
wz1000 2017-01-26 03:55:12
have 2^n branches
wz1000 2017-01-26 03:55:34
where n is the number of dimensions
merijn 2017-01-26 03:55:46
wz1000: Right, but I need 8+ dimensions with overlapping ranges :)
opqdonut 2017-01-26 03:55:51
or have a binary tree and separating hyperplanes
merijn 2017-01-26 03:56:01
opqdonut: Tell me more :)
Jinxit 2017-01-26 03:56:38
kd-trees is the generalized version
Jinxit 2017-01-26 03:56:59
oh they were already mentioned
merijn 2017-01-26 03:57:12
I don't think kd-trees are appropriate, since I don't have discrete values but ranges
opqdonut 2017-01-26 03:57:13
is your stuff axis aligned? then just pick an axis and a threshold per node, and split the data into parts where axisthreshold
opqdonut 2017-01-26 03:57:26
hmm I didn't see your original problem
Jinxit 2017-01-26 03:57:40
oh ranges hmm
Jinxit 2017-01-26 03:58:07
so you want to see if it's inside a cuboid basically?
Jinxit 2017-01-26 03:58:11
in whatever dimensionality
merijn 2017-01-26 03:58:24
opqdonut: Problem is I have N dimension and I have key-value pairs where the key consists of N ranges (i.e. one range per dimension) which is just a "min" and "max" value
opqdonut 2017-01-26 03:58:26
sticking startx, endx, starty, endy, ..., in sql sounds like a good starting point actually
merijn 2017-01-26 03:58:54
opqdonut: I want to be able to do things like "give me all keys where the nth dimensions range includes value X'
opqdonut 2017-01-26 03:59:04
yeah
opqdonut 2017-01-26 03:59:18
for a custom datastructure approach, build an interval tree per dimension
merijn 2017-01-26 03:59:22
Bonus points if I can easily generalise it to multiple values of N
Jinxit 2017-01-26 03:59:23
still feels like something kd-tree-like is the proper solution
opqdonut 2017-01-26 03:59:31
> an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point
lambdabot 2017-01-26 03:59:34
Jinxit 2017-01-26 03:59:41
yeah that sounds right
opqdonut 2017-01-26 03:59:45
oops, shouldn't use > as a quote here
wz1000 2017-01-26 04:03:05
merijn: How about an interval tree or a segment tree?
opqdonut 2017-01-26 04:03:47
wz1000: yeah, interval tree per dimension is the right thing based on his description
merijn 2017-01-26 04:04:50
wz1000: I need to look up how those work to see if it works :)
merijn 2017-01-26 04:05:09
opqdonut: I'm not sure if it's possible to make an interval tree per dimension work?
opqdonut 2017-01-26 04:05:20
merijn: "an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point"
opqdonut 2017-01-26 04:06:14
merijn: so I was thinking about something like have the data in an array, and have the interval trees be indexes on top of it. so the vals in the interval trees are indexes to the array
merijn 2017-01-26 04:06:20
oh, I suppose that could work if you then do an intersection after looking up in each tree
Jinxit 2017-01-26 04:06:37
and if any fail on the way, bail out
opqdonut 2017-01-26 04:06:50
right, you need intersections, then interval trees won't be optimal, but probably good enough
cobreadmonster 2017-01-26 04:07:38
Is ghc applying for gsoc?
merijn 2017-01-26 04:08:13
cobreadmonster: Probably, they've been part of gsoc almost every year (except last, I think? but last year other sponsors stepped in)
cobreadmonster 2017-01-26 04:08:27
merijn: Would you supervise my gsoc?
cobreadmonster 2017-01-26 04:08:34
I want to do something interesting.
wz1000 2017-01-26 04:08:44
cobreadmonster: Yes, they've applied. I just asked sclv yesterday.
merijn 2017-01-26 04:09:31
cobreadmonster: I don't really work on GHC except like 3 minor patches I wrote, plus I don't have the time for that :)
cobreadmonster 2017-01-26 04:09:48
merijn: I wanted to do something academic :(
cobreadmonster 2017-01-26 04:09:57
and yeah, I know you don't have much time.
merijn 2017-01-26 04:10:31
cobreadmonster: Try emailing ghc-devs, I'm sure there's people who can supervise :)
merijn 2017-01-26 04:13:57
opqdonut: hmmm, looks like SQLite actually has builtin support for range queries, so rather than implementing/searching for a interval tree interpretation I might just use that one
jchia_1 2017-01-26 04:18:25
I've previously built my app with "stack build" using --library-profiling --executable-profiling. Now that I'm done profiling, I want to build a regular executable without any profiling slowdown, but when I "stack build" without those options, no new compilation happens and I still get the original slow binary. Is there something better I can do than using "stack clean" before "stack build"?
ph88 2017-01-26 04:22:56
i made this parser which seems to loop forever and i can't figure out why, anyone want to have a look? https://paste.fedoraproject.org/537002/48544022/
phadej 2017-01-26 04:24:34
ph88: p_C accepts empty string, and you "some" it
phadej 2017-01-26 04:24:58
some of empty string is infinitely many, and no input is consumed
ph88 2017-01-26 04:26:03
but the parser should still return CC []
ph88 2017-01-26 04:26:22
because it could match empty string
phadej 2017-01-26 04:26:57
that one does, but DF[DU (CC []), DU (CC []), DU (CC []), ...]
phadej 2017-01-26 04:27:11
but the p_A returns that
ph88 2017-01-26 04:27:12
i didn't even know many is monitoring how much input is consumed o_O i thought the argument parser just had to succeed for many to succeed
quchen 2017-01-26 04:27:32
jchia_1: Try --no-library-profiling maybe?
phadej 2017-01-26 04:28:03
(or would)
ph88 2017-01-26 04:28:46
phadej, p_A only has to return one DU (CC []) for some to succeed, no ?
merijn 2017-01-26 04:29:06
ph88: some will return *as many as it can*
merijn 2017-01-26 04:29:18
ph88: Since it consumes no input, as many as it can is infinite
ph88 2017-01-26 04:29:44
in this case i expect it to return 1 of DU (CC [])
phadej 2017-01-26 04:30:00
:source some
ph88 2017-01-26 04:30:10
@src some
lambdabot 2017-01-26 04:30:10
some v = some_v
lambdabot 2017-01-26 04:30:10
where many_v = some_v <|> pure []
lambdabot 2017-01-26 04:30:10
some_v = (:) <$> v <*> many_v
merijn 2017-01-26 04:30:23
ph88: Why do you expect it to stop? It never fails
merijn 2017-01-26 04:30:45
ph88: "some p" parses as many 'p' as it can, until 'p' fails
merijn 2017-01-26 04:30:53
ph88: If 'p' never fails, some never stops parsing
ph88 2017-01-26 04:31:01
oh right that's why it keeps looping -___-
jchia_1 2017-01-26 04:31:22
quchen: It doesn't work. I can still give profiling RTS flags.
ph88 2017-01-26 04:36:19
merijn, this is just so hard to debug in large grammars, do you have any hints ?
merijn 2017-01-26 04:37:10
ph88: tbh, I've never written parsers that don't consume input, I don't quite see what the point of that would be?
phadej 2017-01-26 04:39:21
iirc `parsec` throws exception if you do many (many $ char 'a') for example
phadej 2017-01-26 04:39:31
i.e. it tracks whether parsers consumes any input or doesn't
phadej 2017-01-26 04:40:04
you can avoid the check by writing recursion manually, so it's not fail proof, but still...
phadej 2017-01-26 04:40:32
not sure if megaparsec removed that (and why)
ph88 2017-01-26 04:41:38
merijn, in development i don't want to write the entire grammar at once. I want to split off sub-tree of the grammar. So it happens often that there are parsers that don't consume input
merijn 2017-01-26 04:42:09
ph88: Looks like you're writing top down, though. I would recommend writing your grammars bottom up
merijn 2017-01-26 04:42:24
That way you always have bits that consume input for testing
ph88 2017-01-26 04:42:39
merijn, yes it's true i wrote top-down :/
maerwald 2017-01-26 04:43:12
the stuff at the bottom is sometimes the most annoying though
maerwald 2017-01-26 04:43:24
(e.g. in SQL)
ph88 2017-01-26 04:43:28
there is nothing warning me if i write a parser that doesn't consume input
