Logs: freenode/#haskell
| 2021-03-10 18:14:31 | <monochrom> | In fact, "search" is terribly ambiguous, too. :) |
| 2021-03-10 18:14:54 | <carbolymer> | ok, so running isInfixOf over all elements ;] |
| 2021-03-10 18:15:03 | <carbolymer> | Data.Bytesting.Char8.isInfixOf |
| 2021-03-10 18:15:40 | <carbolymer> | maerwald: you mean search in general, or lists for search? |
| 2021-03-10 18:15:47 | <maerwald> | lists for search |
| 2021-03-10 18:16:35 | <monochrom> | Alright, I don't know how to do better than exhaustive search, so may as well just list and prepend. |
| 2021-03-10 18:16:43 | × | nf quits (~n@2a03:4000:53:fb4:1869:15ff:fe71:8ab) (Quit: Fairfarren.) |
| 2021-03-10 18:16:43 | <carbolymer> | so which datastructure would be better for substring searches? |
| 2021-03-10 18:16:58 | <monochrom> | I'm sure there is a better way and I'm sure it's in an obscure paper from those algorithm people. |
| 2021-03-10 18:17:26 | × | p8m quits (p8m@gateway/vpn/protonvpn/p8m) (Ping timeout: 260 seconds) |
| 2021-03-10 18:17:30 | <monochrom> | KMP or Boyer-Moore is better for substring searches. |
| 2021-03-10 18:18:00 | <monochrom> | But here you are one level above. |
| 2021-03-10 18:18:04 | × | mayleesia quits (590caa9e@dynamic-089-012-170-158.89.12.pool.telefonica.de) (Quit: Connection closed) |
| 2021-03-10 18:18:12 | × | chele quits (~chele@ip5b40237d.dynamic.kabel-deutschland.de) (Remote host closed the connection) |
| 2021-03-10 18:18:18 | <carbolymer> | actually, KMP or Boyer-Moore perform few times slower than Rabin-Karp in `isInfixOf` |
| 2021-03-10 18:18:33 | × | conal quits (~conal@209.58.139.5) (Ping timeout: 264 seconds) |
| 2021-03-10 18:18:34 | <carbolymer> | or `stringsearch` has inefficient implementations |
| 2021-03-10 18:19:04 | <monochrom> | Here your level is "I have n strings, find one that is a superstring of blah". |
| 2021-03-10 18:19:12 | → | Franciman joins (~francesco@host-82-49-79-189.retail.telecomitalia.it) |
| 2021-03-10 18:19:15 | <dolio> | Those all build some kind of other structure from the string, right? It's probably better to build that structure than a list. |
| 2021-03-10 18:19:35 | <carbolymer> | dolio: actually it's the opposite, they build structure from the needle |
| 2021-03-10 18:19:42 | <carbolymer> | and I'm wondering how to store haystacks |
| 2021-03-10 18:19:48 | <maerwald> | carbolymer: is the needle known at list construction time? |
| 2021-03-10 18:19:52 | <carbolymer> | no |
| 2021-03-10 18:19:57 | × | nineonine quits (~nineonine@2604:3d08:7785:9600:e9a2:5149:9431:1ba4) (Ping timeout: 260 seconds) |
| 2021-03-10 18:20:01 | <maerwald> | the length? |
| 2021-03-10 18:20:22 | <carbolymer> | of the needle? 3-15 chars, haystacks? probably up to 300 chars |
| 2021-03-10 18:20:49 | <maerwald> | ok, 3 is too low to have any gains for pre-filtering |
| 2021-03-10 18:21:18 | × | Waifod quits (~Waifod@91.106.123.186) (Ping timeout: 245 seconds) |
| 2021-03-10 18:21:31 | <carbolymer> | yeah |
| 2021-03-10 18:22:05 | <maerwald> | maybe we can parallelize the search? |
| 2021-03-10 18:23:24 | → | nf joins (~n@monade.li) |
| 2021-03-10 18:24:45 | → | nineonin_ joins (~nineonine@2604:3d08:7785:9600:ec09:110c:743a:f501) |
| 2021-03-10 18:25:02 | <maerwald> | https://hackage.haskell.org/package/parallel-3.2.1.1/docs/Control-Parallel-Strategies.html#v:evalListN |
| 2021-03-10 18:25:05 | → | Ebin joins (6746c694@103.70.198.148) |
| 2021-03-10 18:25:09 | <Ebin> | hai |
| 2021-03-10 18:25:15 | <Ebin> | is any one here |
| 2021-03-10 18:25:22 | × | HiRE quits (~HiRE@104.128.237.40) (Ping timeout: 260 seconds) |
| 2021-03-10 18:25:27 | <maerwald> | sth like that... never used the lib |
| 2021-03-10 18:25:44 | <Ebin> | i am interested in know more about haskell |
| 2021-03-10 18:25:46 | → | HiRE joins (~HiRE@104.128.237.40) |
| 2021-03-10 18:25:59 | → | conal joins (~conal@209.58.139.5) |
| 2021-03-10 18:26:03 | <Ebin> | can anyone share your experience |
| 2021-03-10 18:26:09 | <Ebin> | haskell |
| 2021-03-10 18:26:13 | → | DataComputist joins (~lumeng@50.43.26.251) |
| 2021-03-10 18:26:18 | <Ebin> | how long it take to learn haskell |
| 2021-03-10 18:26:34 | <Ebin> | is it good form production level projects |
| 2021-03-10 18:26:41 | <Ebin> | can any one help me .. |
| 2021-03-10 18:26:47 | <maerwald> | Ebin: what kind of project? |
| 2021-03-10 18:26:49 | <dolio> | carbolymer: A trie, then? |
| 2021-03-10 18:27:30 | <dolio> | At each stage you have a suffix trie, and want to compute the suffix trie from prepending one character? |
| 2021-03-10 18:27:46 | <tomsmeding> | carbolymer: is the haystack kind of random in distribution? |
| 2021-03-10 18:27:52 | <Ebin> | nothing like that i do not planning to do any project, i am interested in learning a function language two chooses in frond of me is elixir and haskell |
| 2021-03-10 18:28:15 | <tomsmeding> | oh wait you said that the needle isn't known at construction time, hmm |
| 2021-03-10 18:28:21 | <maerwald> | Ebin: haskell probably exposes you to more concepts... elixir might be easier to learn (not sure though) |
| 2021-03-10 18:28:25 | <monochrom> | A trie shines for prefixes only. |
| 2021-03-10 18:28:29 | <Ebin> | my agenda is to learn a functional programming langauge |
| 2021-03-10 18:28:54 | <monochrom> | err suffixes only, in that case |
| 2021-03-10 18:29:03 | <maerwald> | Ebin: there aren't many purely functional programming languages and even less that are useful. Elixir is functional, but not purly functional |
| 2021-03-10 18:29:22 | <maerwald> | so if you're into that, haskell is a good choice |
| 2021-03-10 18:29:30 | → | nineonine joins (~nineonine@2604:3d08:7785:9600:383a:c6c2:f8c1:ca2c) |
| 2021-03-10 18:29:44 | <Ebin> | i am a computer engineering student ,while learning programming paradigms, i know more about function programming languages which are good at concurrency control |
| 2021-03-10 18:29:56 | <carbolymer> | maerwald: nope, I can utilize one core ;) parallelization would be too easy |
| 2021-03-10 18:29:57 | × | conal quits (~conal@209.58.139.5) (Quit: Computer has gone to sleep.) |
| 2021-03-10 18:30:26 | <Ebin> | did Haskell have any package manager like python pip |
| 2021-03-10 18:30:31 | <maerwald> | Ebin: yeah |
| 2021-03-10 18:30:33 | <dolio> | But `isInfixOf` just searches for isPrefixOf in a list of suffixes. |
| 2021-03-10 18:30:47 | <tomsmeding> | carbolymer: okay my question stands, is the haystack quite random? If so, while constructing store the suffix _sums_ of the haystack (can be done in constant time per pushed element, of course). Then when you know the needle's length, say N, compute all the sums of substrings of length N, and also compute the sum of the characters in the needle. Then only check actual substring equality on the |
| 2021-03-10 18:30:48 | <tomsmeding> | positions where the "hashes" match |
| 2021-03-10 18:31:10 | → | p8m joins (p8m@gateway/vpn/protonvpn/p8m) |
| 2021-03-10 18:31:30 | <tomsmeding> | if there's a low probability that the "hashes" match in general, this could reduce time to little more than linear in the haystack, instead linear in haystack times needle |
| 2021-03-10 18:31:35 | <dolio> | Oh, I guess the problem is that you don't know which suffixes to modify. |
| 2021-03-10 18:31:38 | <tomsmeding> | s/instead/instead of/ |
| 2021-03-10 18:31:43 | <carbolymer> | tomsmeding: I suspect it's random |
| 2021-03-10 18:31:48 | <tomsmeding> | "suspect" |
| 2021-03-10 18:32:00 | × | kuribas quits (~user@ptr-25vy0i7qqmcrk0iummz.18120a2.ip6.access.telenet.be) (Quit: ERC (IRC client for Emacs 26.3)) |
| 2021-03-10 18:32:03 | <carbolymer> | yeah, I can not know, because I don't know the dataset upfront |
| 2021-03-10 18:32:10 | <monochrom> | Nice hashing scheme, tomsmeding. |
| 2021-03-10 18:32:18 | <tomsmeding> | if you need guaranteed performance, my scheme won't work :) |
| 2021-03-10 18:32:42 | <monochrom> | Just use a cryptographic hash, then everything is really really random. :) |
| 2021-03-10 18:33:02 | <tomsmeding> | and substring search via homomorphic encryption? |
| 2021-03-10 18:33:08 | <tomsmeding> | yeah, that will speed it up :) |
| 2021-03-10 18:33:08 | <monochrom> | haha |
| 2021-03-10 18:33:37 | × | crobbins quits (~crobbins@2601:2c1:200:ec50:5d1f:8754:d509:f553) (Remote host closed the connection) |
| 2021-03-10 18:33:38 | × | nineonin_ quits (~nineonine@2604:3d08:7785:9600:ec09:110c:743a:f501) (Ping timeout: 264 seconds) |
| 2021-03-10 18:33:38 | → | conal joins (~conal@209.58.139.5) |
| 2021-03-10 18:33:47 | → | Waifod joins (Waifod@gateway/vpn/protonvpn/waifod) |
| 2021-03-10 18:33:52 | <tomsmeding> | Ebin: the Haskell package manager works more like a Python virtualenv, not really globally like pip |
| 2021-03-10 18:34:08 | <tomsmeding> | or, well, the haskell package managerS -- there are two in common usage |
| 2021-03-10 18:34:17 | → | crobbins joins (~crobbins@2601:2c1:200:ec50:30f7:9e8e:ec2a:2032) |
| 2021-03-10 18:35:02 | <Ebin> | cabal |
| 2021-03-10 18:35:11 | <tomsmeding> | stack is the other one |
| 2021-03-10 18:35:15 | <Ebin> | is it good to start |
| 2021-03-10 18:35:21 | <monochrom> | Yes. |
| 2021-03-10 18:35:47 | <monochrom> | But where is sm[m] for a second opinion? >:) |
| 2021-03-10 18:35:48 | × | geekosaur quits (82650c7a@130.101.12.122) (Quit: Connection closed) |
| 2021-03-10 18:36:09 | <maerwald> | There are more interesting things for newcomers to learn than about tooling wars |
| 2021-03-10 18:36:09 | → | geekosaur joins (82650c7a@130.101.12.122) |
| 2021-03-10 18:36:38 | <monochrom> | OK then, my third opinion. |
| 2021-03-10 18:36:52 | <monochrom> | Ignore packages. Start with the interpreter ghci first. |
All times are in UTC.