declarative

[thedeemon]

Периодически встречаю словосочетание "декларативное программирование", которое противопоставляют императивному, сопровождая формулой "описывается, что должно быть получено, а не как оно должно быть получено". Известный пример декларативного языка - SQL. Еще к декларативщине частенько относят хаскель и другие ФЯ, но вот с ними проблема: сколько кода я на них видел, (практически) везде было явное описание процесса вычисления, т.е. код был все же императивным по сути (создать список такой-то, свернуть его так-то, построить дерево такое-то и т.д. - это все про "как"). Вопрос к залу: покажите максимально декларативное решение (на любом языке, в том числе еще не существующем и чисто гипотетическом) следующей задачи.

Есть последовательность байтов (фиксированный массив/список или потенциально бесконечный поток - на ваш выбор), нужно их сжать RLE методом по мотивам формата PCX: в выходном потоке байт Х <= 192 обозначает сам себя, а байт Х > 192 означает Х-192 повторений следующего за ним байта. Т.е. последовательность
1, 1, 2, 3, 2, 2, 2, 200, 0, 200, 200, 200, 200
должна превращаться в
194, 1, 2, 3, 195, 2, 193, 200, 0, 196, 200

Comments

[maxim.livejournal.com]

Зачем писать компилятор, все написано :) Это задача двух симметричных функций duplicate и dropwhile.
Что бы не делать монадо и не разрывать результат дропвайл и у меня и две, одна считатет счетчик,
вторая оригинальная эрланговская список.

-module(erle).
-compile(export_all).

drle([]) -> []; % decode rle
drle([H|L]) when H < 192 -> [H,drle(L)];
drle([H,X|L]) -> [lists:duplicate(H-192,X),drle(L)].

cnt(A,[],C) -> C; % helper lema
cnt(A,[H|L],C) when H /= A -> C;
cnt(A,[H|L],C) when H == A -> cnt(A,L,C+1).

erle([]) -> []; % encode
erle([H,H|L]) -> [192+cnt(H,[H,H|L],0),H|erle(lists:dropwhile(fun(X) -> X == H end,L))];
erle([H,X|L]) when H > 192 -> [193,H|erle(lists:dropwhile(fun(X) -> X == H end,[X|L]))];
erle([H,X|L]) -> [H|erle(lists:dropwhile(fun(X) -> X == H end,[X|L]))].

main() ->
Ori = [1, 1, 2, 3, 2, 2, 2, 200, 0, 200, 200, 200, 200],
Enc = [194, 1, 2, 3, 195, 2, 193, 200, 0, 196, 200],
io:format("~p",[lists:flatten(erle(Ori))]),
io:format("~p",[lists:flatten(drle(Enc))]).

Я прошел собеседование ? :)

[thedeemon.livejournal.com]

Тот же баг, что и у многих других - не ограничиваются длины повторов.

Но в целом идея ясна.

[maxim.livejournal.com]

Блядь, точно. Непрошел :)

[maxim.livejournal.com]

Но пофиксать несложно ничего не измениться.

[thedeemon.livejournal.com]

Совершенно верно. :)