文件列表:

LICENSE (1070, 2023-05-28)
bench-out/ (0, 2023-05-28)
bench-out/GenSummary.hs (6833, 2023-05-28)
bench-out/bench-out.csv (39959, 2023-05-28)
bench-out/bench-out.txt (32093, 2023-05-28)
bench-out/bench.sh (313, 2023-05-28)
bench/ (0, 2023-05-28)
bench/AhoCorasickBench.hs (1745, 2023-05-28)
bench/ArrayBench.hs (3770, 2023-05-28)
bench/ArrayNFData.hs (309, 2023-05-28)
bench/BFSBench.hs (449, 2023-05-28)
bench/Bench.hs (2016, 2023-05-28)
bench/BinSearchBench.hs (915, 2023-05-28)
bench/CentroidDecompBench.hs (820, 2023-05-28)
bench/ConvexHullBench.hs (584, 2023-05-28)
bench/DSUBench.hs (1149, 2023-05-28)
bench/DijkstraBench.hs (952, 2023-05-28)
bench/DinicBench.hs (1313, 2023-05-28)
bench/FenwickBench.hs (1756, 2023-05-28)
bench/FenwickMutBench.hs (1350, 2023-05-28)
bench/FloydWarshallBench.hs (691, 2023-05-28)
bench/HLDBench.hs (1291, 2023-05-28)
bench/KMPBench.hs (538, 2023-05-28)
bench/KruskalBench.hs (608, 2023-05-28)
bench/LCABench.hs (839, 2023-05-28)
bench/MIntBench.hs (587, 2023-05-28)
bench/MathBench.hs (1279, 2023-05-28)
bench/MoBench.hs (1496, 2023-05-28)
bench/ModBench.hs (1486, 2023-05-28)
bench/PQTreeBench.hs (881, 2023-05-28)
bench/PruferBench.hs (756, 2023-05-28)
bench/RerootFoldBench.hs (533, 2023-05-28)
bench/SegTreeBench.hs (1356, 2023-05-28)
bench/SegTreeLazyBench.hs (2750, 2023-05-28)
... ...

# haccepted  Data structures and algorithms for competitive programming in Haskell ## About This library contains data structures and algorithms primarily intended for use in [competitive programming](https://en.wikipedia.org/wiki/Competitive_programming). This means that, unlike a typical library, the source code in this library is meant to be looked at, copied, and modified by anyone using it. It is expected that the code in this library will be _correct_ and _fast_. * Property testing with [QuickCheck](https://hackage.haskell.org/package/QuickCheck) is used to check for correctness. * Benchmarking with [criterion](https://hackage.haskell.org/package/criterion) is used to ensure good performance. **Disclaimer**: I'm new to Haskell. Feedback is welcome! :) ### Haskell and competitive programming

Expand

Competitive programming today is largely dominated by C++, followed by Python and Java, in spite of many judges offering a large selection of languages to use. When I tried Haskell, I found it usually leads to short and neat solutions compared to typical imperative implementations. Other benefits of Haskell, like its ready-to-use abstractions and persistent-by-default data structures, are very nice to have. Of course, all this comes at a cost, the most important of which is speed. Simpler problems usually pose no risk, but it is possible that, contrary to the title of this repo, complex algorithms when not heavily optimized will be too slow to be accepted by an online judge. That being said, I still find it enjoyable and worth the effort to solve problems using Haskell, and I hope you'll agree.

### Functional style?

Expand

Functional programming is fun, but sometimes mutable state is necessary for an efficient implementation. Luckily, Haskell allows working with mutable state in the ST monad. So, I'm a little conflicted about the style that should be used in this library. Should the library as fast as possible but boring, using ST everywhere? Should it be as functional as possible, even at the cost of speed? I feel the answer is somewhere in the middle, for now. So here are some loose rules I follow. - Functional style is preferred. - If functional style worsens the time complexity of an algorithm, ST is used. - Data structures are usually functional, making them persistent. - If an algorithm is simpler or a lot faster in the constant factor to implement in ST, ST is used.

## Browsing All source files are present in the [`src`](/src) directory. Each file has a header comment, usually with four parts. 1. An overview of the data structure or algorithm 2. Sources that were referred to when implenting the data structure or algorithm 3. Some notes about the implementation 4. Descriptions and time complexities of the functions intended for external use When using as a black box, it suffices to only read 1 and 4. Example submissions are on the [Examples](https://github.com/meooow25/haccepted/wiki/Examples) page. Tests are found in the [`tests`](/tests) directory. Benchmarks are in the [`bench`](/bench) directory. A benchmark summary file is at [`bench-out/bench-out.txt`](/bench-out/bench-out.txt). ## Judges A non-exhaustive list of online judges that support Haskell submissions, with the available compiler versions at the time of writing. * CSES ([GHC 8.10.4](https://cses.fi/howto/)) * Codeforces (GHC 8.10.1) _{^{(Not documented, the version is seen on the Submit page)}} * AtCoder ([GHC 8.8.3](https://atcoder.jp/contests/language-test-202001)) * Kattis ([GHC 8.6.5](https://open.kattis.com/help/haskell)) * Hackerrank ([GHC 8.6.5](https://support.hackerrank.com/hc/en-us/articles/1500002392722--Execution-Environment-and-Samples)) * CodeChef ([GHC 8.0.1](https://www.codechef.com/wiki/list-compilers)) * HackerEarth ([GHC 7.10.3](https://www.hackerearth.com/docs/wiki/developers/judge/)) Most judges offer only the [Haskell Heirarchical Libraries](https://downloads.haskell.org/~ghc/latest/docs/html/libraries/), some have additional libraries installed. See the respective links for details. ## See also Other resources for competitive programming in Haskell - [Brent Yorgey's blog](https://byorgey.wordpress.com/) ## License MIT. The license text need not be included for competitive programming.

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：