Думаю все знают, что в Философии недавно разразились несколько споров (как всегда бессмысленных и беспощадных) которые все можно объеденить общей мыслью "что есть ООП и чем от отличается от ...". Одним из таких споров стал спор на счет базиса STL. Один известный, в наших, узких кругах, товарищь долго доказывал что STL — ООП, так как итераторы по сути объектная абстракция.

Не вдаваясь в суть спора по STL хочется поднять одну тему, на мой взгляд пересекающуюся с этой.

Если поглядеть на то как организована работа со списоками в ООЯ, то нетрудно заметить, что она реализуется почти всегд через введение некого абстрактного интерфейса который тем или иным путем реализуется или поддерживается коллекциями. Причем всегда имееся большое количество коллекций поддерживающих этот интерфейс. Нам по барабану тип коллекции. Мы можем взять любую коллекцию и применить к ней тот или иной алгоритм/паттерн.

В С++ это STL-ные итераторы. В C# — это IEnumerable<T>. И так далее, и тому подобное.

Теперь взглянем на мир ФЯ. Что же мы наблюдаем? А наблюдаем мы весьма странную картину. Мы наблюдаем отсуствие астракции в обработке списков. Любой ФЯ (начиная с Лиспа и заканчивая Хасклем) поддерживает однонаправленные связанные, неизменяемые списки. На их базе и строится вся обработка списков.

Конечно почти все ФЯ подерживают полиморфизм списков в том смысле, что позволяет создавать процедуры которые обрабатывают списки с различными типами хранимых значений. Но вот сам список — это всегда "однонаправленный связанный, неизменяемый список". Мы не можем (если я конечно не ошибаюсь) создать единую процедуру которая обрабатывала бы и список и (скажем) массив (коие все же есть в болшинстве ФЯ).

Языки поддерживающие ФП и ООП обычно позволяют ввести ОО-абстракцию (интерфейс) и на ее базе реализовать фукнциональные, но полностью абстрактные фунции обработки списков. ОК. Но это ООЯ. И этим все сказано.

Внимание! Вопрос!

Так есть ли что-то в ФП для создания действительно абстракных функций обработки всего что может быть абстрактно отнесено к спискам. Или все же ФП это стиоль завязанный исключительно на односвязанные списки?

Очень хочется услышать именно мысли, а не защиту "любимой игруки".

Здравствуйте, VladD2, Вы писали:

VD>Конечно почти все ФЯ подерживают полиморфизм списков в том смысле, что позволяет создавать процедуры которые обрабатывают списки с различными типами хранимых значений. Но вот сам список — это всегда "однонаправленный связанный, неизменяемый список". Мы не можем (если я конечно не ошибаюсь) создать единую процедуру которая обрабатывала бы и список и (скажем) массив (коие все же есть в болшинстве ФЯ).

Можем, почему нет? Списки разделяют самые разные интерфейсы с самыми разными типами.
Тебя, скорее всего, заинтересует Data.Foldable

Обрати внимание на типы функций:

sum :: (Foldable t, Num a) => t a -> a

Т.е. любой "сворачиваемый" контейнер может быть обработан этой функцией для подсчёта суммы его элементов.
Погляди на дефолтные инстансы — там есть и список и массив.

Здравствуйте, lomeo, Вы писали:

L>Можем, почему нет? Списки разделяют самые разные интерфейсы с самыми разными типами.
L>Тебя, скорее всего, заинтересует Data.Foldable

L>Обрати внимание на типы функций:

L>

L>sum :: (Foldable t, Num a) => t a -> a
L>

L>Т.е. любой "сворачиваемый" контейнер может быть обработан этой функцией для подсчёта суммы его элементов.
L>Погляди на дефолтные инстансы — там есть и список и массив.

Замечательно. Только в Хаскеле классы типов — это фактически вариант интерфейсов. А их воплощения ни что иное как аналог реализации интерфейсов в классаях.

Выходит используется фактически ОО-подход.

Не так ли?

А в других языках (где нет классов типов или ОО-интерфейсов) как?

