← All posts tagged Haskell

Macil
? Haskell XML lexing Есть одна ебанутая спецификация, которая требует отдельные 0x0D заменять на 0x0A, а пары 0x0D 0x0A заменять на 0x0A. И пусть меня закидают ссаными тряпками, я вообще не вкуриваю как это сделать.
Не, ясен пень, нужно сварганить простейший конечный автомат (вернее, трансдюсер), который будет разбивать поступающие на вход байтстринги на более мелкие байтстринги (ленивые, без копирования). А вот как это сделать в реале?
Перейти на стринги, перейти на текст? Важна даже не столько вычислительная сложность. Важно чтобы реализация как можно меньше сношала сборщик мусора.
Обойти — не вариант. Во-первых, такое поведение — MUST. Во-вторых, без реализации такого поведения к чертям полетит вся кошер^W каноничность.
Macil
Haskell types Камрады, а вам не кажется странным что в Хаскеле мы можем невозбранно создавать «анонимные» типы-произведения, но не можем создавать «анонимные» типы-суммы? Более формально,
:k (Int, Char, String)
(Int, Char, String) :: *
:k '[Int, Char, String]
'[Int, Char, String] :: [*]
Кажется, что проблема всего лишь в отсутствии синтаксического сахара. Или я не прав?
Macil
Haskell tree Осилил extension-кодирование произвольного дерева в бинарное. Запилил по этому поводу гист gist.github.com
Достоинства:
1. Бинарное дерево. А значит, целый арсенал отработаных методов (хранение, сравнение и т.п.).
2. Узлы в исходном и закодированном дереве при обходе слева-направо обходятся в том же порядке.
3. У внутренних узлов всегда два потомка (в отличие от FCNS).
4. Каждому поддереву исходного дерева соответствует поддерево закодированного. В случае FCNS, например, это не так, там поддереву закодированного соответствует хедж исходного.
5. Можно разбирать как снизу-вверх с помощью stepwise automata (аццкая штука, обладающая магическими свойствами), так и сверху-вниз с помощью обычного рекурсивного спуска (ака монадический комбинаторный парсер). В любом случае из за свойства (4) разборщик будет хорошо комбинироваться.
6. Зиппер для бинарного дерева прост и понятен.

Недостатки:
1. Это совершенно неинтуитивно. Первая мысль при взгляде на закодированное дерево — «что за хуйня». Гист пытается немного помочь в освоении.
2. Дерево будет несбалансированным. Совсем. Справдливости ради стоит заметить что в случае FCNS оно ещё более несбалансировано.
3. Увы, но исходное дерево нельзя кодировать сверху-вниз.
4. Более того, кодировать можно только имея уже существующее дерево в другой форме. Например, ХМЛ напрямую закодировать нельзя, в отличие от FCNS.
5. Обходить дерево имеет смысл только слева-направо.
6. Для исходного дерева требуется использовать структуру, поддерживающую эффективную операцию взятия последнего элемента.

ЗЫ: Кому бы в голову это не пришло... Но автора, однозначно, конкретно припёрло.
Macil
Haskell tree Камрады, а почему все повсеместно используют реализацию хедж-деревьев в виде
data Tree a = Node a | Tree a [Tree a]
Если уж и юзать хедж-деревья, то тогда уж вместо списка юзать finger tree (сиречь Data.Seq). Тут вам и вставка и слева и справа за константное время и разбивка/склейка за логарифмическое... И ещё какие-то плюшки... Странно всё это...
Macil
Haskell fpcomplete.com ФП-Комплиты открыли ide-backend — враппер GHC API для анализа/компиляции хаскельных сырцов. Просто пиздец какой-то!
Macil
Haskell ghc UEFI Интересно, а реально ли портировать GHC на UEFI окружение, чтобы можно было писать ФП-буткиты^W красивые загрузчики с блекджеком и шлюхами?
С чего следует начать? Наверно с запиливания возможности генерить бинарники диалекта PE+, используемого в UEFI? Разделяемых библиотек в UEFI нет, всё динамически через COM^W интерфейс «протоколов», так что хаскелистам не привыкать. Хотя, первым делом придётся портировать integer-gmp на UEFI...
Может быть кто-то из таких же извращенцев уже данным вопросом занимается?
Macil
Haskell Ну и чё? Проапгрейдил до 7.10.1, поставил стандартный (кабал-инстал, алекс, хэппи) и былокодерский (линзы, хмл-кондуит, скотти) наборы... И хоть бы одна ошибочка во время сборки... А это, на минуточку, 65 пакетов. Ску-у-у-у-чно...
Macil
? Haskell zipper А прикрутить к зипперу continuation чтобы запилить Applicative, Alternative и Monad интерфейсы для перемещения по дереву, это как, нормально или всё-таки перебор?
Macil
ненависть Haskell zipper Бля, какая тварь «додумалась» представлять зиппер для бинарного дерева как type Zipper = (BinTree a, [Context a])? Расстрелять нахуй из рекативных говномётов. Два раза!
Зиппер это исключительно type Zipper = (BinTree a, Context a), где data Context a = Top | L a (BinTree a) (Context a) | R a (BinTree a) (Context a) без сраных паттерн матчнигов по спискам!
Macil
Haskell XML Если закодировать XML-дерево в бинарное с помощью техники FCNS, то получившийся результат прекрасно ложится на обычный комбинаторный парсер: комбинатор get (получить следующий токен) разбивается на два: fc (получить следующего «ребенка») и ns (получить следующего «брата»), т.е. пойти влево по дереву или пойти вправо. Понятно дело, что в реальном мире всё несколько сложнее: нужно парсить атрибуты, не давать парсить надмножество XML, парсит не well-formed документы, стримить документы и т.д. Но все базовые свойтва остаются.
Умные люди вообще считают что если закодировать XML бинарным деревом, то задачи валидации/навигации сведутся к SAT, и выдвигают туеву хучу вариантов реализации.
Есть и другая техника кодирования: карринг (или как её называют в TATA, extension encoding). Но почему-то я не нашел ни одной статьи по этому поводу.