Есть индуктивный тип данных, примерно такое
data InType = In1 InType | In2 InType InType | InL [InType] | In0
и тип, полученный из него разложением на составляющие:
type Key = String
data OutType = Out1 Key | Out2 Key Key | OutL [Key] | Out0

и таких пар несколько (штуки 4). Везде структура сторого типа в точности повторяет структуру первого, за исключением рекурсивности. Как бы сэкономить и не писать такие повторения руками? И вообще, что тут можно сэкономить?
Есть соблазн в каждое рекурсивное вхождение воткнуть Either InType Key, но это перегрузит доступ к типу сборками-разборками Either. И ваще как-то некрасиво.

Первый номер журнала "Практика функционального программирования"

Как это обычно говорится? Срочно выводим в топ!

Мнение: автору статьи о моноидах - респект, статью о состоянии потестю на явщиках. Перевод The Gentle Introduction - это круто, моя первая книжка про Haskell.
Если найду время - попробую помедитировать над адептовскими шашками.

Можно ли с помощью кабалы, а именно, build-type: Simple, собрать DLL? С помощью build-type: Make , ясное дело, её собрать можно, но тогда непонятно, зачем, собственно, нужна кабала. Да и забыл я, как мэйкфайлы пишут, слишком мало практики было.

( подробности )</></></></></></></></></></></></>

Если я правильно понимаю ситуацию, то ленивое выражение вычислется так:
Выполнятор (RTS или STGM или как оно правильно называется) берёт отложенное вычисление (которое представляет из себя вершину в графе AST) и пытается его форсировать. При этом он натыкается либо на отложенное подвыражение, либо на вызов функции из FFI либо Prelude. В первом случае ситуация повторяется. Во втором случае вызывается нативный код. Если время выполнения каждого нативного вызова предсказуемо, то получается, что выполнятор получает управление через предсказуемые промежутки времени. И может перед каждым шагом вычисления отложенных выражений переключать контекст.

Как бы теперь это к работе приспособить. Нужен легковесный ленивый параллельный язычок для тупых процессоров. И компромиссная библиотека: чем мельче будут раздроблены нативные вызовы, тем больше оверхед, но тем большее разрешение по времени мы получим для нашей многозадачности. А поверх этого надо накрутить какие-нибудь "контракты" с железом - чтобы знать, когда к каким событиям мы должны успеть. Смешение парадигм, однако.
Альтернатива - параллельные сишные программисты, которые умеют точно оценивать время работы своего кода.
Другая альтернатива - брать процессор помощней и надеяться, что всё везде успеет.