Здравствуйте, VladD2, Вы писали:

VD>Замечательно. Только в Хаскеле классы типов — это фактически вариант интерфейсов. А их воплощения ни что иное как аналог реализации интерфейсов в классаях.

VD>Выходит используется фактически ОО-подход.

VD>Не так ли?

Ну, не фактически ОО, а аналогичный.

VD>А в других языках (где нет классов типов или ОО-интерфейсов) как?

Например, какие? На Лиспе, как известно, можно сделать всё,
в окамле есть классы...

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, lomeo, Вы писали:

VD>Замечательно. Только в Хаскеле классы типов — это фактически вариант интерфейсов. А их воплощения ни что иное как аналог реализации интерфейсов в классаях.

VD>Выходит используется фактически ОО-подход.

VD>Не так ли?

Это опять очень холиварная тема по поводу определения ОО. Если ОО — это объекты с состоянием, обменивающиеся сообщениями, то скорее нет. Если православие, самодержавие, народность, то есть тьфу, инкапсуляция, наследование, полиморфизм — то скорее да.

VladD2,

VD>Теперь взглянем на мир ФЯ. Что же мы наблюдаем? А наблюдаем мы весьма странную картину. Мы наблюдаем отсуствие астракции в обработке списков. Любой ФЯ (начиная с Лиспа и заканчивая Хасклем) поддерживает однонаправленные связанные, неизменяемые списки. На их базе и строится вся обработка списков.

Контрпримерs: Sisal и J — функциональные языки, где основная структура — массив. То есть индексация O(1) и т.п. Правда с ними не всё гладко.

Массивы (то есть структура данных с произвольным доступом) не слишком красиво ложатся в ФП, так как изменение требует O(n) — весь массив должен быть скопирован (по крайней мере в наивной реализации).

Чтобы успешно использовать массивы, нужно решить 2 проблемы (это в принципе известный факт, но я озвучу для полноты изложения):

1. Проблема инициализации массива. В стандартных императивных алгоритмах часто проезжают по всем элементам массива устанавливая значеня одно за другим. Другими словами, чтобы инициализировать массив размера n, должно быть произведено n-1 деструктивных операций, если каждое действие требует создание копии, то мы приплыли к O(n^2).

2. Проблема изменения существующего массива (который может иметь вообще говоря несколько имён).

С первой проблемой можно успешно бороться оптимизаторами и навороченной системой типов, с помощью которой можно выделить код с деструктивными эффектами.

Со второй проблемой можно бороться с помощью языковой поддержки и богатых средств доступа к массиву. Например, в том же J интерфейс доступа к массиву — это не банальный набор "получить элемент по индексу, обновить элемент по индексу", а целая куча операций : всякие сортировки, перебор окнами, оператор неподвижной точки, степени, разбиения и т.д. Не факт, что данный набор полный (а кстати, интересно, можно выделить полный базис для доступа к массиву?), но для практических нужд хватает с лихвой.

Как вариант — использовать разряжённые массивы (то есть хэш-таблицы int->object), деструктивные операции также достаточно быстры, а чтение по-прежнему O(1).

Есть ещё v-arrays — версионное дерево, полностью функциональная структура данных, в которой доступ к самой новой копии O(1), а к более старым — "O-большое" от количества произведённых деструктивных операций.

Ок, хватит про массивы (Подробный анализ массивов в ФП можно найти у Криса Окасаки).

Со списками же, как ты понимаешь, проблем гораздо меньше. Фактически, список — это и есть общий низкоуровневый интерфейс для некоторой последовательности. Всё что нужно, у него есть: конструктор списка cons, и деструктор с помощью паттерн-матчинга. Если сказать кратко: список — это и есть "итератор" в ФП.

Здравствуйте, VladD2, Вы писали:

VD>Если поглядеть на то как организована работа со списоками в ООЯ, то нетрудно заметить, что она реализуется почти всегд через введение некого абстрактного интерфейса который тем или иным путем реализуется или поддерживается коллекциями. Причем всегда имееся большое количество коллекций поддерживающих этот интерфейс. Нам по барабану тип коллекции. Мы можем взять любую коллекцию и применить к ней тот или иной алгоритм/паттерн.

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

