Поэтому иногда мне нужно написать структуру данных, которую я не могу найти в Hackage, или то, что я нахожу, не проверено или недостаточно для того, чтобы я мог доверять, или это просто то, что я не хочу быть зависимым. Я читаю книгу Окасаки прямо сейчас, и это неплохо объясняет, как создавать асимптотически быстрые структуры данных.
Однако я работаю специально с GHC. Для моих приложений важны постоянные факторы. Использование памяти также для меня очень важно. Поэтому у меня есть вопросы конкретно о GHC.
В частности,
- Как максимизировать совместное использование узлов.
- Как уменьшить объем памяти памяти
- Как избежать утечек пространства из-за неправильной строгости/лени.
- Как получить GHC для создания плотных внутренних петель для важных разделов кода.
Я просмотрел различные места в Интернете, и у меня есть смутное представление о том, как работать с GHC, например, глядя на основной вывод, используя UNPACK
прагмы и т.п. Но я не уверен, что понимаю.
Итак, я открыла свою любимую библиотеку структур данных, контейнеры и посмотрел модуль Data.Sequence. Я не могу сказать, что я много понимаю, что они делают, чтобы быстро сделать Seq.
Первое, что бросается в глаза, - это определение FingerTree a
. Я предполагаю, что только я не знаком с пальцами. Второе, что бросается в глаза, - это все прагмы SPECIALIZE
. Я понятия не имею, что здесь происходит, и мне очень любопытно, поскольку они усеяны по всему коду.
У многих функций также есть прагма INLINE
, связанная с ними. Я могу догадаться, что это значит, но как я могу судить о том, когда функции INLINE
?
Вещи действительно интересны вокруг линии ~ 475, секции, которая называется "Аппликационная конструкция". Они определяют оболочку newtype для представления монады Identity, они пишут свою собственную копию монады строгого состояния, и у них есть функция, определенная под названием applicativeTree
, которая, по-видимому, специализируется на Monad Identity, и это увеличивает совместное использование вывода функция. Я понятия не имею, что здесь происходит. Какое колдовство используется для увеличения обмена?
В любом случае, я не уверен, что многое можно узнать из Data.Sequence. Существуют ли другие "программные программы", которые я могу прочитать, чтобы получить мудрость? Мне очень хотелось бы знать, как сушить мои структуры данных, когда мне действительно нужно, чтобы они пошли быстрее. В частности, речь идет о создании структур данных, облегчающих слияние, и о том, как писать хорошие правила слияния.