Обработка элемента множества в контексте "соседей"

[metaclass]

Вот тут http://levgem.livejournal.com/420910.html задают вопрос, который меня тоже сильно интересует - есть ли такая высокоуровневая операция, которая бы позволила абстрагировать обработку элемента (упорядоченного) множества в контексте взаимодействия этого элемента с его соседями.
Вроде antilamer что-то похожее писал про комонады, но мне без конкретной задачи сложно осознать, как это использовать.
Вот например map, filter, fold - я их понял от входа, потому что очевидная аналогия с SQL запросами - select, where, group by (и прочие агрегаты).
У обработки в контексте понятная мне аналогия - это, например, window functions в SQL, скользящее среднее, интеграторы-дифференциаторы и прочие фильтры-свертки в DSP, но вот их я внятным образом с функциональщиной сопоставить не могу.

PS: клеточные автоматы и комонады: http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html Клеточный автомат тоже подвид фильтра поверх скользящего окна.
И функции поверх потоков: http://blog.sigfpe.com/2006/06/monads-kleisli-arrows-comonads-and.html

Comments

[antilamer.livejournal.com]

Это стопудоф комонады. Но вот что я тебе скажу: я понимаю, как все эти вещи моделируются с их помощью, но я пока не понимаю, есть ли смысл использовать для этой цели именно комонады. Можешь попробовать - думаю, с практической задачей в руках ты зайдешь в исследовании дальше, чем я.

[lomeo.livejournal.com]

Расскажи.

[antilamer.livejournal.com]

Дык http://antilamer.livejournal.com/444472.html же

[lomeo.livejournal.com]

Какая из них? (Мы же про задачу levgem?)

[antilamer.livejournal.com]

Я про "window functions в SQL, скользящее среднее, интеграторы-дифференциаторы и прочие фильтры-свертки в DSP". Как это на задачу levgem ложится, не знаю :)

[metaclass.livejournal.com]

Да так же и ложится - из элемента и его соседей делается "элемент с указателями на соседей". Это тот же фильтр.

[lomeo.livejournal.com]

Для его задачи и зиппера хватает ;-)

Только причём тут комонады? Ведь когда говорят "монада", "комонада", имеют в виду соответствующие функции, а не структуры данных, верно? Т.е. монада список — это concatMap, удобный liftM2 и т.д.

Тут-то вроде ничего подобного не нужно.

[lomeo.livejournal.com]

А, ты про зиппер, наверное. В общем, я не о том, проехали.

[palm-mute.livejournal.com]

интернеты утверждают, что для скользящих окон полезны зигоморфизмы :)
http://www.iis.sinica.edu.tw/~scm/2010/functional-pearl-maximally-dense-segments/

[nivanych.livejournal.com]

По большому счёту, эти все типы рекурсии не нужны, это лишние сучщности.
Упрощают они очень немного, а запоминать всё такое мне лично неохота.
Я уж и названия их всех позабыл, кроме ката-ана-морфизмов.

[jdevelop.livejournal.com]

я чота не понимаю, в чем весь сыр-бор

берем State - и поехали

[lomeo.livejournal.com]

Это вообще универсальный ответ.

[nivanych.livejournal.com]

Основная идея подобного коалгебраического-комонадического в генерации чего-то-там.
В случае клеточных автоматов, это вычисление следующего состояния из предыдущего.
Любой процесс, даже Тьюринг-полное, можешь разложить на шаги.
Только в Тьюринг-полном должно стоять условие навроде "если это не ноль, продолжать".

Каждый шаг — это стрелка коалгебры.
Например, конечный автомат — (In,S)→(Out,S)
Или в коалгебраическом варианте — S→(In→(Out,S))
S может быть и пачкой клеток или клетками, объединёнными в список.
Шаг работы какого-нибудь клеточного автомата может быть записан таким типом, только к состоянию S нужно будет добавить координаты "окна".
Ну и понятно, что понятие комонадЪ'а тесно связано с коалгебрами.

Далее, в контексте взаимодействия элемента с соседями — это ж такие схемы рекурсии бывают.
Структурная реукрсия, это кото-морфизм. То есть, это вычисление алгебры alg : F x → x для любого носителя x, исходя из начальной алгебры initalg : F in → in, то есть, свёртка initalg по конкретной алгебре alg.
В простейшем случае, x бывает чем-то примитивным типа числа, в более сложном случае, это может быть тупель из многих вспомогательных типов, например, списков.
Если в x есть список, то это означает, что ты будешь 'сворачивать' initalg'ебру по твоей алгебре, используя список в качеcтве состояния.
В списке можно, например, содержать N последних значений, связанных с твоей обработкой.
Таким образом, даже и автомат с мазазинной памятью (а значит, и синтаксический разбор) может быть записан в виде кото-морфизма.

А про SQL — ну так в поцгресе давно есть WITH RECURSIVE, и в оракелё подобное совсем давно есть ;-)

Не вполне уверен, полезно ли это чем-то, но решил оставить. Зря писал, что ли?