Здравствуйте, VladD2, Вы писали:

VD>Внимание! Вопрос!

VD>Так есть ли что-то в ФП для создания действительно абстракных функций обработки всего что может быть абстрактно отнесено к спискам. Или все же ФП это стиоль завязанный исключительно на односвязанные списки?

VD>Очень хочется услышать именно мысли, а не защиту "любимой игруки".

Очень правильный вопрос. Строго говоря, описанное тобой свойство — это слабое место многих ФЯ, которое большинство обходит стороной. Однако, эта проблема решена в Scala и отстствует в Haskell.

1) В скале проблема решается тем, что ты можешь выполнять паттерн-матчинг на итераторах. В результате, вместо списка можно подпихнуть что угодно в функцию, которая рекурсивно через паттерн-матчинг пробегается по чему-то, что ей подпихнули. Для решения этой проблемы нужна возможность выполнять сопоставления с образцом на пользовательских абстрактных типах данных — это должен подделживать язык, и в Скале это есть. Или...

2) язык должен быть ленивым. В Хаскеле проблемы нет, благодаря тому, что язык ленивый. Поэтому, достаточно для каждого контейнера определить функцию, перегоняющую его в список. В результате, функция обработки определенная на списке эффективно заработает на любом контейнере — благодаря ленивости и оптимизации deforestation промежуточный список компилятор вообще вырежет, и сгенерирует вместо него код однонаправленного итератора.

Здравствуйте, Gaperton, Вы писали:


G>Очень правильный вопрос. Строго говоря, описанное тобой свойство — это слабое место многих ФЯ, которое большинство обходит стороной. Однако, эта проблема решена в Scala и отстствует в Haskell.

В рефале тоже нет этой проблемы, и решена первым способом.

Здравствуйте, deniok, Вы писали:

D>Это опять очень холиварная тема по поводу определения ОО. Если ОО — это объекты с состоянием, обменивающиеся сообщениями, то скорее нет. Если православие, самодержавие, народность, то есть тьфу, инкапсуляция, наследование, полиморфизм — то скорее да.

Инкапсуляция подразумевает спрятанное в объекте состояние, к которому нет прямого доступа. Без этого объектная декомпозиция невозможна, а без нее об ОО говорить глупо. Под "наследованием" подразумевается такая штука, как "наследование реализации" (т.е. объект наследует поведение, а не интерфейс) — тоже не наш случай.

То что есть в Хаскельном примере — это только полиморфизм. Зато какой! ОО отдыхает.

Здравствуйте, VladD2, Вы писали:

L>>Обрати внимание на типы функций:

L>>

L>>sum :: (Foldable t, Num a) => t a -> a
L>>

L>>Т.е. любой "сворачиваемый" контейнер может быть обработан этой функцией для подсчёта суммы его элементов.
L>>Погляди на дефолтные инстансы — там есть и список и массив.

VD>Замечательно. Только в Хаскеле классы типов — это фактически вариант интерфейсов. А их воплощения ни что иное как аналог реализации интерфейсов в классаях.

VD>Выходит используется фактически ОО-подход.

VD>Не так ли?

VD>А в других языках (где нет классов типов или ОО-интерфейсов) как?

ИМХО, тут нельзя говорить о ОО и ФЯ как о полюсах. ОО возникло как средство абстрагимрования на базе ИЯ. Но ведь аоздавать систему с определённым дизайном нужно и в ФЯ. Потому придумывают разные подходы, либо притягивая за уши ОО, чтобы он подошёл к ФЯ (как в OCaml), либо делают смешанный ФЯ/ИЯ, который нормально уживается с ОО (Nemerle, Scala), либо, как в Хаскеле, придумывают свой особенный механизм абстрагирования. Причём в чём-то он похож на ОО и на интерфейсы из джавы, но это всё-таки нечто другое.

