Как вы пишете структуры данных, которые максимально эффективны в GHC? [closed]

Закрыт . Этот вопрос должен быть более сфокусированным . В настоящее время он не принимает ответы.

Хотите улучшить этот вопрос? Обновите вопрос, чтобы он касался только одной проблемы, отредактировав это сообщение .

Закрыт 12 месяцев назад .

Иногда мне нужно написать структуру данных, которую я не могу найти на Hackage, или то, что я нахожу, не проверено или недостаточно качественно, чтобы я мог доверять, или это просто что-то, что я не хочу быть зависимым. Я читаю книгу Окасаки прямо сейчас, и она довольно хорошо объясняет, как проектировать асимптотически быстрые структуры данных.

Однако я работаю конкретно с GHC. Постоянные факторы имеют большое значение для моих приложений. Использование памяти также имеет большое значение для меня. Так что у меня есть вопросы конкретно о GHC.

В частности

Как максимизировать совместное использование узлов
Как уменьшить объем памяти
Как избежать утечки места из-за неправильной строгости / лени
Как получить GHC для создания плотных внутренних циклов для важных участков кода

Я просмотрел различные места в Интернете, и у меня смутное представление о том, как работать с GHC, например, глядя на ядро вывод с использованием прагм UNPACK и т.п. Но я не уверен, что понимаю.

Итак, я открыл свою любимую библиотеку структур данных, контейнеры и посмотрел на модуль Data.Sequence. Я не могу сказать, что понимаю многое из того, что они делают, чтобы сделать Seq быстрой.

Первое, что бросается в глаза, - это определение FingerTree a . Я полагаю, что это просто я незнаком с пальмовыми деревьями. Второе, что бросается в глаза, - это прагмы SPECIALIZE . Я понятия не имею, что здесь происходит, и мне очень любопытно, так как они разбросаны по всему коду.

Многие функции также имеют связанную с ними прагму INLINE . Я могу догадаться, что это значит, но как мне сделать вывод о том, когда использовать INLINE функции?

Все становится действительно интересным в строке ~ 475, разделе, озаглавленном «Аппликативная конструкция». Они определяют оболочку newtype для представления монады Identity, они пишут свою собственную копию монады строгого состояния, и у них есть определенная функция под названием ApplicativeTree , которая, по-видимому, специализирована для монады Identity, и это увеличивает совместное использование вывод функции. Понятия не имею, что здесь происходит. Какое колдовство используется для увеличения обмена?

В любом случае, я не уверен, что можно многому научиться у Data.Sequence. Могу ли я почитать другие «модельные программы», чтобы получить мудрость? Я действительно хотел бы знать, как улучшить свои структуры данных, когда мне действительно нужно, чтобы они работали быстрее. В частности, одна вещь - это написание структур данных, упрощающих слияние, и то, как писать хорошие правила слияния.

data-structures haskell

задан danharaj 21 June 2011 в 21:35

0 ответов

Другие вопросы по тегам:

data-structures haskell

Как вы пишете структуры данных, которые максимально эффективны в GHC? [closed]

0 ответов

Похожие вопросы: