Brent Yorgey - Competitive Programming in Haskell
Вставка
- Опубліковано 8 лис 2022
- Special thanks to the Haskell Foundation for supporting the production of this video!
Haskell Love 2021 schedule: emamo.com/event/haskell-love
Haskell Love twitter: / _haskellove
Competitive programming is an exciting mind sport where competitors race to solve difficult programming tasks as quickly as possible, either individually or as part of a team. It requires sharp problem-solving skills, broad knowledge of algorithms and data structures, and (often) developing a good library of reusable code components ahead of time. Most serious competitive programmers use C++, but this is an arena where Haskell can shine: Haskell's strong type system helps prevent stupid mistakes made in the heat of the moment, and its capability for abstraction allows us to develop versatile libraries and solve problems using a minimum of boilerplate. In this talk, I will livecode a solution to a representative challenge, showing off techniques and libraries along the way.
I will also highlight some areas needing work. In some cases, in order to fit within the time limit imposed by the creators of a problem, it is necessary to write code that runs within a small constant multiple of the time taken by a C++ solution. This is possible but difficult; the name of the game is to create libraries of algorithms and data structures that are highly optimized internally but present a flexible and idiomatic interface suitable for use in a contest.
I hope that Haskellers of all skill levels will be able to take away something new, and that some will be convinced to take up a new hobby, or contribute some code! - Наука та технологія
Half of the screen is dedicated to a white background and the "Haskell Love conference" branding. Really? Who was the genius who decided that only one-third of the available space should be enough for the code section in a presentation about competitive programming?
I thought the factorial problem would check for huge enough numbers so people cheating with an arbitrary large integer data type would fail due to inefficiency. Note that:
H> (\k -> product [1..k] `mod` 10 :: Integer) [0..]
[1,1,2,6,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0..]
Esto on top lowz K