Здравствуйте, VladD2, Вы писали:

VD>Замечательно. Только в Хаскеле классы типов — это фактически вариант интерфейсов. А их воплощения ни что иное как аналог реализации интерфейсов в классаях.

Ага, за исключением того малюсенького обстоятельства, что классы типов в Хаскелле обеспечивают сколь угодно изощренное метапрограммирование. И это не какие-то приколы, а повсеместно работает в real world коде.

Здравствуйте, awson, Вы писали:

A>Ага, за исключением того малюсенького обстоятельства, что классы типов в Хаскелле обеспечивают сколь угодно изощренное метапрограммирование. И это не какие-то приколы, а повсеместно работает в real world коде.

Ммм, покажи на них, к примеру, генерацию кода в компайл-тайме, плиз

Здравствуйте, Курилка, Вы писали:

К>Ммм, покажи на них, к примеру, генерацию кода в компайл-тайме, плиз

Какого кода? Сформулируй точнее.

ты правильно сделал что написал сюда поскольку мне лень логиниться

первое. нужно противопоставить ООП и полиморфизм. при ООП каждый объект включает VMT, из которой берутся реализации операций. при полиморфном программировании реализации операций передаются отдельным (невидимым) аргументом. полиморфизм совместим с type inference. STL в C++ как я понимаю, это полиморфизм в чистом виде — никаких VMT, вывод типов, реализации алгоритмов не включены в состав объектов, хотя и не передаются отдельным аргументом — они просто подставляются во время компиляции. поравьте меня, если я плохо знаю STL, но там нет и не иожет быть никакого наследования алгоритмов, поскольку они сделаны на templates, a templates — это и есть compile-time polymorphism, не имеющий никакого отношения к ООП. в STL достаточно использовать стандартную схему наименования для новых коллекций, никакого ООП наследования не требуется, верно?

type classes отличаются от C++ templates тем, что реализация операций класса для конкретного обрабатываемого типа передаётся невидимым аргументом в функцию и это означает, что можно генерить один код, работающий с любым типом, а также что во время выполнения можно производить различные манипуляции над этими словарями

рекомендую http://haskell.org/haskellwiki/OOP_vs_type_classes и http://homepages.inf.ed.ac.uk/wadler/papers/class/class.ps.gz


>Замечательно. Только в Хаскеле классы типов — это фактически вариант интерфейсов. А их воплощения ни что иное как аналог реализации интерфейсов в классаях.

сейчас я бы так не сказал. скорее интерфейсы темплейтов с run-time передачей


VD>Так есть ли что-то в ФП для создания действительно абстракных функций обработки всего что может быть абстрактно отнесено к спискам. Или все же ФП это стиль завязанный исключительно на односвязанные списки?

есть две библиотеки — collections и edison, которые жтим и занимаются, классы folfable, applicative и прочие тоже частично это делают. фактически это находлится в загоне, поскольку мало кому нужно. вместо этого реализовывают различные типы данных с Data.List-подобным интерфейсом и удовлетворяются тем, что одим тип коллекций можно заменить на другой простой сменой импорта. Data.Map. Data.ByteString сделаны подобным образом. учитывая сложности с созданием полиморфных коллекций, потребность именно в том, чтобы это было классом, действительно мало у кого возникает


кроме того, есть такая штука, как generic programming (это не generics из ООП языков). грубо говоря, она позволяет писать универсальные функции, работающие с любым типом. в ООП языках его можно сэмулировать с помощью RTTI или макросов. вот пример применения одной из таких библиотек: представь себе, что у тебя есть AST некоторой программы. тип, описывающий AST. может содержать десятки вариантов, сама AST может содержать тысячи узлов различной вложенности. и тем не менее напечатать все идентификаторы, начинающиеся на 'A', можно простой строчкой:

print (gfilter (\(ID ('a':_)) -> True) ast)

при этом gfilter включает в себя универсальный код для обхода произвольных структур данных

G>благодаря ленивости и оптимизации deforestation промежуточный список компилятор вообще вырежет, и сгенерирует вместо него код однонаправленного итератора.