(#) :: obj -> (obj -> a) -> a

Reverse application, i.e. x # f = f x. Useful for an object oriented style of programming.
(frame # frameSetTitle) "hi"

feed :: a -> (a -> b) -> b
Inverse application, i.e. feed x f = f x.

feed2 :: a -> b -> (a -> b -> c) -> c
Composed Inverse application, i.e. feed2 x y f = f x y.


Источник: wxHaskell

Там ещё есть в коде открытий чудных. Начиная с того, что wxcore у меня отказался собираться:
1. Оказывается, порты wxWidgets забывают ставить wx-config в пути. ln -s моё всё, возможно, есть более кошерный способ.
2. wx-core не подозревает, что на некоторых системах GNU make называется gmake.
3. ещё оно забывает сказать себе -I /usr/include (-I /usr/local/include) и потом безусмешно (вот это опечатка! оставлю) ищет GL/gl.h
Ну и, конечно, makefile там 2 штуки и генерятся они через configure. Это чтобы я не мог патч к 2 и 3 сделать и выслать аффтарам, однозначно.
Подозреваю, что к концу прочтения доков буду утверждать страстно, что хаскель - ОО язык. Как минимум, в той же мере, в которой COM - ОО-архитектура.

Каст CDouble->Double и обратно делает функция realToFrac.
Каст CInt->Int - fromIntegral.

Существует ли какая-нибудь библиотека "текстовых видгетов"? На такой, вероятно, сделан mc. Мне не верится, что его авторы курсорчик руками двигают и ставят красят буковки в правильные цвета
Хочется иметь listbox, который удобно вызывать из GHCi.

BTW: Пятиминутка беспомощности закончена. Оказалось, что если писать аналог hmatrix руками, на "императивном хаскеле", то он получается:
1. Без единой строки на C. (Если не считать хедера, в котором записаны прототипы функций из DLL)
2. Заметно короче.
3. Некоторые моменты, например, ловля ошибок, получаются не размазанными по разным местам и языкам, а в одной куче.
4. unsafePerformIO вылезают ближе к юзеру.
5. Скорость работы данной конструкции требует дополнительных измерений. "На глаз" совершенно неочевидно, что быстрей - двуязычный оригинал или одноязычный потомок.
6. Аналогично эффективность работы с памятью. Попытки понять с помощью GHCi, как GC собирает память, выделенную через malloc/free, оказались безуспешными.

1. Хочется сделать выполнитель отложенных заданий. Пока считаю, что задания выполняются быстро. В который можно класть задачу на выполнение, а он сам их будет запускать. С интерфейсом навроде:
schedule::TimeSpec-> IO () -> IO ()
2. Кажется логичным сделать его в 2 потоках: в одном ставятся задания, в другом - запускаются на выполнение.
3. Было бы логично усыплять второй поток до тех пор, пока задания ждут своего часа.
4. Если приходит новое задание, которому вставать на работу раньше всех остальных, то надо потоку переставлять будильник.
5. Как это правильно делать?
5.1. Предполагаю, что надо будить поток, потом усыплять его снова.
5.2. Если поток кладётся спать функцией threadDelay, то чем его будить?
5.3. Исключение в него кидать?
5.4. Или из первого потока во второй воткнуть какой-нибудь TChan? Чтоб он просыпался когда что-то приходит по каналу? Но тогда не получится воспользоваться Thread Delay в лоб.

Как известно, в Haskell есть "полная поддержка уникода". Настало время выяснить, что же это означает.
1. Внутренний тип данных Char представляет из себя unicode code point. То есть, в нём можно хранить любой символ, предусмотренный уникодом. Осталось выяснить, как его туда положить и вытащить обратно.
2. Парсер GHC устроен так, что работает в кодировке UTF-8. То есть, если в исходном коде задавать имена и строковые константы в UTF-8, GHC их поймёт правильно.
3. Для преобразования строк при вводе-выводе используются три библиотеки и Data.ByteString.
4. Data.ByteString - это, грубо говоря, строка из привычных нам восьмибитных байтов. Для неё перегружен ввод-вывод - определены стандартные функции: getLine, putStrLn, interact и т.д.
5. Консольный ввод-вывод делается байтами, а не уникодами, поэтому, при выводе String происходит либо обрезание кода символов до младших 8(7?) бит либо escaping(экранирование).
6. При выводе русских строк их надо преобразовать к нужной кодировке:
7. Библиотека Data.Encoding. Написана на хаскеле, кодировки представляют из себя абстрактный тип данных, принадлежащий классу Encoding и подключаются модулями, например, Data.Encoding.KOI8R. Также можно определять кодировку динамически, с помощью функции encodingFromString. Интерфейс очень простой:
encode::(Encoding enc)=>enc->String->ByteString
decode::(Encoding enc)=>enc->ByteString->String
Есть также функции для работы с lazy bytestring и recode.
-------
В Data.Encoding.KOI8R, видимо, ошибка: Data.ByteString.putStrLn $ encode KOI8R myStr where myStr="русская строка" выдаёт транслитерацию, (decode KOI8R (encode KOI8R myStr) == myStr) = False.
(decode CP1251 (encode CP1251 myStr) == myStr) = True, putStrLn $ encode CP1251 myStr печатает нормально. С UTF8 тоже всё хорошо, а кодировки IBM866 в библиотеке Data.Encoding нет.
При установленном LANG=ru_RU.KOI8-R функция getSystemEncoding возвращает KOI8R, а при LANG=ru_RU.CP1251 она, почему-то, возвращает ASCII. Проверять, в библотеке или в моей системе проблемы, было лень.
-------
Итог: интерфейс очень удобный, но KOI-8 не работает, а хочется, чтобы было всё.
8. Библиотека UTF8-string.
Интерфейс:
encodeString::String->String
decodeString::String->String
encode::String->[Word8]
decode::String->[Word8]
Поддерживает только одну кодировку, при использовании предлагает либо строгую типизацию (encode/decode), либо простоту(encodeString/decodeString) - уникоды и байты хранятся в одинаковом типе String.
-------
Она нам ещё пригодится.
9. Билиотека Codec.Text.IConv. Представляет из себя обёртку вокруг libiconv.
Интерфейс:
convert::EncodingName->EncodingName->ByteString->ByteString.
Есть также функции для проверки, что можно перекодировать, а что нельзя, и т.п.
Для использования необходимо как-то получить ByteString. Немного поразбиравшись, взял библиотеку UTF8-string. Итоговый код:
import Data.ByteString.Lazy
import Codec.Text.IConv
import Data.ByteString.Lazy.UTF8

myStr="это - строка по-русски "
main = Data.ByteString.Lazy.putStrLn $ convert "UTF-8" "KOI8-R" $ Data.ByteString.Lazy.UTF8.fromString myStr
Работает.
Достоинства: iconv знает много разнообразных кодировок. Недостатки: библиотека системно-зависимая - при отсутствии в libiconv необходимой кодировки вылетает исключение. Что и было продемонстрировано по просьбе преобразовать из "UTF8" в "KOI8-R". а у автора библиотеки (irc://irc.freenode.net:6667#haskell:dcoutts) система знала эту кодировку под обоими именами: "UTF8" и "UTF-8".

Возможно, в ближайшем будущем буду пробовать получать русские буквы через HTTP.

ОБН: Автор библиотеки Data.Encoding ответил, что про баг с декодированием КОИ-8 он знает и в darcs он исправлен, сейчас идёт большой редизайн, и следующая версия библиотеки будет пуще прежнего.

Вчера с 20.00 МСК до 25.00 МСК.
7 задач, одна отправленная, 0 решённых.
Радует то, что получив Time Limit Exceeded на хаскеле, успел доделать решение на асме. Не радует то, что результат аналогичный. Оставалось несколько менее часа, решил сдаться. Также не радует то, что непонятно: нужно знание какого-то сакрального алгоритма или можно уложить во время тюнингом структур данных.
ОБН: оказывается, у меня решение не только тормозное, но ещё и неправильное. aleksey подсказал, как делать транзитивную редукцию графа за O(VE).
Моё решение должно было работать за O(E²). Отсюда получаем побочный результат: OCAML медленней асма в моём исполнении (примерно GCC или чуть лучше) менее, чем в E/V = 10 раз.

Как ездить на коньках задом? На горных лыжах просто - движения те же, как и передом, только перевёрнутые. А на коньках не получается отталкиваться - вместо скольжения выходят шаги.

Хочу к приоритетной очереди прикрутить persistence, чтобы сделать beam stack search. Приоритетная очередь готовая есть в двух вариантах - стандартный Data.Map и Data.Edison.Assoc (причём, в Эдисоне есть и стандартный Data.Map с прикрученным к нему другим интерфейсом). Beam Stack делается так: в определённый момент, когда очередь сжирает очень уж много памяти, от неё отламывается наименее полезная часть и кидается (например, на диск), а потом, в случае надобности, последний сохранённый кусок подкачивается обратно. И Data.Map и большинство реализаций Эдисона внутри представляют из себя хорошо сбалансированное дерево, его делить на части очень просто - отламывается от вершины правая ветка, получается примерно половина дерева, сложность операции O(1). Всё хорошо и замечательно, но ни Data.Map ни Эдисон не показывают наружу конструкторы своего дерева. Как поступить правильно? Как поступают серьёзные промышленные программисты? Править локально установленный экземпляр Data.Map? Копипастить код в свой файл? Или не маяться х заниматься ерундой - даже если операция "разлом дерева" будет O(n), сохранение куска на диск будет всё равно существенно дольше? Кстати, где-то thesz выкладывал руководство по правильному программированию, там была очень интересная табличка про скорость различных памятей. Я таки потерял его. :(

ОБН: Data.Map в чистом виде ещё и не подходит. Там предполагается, что все ключи различны. Либо надо их солить, либо брать другую реализацию. Похоже, придётся самому руками делать балансирующиеся деревья. :(

А ещё сегодня весь день мазила падает, видать, к осени, пишу через konqueror. Самое смешное, что раньше на некоторых из нехороших сайтов падал именно Konqueror.

( Проект доклада )
Получается явно не на 5 минут, а скорее на час.
9. Если что надо выкинуть или добавить - предлагайте
10. Чем делают слайды в PDF?
( реализация )

Пытаюсь нарисовать замену классу Num для, скажем, векторов, и что-то не понимаю. Имеем:
(.+)::v->v->v
(.*)::s->v->v
и т.п.
Получается, что (+) и (*) должны принадлежать разным классам, где первый класс - однопараметрический, а второй - двухпараметрический? Но тогда нельзя из второго класса вывести instance для первого (ну мало ли для каких извращений это мне может понадобиться :) ) ?

Тестовые ситуации, на которой я проверяю разные варианты энтого класса:
1. скаляр - тоже вектор, только маленький
instance Fractional s=>Vec s s where
x .+ y = x + y
x .* y = x * y

2. Вектор можно представить спискообразным типом
class Listable v s where
toList::v->[s]
fromList::[s]->v
instance (Listable v s)=>Vec v s where
(.*) s v = fromList $ map (s*) $ toList v
а с (+) у меня такое не выходит, потому что у двухпараметрического класса в типах всех функций должны упоминаться оба параметра.

BTW: если кто-то подскажет красивое начертание для векторных операторов, буду весьма благодарен. Взятые по умолчанию (.+) и (.*) мне не нравятся своим внешним видом.

Воспоминания об ICFPC07. Предварительная версия.
1. Болтаем в ирке.
2. Звенит звонок. Все скачивают pdf, начинают читать.
3. Визуально оцениваю объём части, которая говорит о DNA -> RNA, решаю её пропустить - конкретику можно подчитать и попозже, а моск нужно экономить. Рядом Gvennet читает DNA -> RNA. Читаю вместо этого RNA -> картинко и мельком заглядываю в ту часть, которая о производительности.
4. Первое собрание. Делим задачи. Я не решаюсь взять себе и Gvennet лакомые кусочки. Получаю задачу "разобраться с DNA". Сажусь читать пропущенную часть, чтоб понять, что такое DNA.
5. Пытаемся с Gvennet решать примеры по редукции DNA. Почему-то без знания правильного ответа не получается. Становится неясно: мы тупим или просто ошибаемся в вычислениях. Если второе - то надо написать программку "DNA -> RNA" и решать ей, а не руками. Если первое - то программка такая выйдет с серьёзными ошибками. Но её уже пишет akamaus.
6. Смотрю глазами на endo.dna. Надоедает листать абракадбру. Теперь-то мы знаем, что надо было досмотреть до конца и было как минимум 4 человека, которых я мог заставить этим заниматься.
7. Пытаюсь понять, как это работает. Выясняется, что RNA - линейный код из граф. примитивов. Возникает мысль, что в DNA можно как-то "заархивировать последовательность рисования".
8. Появляется идея написать примитивы для программирования на языке DNA. То есть, не писать руками нуклеотиды, а изобрести метаязык. муравьям-2004 превед
9. Возникает идея брутфорса - быстренько, пока ivant не доделал векторизацию, построить target image, а endo.dna - не использовать. Попробовать уложиться в lightning.
10. Быстренько в итоге потянуло на сутки с небольшим.
11. Беру target.pnm, Gvennet берёт target.png - считаем всякие синтетические свойства, чтоб понять, какие вещи самые дорогие при брутфорс-рисовании. Выясняется, что если каждой точке указывать свой цвет - то код не укладывается в условия. Операция смешения цвета - очень дорогая. Пишу функцию смешения цвета, ошибаюсь, фиксю её часа 4 , потом переключаюсь на что-то другое. ivant дарит мне готовый смеситель цвета. Раз в картинке уже сэкономили на задании цвета, то пытаюсь ещё сэкономить - сделать RLE-сжатие, наподобие PCX. Получаю огроменный файл. Отсылаю. Проверить, какую картинку он строить - никак. Выясняется, что средняя длина одноцветного отрезка - 2 точки, RLE тут не катит.
12. Туплю на тему "как ещё можно сжать и вообще улучшить это решение". Возвращается идея программирования на DNA, собираюсь заняться ей, когда закончится lightning.
12.5 lightning expires
13. Кто-то предлагает нарисовать двухцветную картинку. Сверху - самый частый синий, снизу - самый частый зелёный. Делаем её с Gvennet, отсылаем. Получается довольно фигово.
14. Делаем картинку из одного синего цвета. Она оказывается лучше всех предыдущих.
15. Считаю, что брутфорс исчерпал себя, надо заниматься серьёзными вещами. Поднимаю голову и осматриваюсь, вижу 2 задачи:
15.1 Запрограммировать на DNA векторную картинку, которую вот-вот получит ivant.
15.2 Более простое программирование на DNA - заархивировать RNA-код. Например, улучшить брутфорс.
16. Пытаюсь написать на DNA fix,if,while - что получится. Моск устал от адреналина и короткого сна, но я этого не замечаю и не понимаю, насколько медленней двигаются мысли.
17. Вечер убивается на комбинаторы. Подключается lome0, в результате часть умственных ресурсов уходит на то, чтоб мне понять его решение, а ему моё. Gvennet, кажется, выдохлась, а у меня моск занят, руководить ей не могу.
18. Утром пропадают akamaus и vsb. Оказывается, они где-то нашли 28-символьный префикс и отослали его. Мне хочется посмотреть как он устроен, подумать, но взять его неоткуда.
19. Остаётся копать комбинаторы, хотя подсознание начинает понимать, что я, скорее всего, не успею переключиться на задачу "применить комбинаторы", а объяснить их кому-то ещё точно не хватит времени.
16.5 В процессе изобретения комбинаторов очень быстро придумывается тупой алгоритм сжатия RNA. К сожалению, он жмёт очень слабо, зато абсолютно любую RNA. Независимо от меня lome0 тоже его изобретает и сразу прикручивает к нему Хаффмана.
16.6 А хочется жать сильно, самый первый брутфорс из-за длины набрал много штрафных очков.
16.7 И только потом я понимаю, что в брутфорсных картинках (кроме чисто синей) могли быть какие-нибудь грубые ошибки. Их так и не проверили на DNA -> RNA -> PNM.

20. Заметил рассинхронизацию: как только у меня заканчивается мысль и наступает время пожрать, почему-то происходит собрание и меня загружают другими мыслями. Пока мысль работает, отвлекаться на жратву не хочется. Gvennet, кажется, вообще ничего не ест.

Участвовал в ICFPC'06.
Результаты: стратегия - чистый минус.
Владение haskell ~ 0.1 Не умею я рекурсивные программы писать!
Знание стандартных библиотек ~ 0.
Программирование (скорость) ~ 0.25
Эмоциональная стойкость - в минусе.
Восприятие английского текста ~ 0.4
Место: во второй сотне.
Мораль: если этот год по сложности принципиально не отличается от остальных - участвовать можно. Даже в одиночку.

Забавное стратегическое наблюдение (по ММБ, ПМБ, ICFPC): Если заранее присоединиться к (сильной) команде - возможно, придётся участвовать в одиночку, возможно, придётся сойти с дистанции. А если готовиться к одиночному участию / оставить подбор команды на самотёк - с хорошей вероятностью соберётся неплохая команда, либо непосредственно перед стартом, либо уже в процессе.

( Read more... )

Определения:
class Arrow a where
arr:: (b->c) -> a b c -- загоняет вычисление в стрелку
(>>>):: a b c -> a c d -> a b d -- стрелочная композиция
class Arrow a=> ArrowPlus a where
zeroArrow:: a b c
(+++):: a b c -> a b c -> a b c -- вторая операция над стрелками и её нуль
class Arrow a=> ArrowApply a where
app:: a (a b c,b) c -- аналог монадного >>= применяет стрелочное вычисление к стрелочному типу

Для каждой монады можно определить ArrowPlus и наоборот:
newtype Kleisli m a b = K (a -> m b)
instance Monad m => ArrowApply (Kleisly m) where
arr f = K (\b-> return f b)
K f >>> K g = K (\b -> f b >>= g)
app = K ( \(K f,x) -> f x)

newtype ArrowApply a=> ArrowMonad a b = M (a () b)
instance ArrowApply a=> Monad (ArrowMonad a) where
return x = M (\z-> x)
M m >>= f = M (m >>> arr (\x-> let M h = f x in (h,undefined)) >>> app)


Из такой конструкции получаем 3 вывода:
1. Стрелки, на которых определено apply - равноценны монадам.
2. Если делаем на этом, например, парсеры. Если парсеры, например, детерминистские. То. Парсер состоит из двух частей:
type Parser a = (StaticParser a, DynamicParser a)
type DynamicParser a = (String->[(a,String)])
StaticParser содержит в себе детерминизм (всякие там таблицы предпросмотра и т.п.) DynamicParser - сама разбирающая функция. StaticParser вычислим статически, то есть, при сборке из элементарных парсеров и комбинаторов. DynamicParser срабатывает, когда готовому парсеру скармливают аргумент.
На монадах прямо этого сделать нельзя. Потому что комбинатор bind (>>=) имеет первым аргументом монаду ma, вторым - функцию, которая строит монаду a-> m b. То есть, монада m b строится динамически. То есть, статическую информацию она содержать не может.
Стрелочный комбинатор >>> ,напротив, вторым аргументом имеет стрелку. То есть, в эту стрелку можно вложить статическую часть.
3. Программа, составленная из стрелок с использованием только комбинаторов, в явном виде прописывает information flow: если выход какой-то стрелки a направляется на вход стрелок b и c, то нужно ставить комбинатор, который включает b и c параллельно. То есть, по коду легко проследить, какое значение до какого места доживает, и когда оно может быть собрано. Memory Footprint становится более-менее управляемым при использовании стрелочных комбинаторов.

Вывод 4: существующий стрелочный синтаксис - неудовлетворительный: несложная комбинация из нескольких стрелок соединённых параллеьно и последовательно содержит туеву хучу скобок и плохочитаема. Поскольку стрелочный синтаксис, в общем-то, описывает dataflow при вычислениях - он должен быть как минимум двухмерным (будет по читаемости близко к блоксхемам).