declarative
Dec. 25th, 2012 01:34 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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
Есть последовательность байтов (фиксированный массив/список или потенциально бесконечный поток - на ваш выбор), нужно их сжать 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
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2012-12-26 04:50 am (UTC)Программа при этом, конечно же, одна и та же.
То есть вы можете рассуждать о map f как об утверждении "аргумент - некоторый список, результат - список того же размера, элементы которого являются результатом применения f к элементам аргумента, причем результат применения f к i-тому элементу аргумента имеет i-тую позицию". А можете как о последовательности шагов: "разделить входной список на голову и хвост, применить f к голове, map f к хвосту, вернуть список, полученный из новых головы и хвоста".
Аналогично в вашим rle:
decodeBytes bytes = concat $ map decodeByte bytes
where
decodeByte x =
| x <= 192 = [x]
| x > 192 = replicate (x-192) x
можно воспринимать этот код как описание свойств decode, а можно - как указание вычислителю на действия, которые он должен выполнить.
no subject
Date: 2012-12-26 05:33 am (UTC)no subject
Date: 2012-12-26 08:24 am (UTC)Надо как-то так, понятное дело:
decodeBytes bytes = concat $ map decodeByte bytes
where
decodeByte x =
| followThe x 192 = []
| x <= 192 = [x]
| x > 192 = replicate (x-192) x
Здесь как раз уже будет лучше видно суть декларативного подхода - вместо того, чтобы декомпозировать функцию на _последовательность шагов_ мы декомпозируем ее описание в _набор свойств_, в данном случае "х следует за байтом > 192" - это как раз свойство конкретного байта.
В конечном итоге с императивной точки зрения мы имеем шаги вычисления и стратегии вычислений, с точки зрения декларативного подхода - свойства и комбинаторы свойств. Естественно, любой шаг/стратегия выражается через свойства/комбинаторы и наоборот - это как раз и гарантирует, что для любой программы существуют сразу оба способа reasoning'а. Однако, в зависимости от конкретной программы тот или иной способ может быть более или менее удобен (субъективно, конечно). Ну и для конкретной задачи может быть более или менее удобен тот или иной способ декомпозиции. Тогда мы и говорим, что "язык императивен/декларативен", "задача больше подходит для императивного/декларативного подхода".
no subject
Date: 2012-12-26 08:46 am (UTC)и
map decodeByte bytes
по-прежнему выглядят как баг на баге, ну да неважно.
На всякий случай: decodeBytes [195, 1] должен возвращать [1,1,1].
no subject
Date: 2012-12-26 06:25 am (UTC)Соответственно, в этом контексте _важно_, как смотреть на проблему.
no subject
Date: 2012-12-26 08:31 am (UTC)По-моему одни задачи удобнее решаются императивно, а другие - декларативно. В вашем же случае выходит - как задачу урешать удобно, так декларативно и есть, даже если мы решаем ее на ассемблере.
no subject
Date: 2013-02-14 01:59 pm (UTC)>> В вашем же случае выходит - как задачу урешать удобно, так декларативно и есть, даже если мы решаем ее на ассемблере.
1) В моём случае так не выходит.
2) Прошу отметить, что расстояние от написанного кода до работающей системы - иногда более года. Если Вы этого намёка не понимаете, то Вам сложно чем-то помочь.