вряд ли. насколько я разбираюсь, спислк так и будет лениво генерироваться в процессе потребления. deforestatuion делают специально в отдельных библиотеках на RULES. реально оно сейчас есть в bytestring и parallel arrays — afaik. точнее, его называют stream fusion

(если я что-то неправильно понимаю — исправляйте)

Здравствуйте, Аноним, Вы писали:

G>>благодаря ленивости и оптимизации deforestation промежуточный список компилятор вообще вырежет, и сгенерирует вместо него код однонаправленного итератора.

А>вряд ли. насколько я разбираюсь, спислк так и будет лениво генерироваться в процессе потребления. deforestatuion делают специально в отдельных библиотеках на RULES. реально оно сейчас есть в bytestring и parallel arrays — afaik. точнее, его называют stream fusion

А>(если я что-то неправильно понимаю — исправляйте)

Вроде как в GHC foldr/build rule позволяет элиминировать списки во многих ситуациях (см. здесь).

Хотя я не большой специалист в его (GHC) внутреннем устройстве.

D>Вроде как в GHC foldr/build rule позволяет элиминировать списки во многих ситуациях (см. здесь).

при обработке самих списков — да. а вот если у тебя есть операция, генерящая списки... то наверно тоже да. a stream fusion — это как я понял каокй-то другой способ достижения той же цели, который уже применён в bytestring и как я понял, им собираются заменить foldr/build систему. в общем, я тоже только краем уха слышал

Здравствуйте, Аноним, Вы писали:

А>первое. нужно противопоставить ООП и полиморфизм. при ООП каждый объект включает VMT, из которой берутся реализации операций. при полиморфном программировании реализации операций передаются отдельным (невидимым) аргументом. полиморфизм совместим с type inference. STL в C++ как я понимаю, это полиморфизм в чистом виде — никаких VMT, вывод типов, реализации алгоритмов не включены в состав объектов, хотя и не передаются отдельным аргументом — они просто подставляются во время компиляции. поравьте меня, если я плохо знаю STL, но там нет и не иожет быть никакого наследования алгоритмов, поскольку они сделаны на templates, a templates — это и есть compile-time polymorphism, не имеющий никакого отношения к ООП. в STL достаточно использовать стандартную схему наименования для новых коллекций, никакого ООП наследования не требуется, верно?

Что такое "схема наименования"? В STL контейнеры должны выставлять интерфейс итераторов, которые реализуют разные "концепции", всё более и более сильные: от итератора ввода (в одну сторону и только на чтение) до итератора произвольного доступа (по функциональности — обычный сишный указатель). А алгоритмы работают с итераторами, реализующими "концепции" нужной для алгоритма силы (это сделано в том числе и для эффективности реализации). А наследования контейнеров действительно не нужно.



А>кроме того, есть такая штука, как generic programming (это не generics из ООП языков). грубо говоря, она позволяет писать универсальные функции, работающие с любым типом. в ООП языках его можно сэмулировать с помощью RTTI или макросов. вот пример применения одной из таких библиотек: представь себе, что у тебя есть AST некоторой программы. тип, описывающий AST. может содержать десятки вариантов, сама AST может содержать тысячи узлов различной вложенности. и тем не менее напечатать все идентификаторы, начинающиеся на 'A', можно простой строчкой:

А>print (gfilter (\(ID ('a':_)) -> True) ast)

А>при этом gfilter включает в себя универсальный код для обхода произвольных структур данных

Что имеется ввиду под словами функции, работающие с любым типом?

gfilter :: forall a. (... -> Bool) -> a

?
Или всё же AST делается Gfilterable через какой-то instance declaration?

Здравствуйте, lomeo, Вы писали:

L>Например, какие? На Лиспе, как известно, можно сделать всё,

Дык, покажи.

L>в окамле есть классы...

Аналогично. В прочем, классы опят будет ООП и стало быть гибридное решение. Получается, что как раз ФП-шного решения этой проблемы не существует?