Со времени выхода книги Криса Окасаки «Чисто функциональные структуры данных» 1998 года я не видел слишком много новых интересных чисто функциональных структур данных; Я могу назвать только несколько: IntMap (также изобретен Окасаки в 1998 году, но не представлен в этой книге) Пальцевые деревья (и...
Этот вопрос вдохновлен другим вопросом о том, что нового в ПФДС с момента публикации книги Окасаки в 1998 году . Я начну с двух вопросов, которые у меня есть: Существует ли чисто функциональная структура данных набора, которая приближается к скорости хеш-таблиц? Попытки еще не там. Существуют ли...
Я хотел бы понять Applicativeс точки зрения теории категорий. Документация для Applicativeговорит , что это сильный слабый моноидальный функтор . Во-первых, на странице Википедии о моноидальных функторах говорится, что моноидальный функтор слабый или сильный . Так что мне кажется, что либо один из...
Большинство известных алгоритмов первого порядка в том смысле, что их ввод и вывод являются «простыми» данными. Некоторые из них являются вторым порядком тривиальным способом, например, сортировка, хеш-таблицы или функции map и fold: они параметризуются функцией, но на самом деле они не делают с...
Существуют ли (функциональные?) Языки программирования, в которых все функции имеют каноническую форму? То есть любые две функции, которые возвращают одинаковые значения для всего набора ввода, представляются одинаково, например, если f (x) вернул x + 1, а g (x) вернул x + 2, то f (f (x )) и g (x)...
В настоящее время я читаю « Лямбда-исчисление и комбинаторы » Хиндли и Селдина. Я не эксперт, но всегда интересовался лямбда-исчислением из-за участия в функциональном программировании (начиная с Lisp и SICP, а теперь с R и Haskell). В « Binary лямбда - исчисления и комбинаторной логики» , Джон...
ACSL (Ansi C Specification Language) - это спецификация для кода C, снабженная специальными комментариями, которая позволяет формально проверять код C. Я не рассматривал это, но я полагаю, что формальные методы, используемые в верификаторах ACSL , будут похожи на Hoare Logic. Однако для чисто...
Я только что понял, что я предполагаю, что ответ на мой вопрос - «да», но у меня нет веской причины. Я предполагаю, что, возможно, существует сборщик мусора, который доказуемо вводит только замедление в худшем случае. Есть ли конкретная ссылка, которую я могу привести? В моем случае я работаю над...
Я разрабатываю простой статически типизированный функциональный язык программирования для обучения. Похоже, что система типов, которую я реализовал до сих пор, могла (с небольшой дополнительной работой) включать типы пересечений и объединений, например, вы могли бы иметь: <Union String...
Каковы ограничения общего функционального программирования? Он не является полным по Тьюрингу, но все еще поддерживает большое количество возможных программ. Существуют ли важные конструкции, которые вы могли бы написать на языке Тьюринга, но не на полном функциональном языке? И правильно ли...
Пусть будет CCC . Пусть быть бифунктором продукта на . Так как Cat - это CCC, мы можем карри (\ times) :ССC( × )(×)(\times)ССC( × )(×)(\times) с у г г у( × ) : C→ ( C⇒C)curry(×):C→(C⇒C)curry (\times) : C \rightarrow(C \Rightarrow C) curry(×)A=λB.A×Bcurry(×)A=λB.A×Bcurry (\times) A = \lambda B. A...
Я читаю «Реализацию языков функционального программирования» Саймона Пейтона Джонса, и есть одно утверждение, которое меня немного удивило (на странице 39): В гораздо большей степени, чем в случае императивных языков, функциональные языки в значительной степени являются синтаксическими вариациями...
Я пытался прочитать « Жемчужины разработки функциональных алгоритмов », а затем « Алгебру программирования », и есть очевидное соответствие между рекурсивно (и полиномиально) определенными типами данных и комбинаторными объектами, имеющими то же самое рекурсивное определение и впоследствии ведущим...
После небольшой работы с 2-3 пальцами я был впечатлен их скоростью в большинстве операций. Однако одна проблема, с которой я столкнулся, - это большие накладные расходы, связанные с первоначальным созданием большого дерева пальцев. Поскольку построение определяется как последовательность операций...
С чисто абстрактной математической / вычислительной точки зрения (как) можно даже узнать или рассуждать о таких проблемах, как 3-SAT, сумма подмножества, коммивояжер и т. Д.,? Сможем ли мы хоть как-то осмыслить их с функциональной точки зрения? Будет ли это вообще возможно? Я размышлял над этим...
Мне нужно хранить наборы элементов типа а. Тип a частично упорядочен, поэтому сравнение и может вернуть меньшее, большее, равное или несопоставимое.2a1a1a_1a2a2a_2 Одна проблема с хеш-таблицами состоит в том, что два равных элемента могут быть представлены по-разному, и у меня нет доступа к...
Я читал главу в LYAH, которая не имела для меня никакого смысла. Я понимаю, что молнии могут произвольно пересекать древовидную структуру, но мне нужно кое-что прояснить. Кроме того, могут ли молнии быть обобщены на любую структуру...
Я изучаю идею написания СУБД чисто функциональным способом. Традиционной структурой данных, используемой для индексации, является B-Tree. Я хотел бы знать какой-то чисто функциональный эквивалент B-Tree, который был бы оптимизирован для минимизации доступа к диску....
Рассмотрим простой односвязный список в чисто функциональной обстановке. Его похвалы пели с горных вершин и будут продолжать петь. Здесь я расскажу об одной из его сильных сторон и о том, как ее можно распространить на более широкий класс чисто функциональных последовательностей, основанных на...
Функциональный язык можно рассматривать как категорию, где его объектами являются типы и функции морфизмов между ними. Как классы типов вписываются в эту модель? Я предполагаю, что мы должны рассматривать только те реализации, которые удовлетворяют ограничению, которое имеет большинство классов...