2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Индуктивные функции на бесконечных последовательностях
Сообщение10.04.2021, 00:48 
В § 8 книги "Программирование для математиков" А.Г. Кушниренко и Г.В. Лебедева вводится понятие индуктивной функции на конечных последовательностях. Пусть $A$ есть алфавит и $A^*$ обозначает множество конечных слов в $A$. Функция $f\colon A^*\to Y$ называется индуктивной, если существует функция $g\colon Y\times A\to Y$, такая что $f(wa)=g(f(w),a)$ для любых $w\in A^*$ и $a\in A$. Если провести аналогию с Haskell, то это функция на списках, вычисляемая с помощью левой свертки, то есть foldl.

В книге доказывается, что для любой функции $f\colon A^*\to Y$, не обязательно индуктивной, существует единственное так называемое минимальное индуктивное расширение, то есть индуктивная функция $F\colon A^*\to Z$, такая что $f$ факторизуется через $F$, то есть $f=\pi\circ F$ для некоторой функции $\pi\colon Z\to Y$. Минимальность при этом означает, что $F$ факторизуется через любое другое индуктивное расширение $f$.

Мой вопрос: что можно сказать про класс функций, выражаемых с помощью правой свертки (foldr в Haskell) на бесконечных последовательностях $A^\omega$? То есть меня интересуют функции $f\colon A^\omega\to Y$, для которых существует $g\colon A\times Y\to Y$ и имеет место $f(aw)=g(a,f(w))$ для всех $a\in A$ и $w\in A^\omega$. В частности, $Y$ может совпадать с $A^\omega$. Насколько я понимаю, в Haskell foldl не работает на бесконечных списках, поэтому я спрашиваю про foldr. Есть ли альтернативное описание такого класса функций? Есть ли для них результат, аналогичный утверждению про минимальное индуктивное расширение?

 
 
 
 Re: Индуктивные функции на бесконечных последовательностях
Сообщение10.04.2021, 15:46 
3D Homer в сообщении #1513707 писал(а):
Если провести аналогию с Haskell, то это функция на списках, вычисляемая с помощью левой свертки, то есть foldl.
Кстати $f(w a)=g(f(w), a)$ это они зря сделали, потому что во всём мире языков программирования последовательности, когда они представляются связными списками, имеют натуральной правую свёртку, а не левую, и отщипывание отдельных элементов за $O(1)$ у них с левой, а не с правой стороны.

3D Homer в сообщении #1513707 писал(а):
Есть ли альтернативное описание такого класса функций? Есть ли для них результат, аналогичный утверждению про минимальное индуктивное расширение?
Должен бы быть, но не для всех функций, или не очень хорошо сочетающийся с вычислимостью, потому что бесконечных списков уже слишком много. Во всяком случае тип конечных списков индуктивный, а тип бесконечных уже не индуктивный.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group