Не надо так оверквотить. ОК?
K>ИМХО, тут нельзя говорить о ОО и ФЯ как о полюсах.
Дык я то как раз только "за". Но вот я не раз встречал ФП-джидаев которые ООП на дух не переносят. Вот и интересно послушать про то, что же в этой области может предложить ФП. С Хаскелем все ясно, но это ООП вид сбоку. Про Немерле, Скалу и ОКамл опять же говорить не приходится, так как это чистые гибриды.
Выходит, что борьба с ООП просто глупа. И без него в общем-то никуда.
K> ОО возникло как средство абстрагимрования на базе ИЯ. Но ведь аоздавать систему с определённым дизайном нужно и в ФЯ. Потому придумывают разные подходы, либо притягивая за уши ОО, чтобы он подошёл к ФЯ (как в OCaml), либо делают смешанный ФЯ/ИЯ, который нормально уживается с ОО (Nemerle, Scala), либо, как в Хаскеле, придумывают свой особенный механизм абстрагирования. Причём в чём-то он похож на ОО и на интерфейсы из джавы, но это всё-таки нечто другое.
О том и речь. Вот и интересно мнение наиболее ортодоксальных фунциональщиков. Ведь когда все крутится вокруг одних однораправленных связанных списков, то чувствуется какая-то ущербность.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, awson, Вы писали:
A>Ага, за исключением того малюсенького обстоятельства, что классы типов в Хаскелле обеспечивают сколь угодно изощренное метапрограммирование. И это не какие-то приколы, а повсеместно работает в real world коде.
Обоснуй это урверждение. Я метапрограммирования в них в упро не вижу. Оди в один идея явного воплощения абстрактных типов как в АДА.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR>Массивы (то есть структура данных с произвольным доступом) не слишком красиво ложатся в ФП, так как изменение требует O(n) — весь массив должен быть скопирован (по крайней мере в наивной реализации).
Ага. И это проблемы ФП, а не массивов. В прочем, на мой взгляд, это вопрос наличия сахара и привязанности ортодоксальным идеям.
LCR>Чтобы успешно использовать массивы, нужно решить 2 проблемы (это в принципе известный факт, но я озвучу для полноты изложения):
LCR>1. Проблема инициализации массива. В стандартных императивных алгоритмах часто проезжают по всем элементам массива устанавливая значеня одно за другим. Другими словами, чтобы инициализировать массив размера n, должно быть произведено n-1 деструктивных операций, если каждое действие требует создание копии, то мы приплыли к O(n^2).
LCR>2. Проблема изменения существующего массива (который может иметь вообще говоря несколько имён).
На мой взгляд, начинать нужно не с вопросов краткости и производительности, а с вопросов связанных с полиморфизмом и абстрацией.
Пока что я вижу только один полноценный механизм абстрагирования в ФЯ — это классы типов Хаскеля. Причем их идея фактически заимствована из ООП. Это те же интерфейсы — вид сбоку.
Другие языки или являются гибридами и предоставляют ОО-полиморфизм, или просто не предоставляют полноценных средств абстрации (ну, или я их в упор не могу увидить).
LCR>Ок, хватит про массивы (Подробный анализ массивов в ФП можно найти у Криса Окасаки).
Меня этот вопрос не интересует. См. выше.
LCR>Со списками же, как ты понимаешь, проблем гораздо меньше. Фактически, список — это и есть общий низкоуровневый интерфейс для некоторой последовательности.
Нифига списки не интерфейс. Списки это голимая реализация. Просто они неплохо ложаться на идеи фунционального вычисления. Но скажем интрфейс IEnumerable<T> ложится на них не сильно хуже.
В общем, еще раз повторю вопрос.
Где в ФП те средства абстракции и полиморфизма которыми мы так привыкли пользоваться в ООЯ? И если их нет, то к чему противопоставлять ООП и ФП? Не лучше ли думать о их сблжении? А то и вообще рассматривать ФП как отдельную технику программирования, а не как полноценную парадигму.
LCR> Всё что нужно, у него есть: конструктор списка cons, и деструктор с помощью паттерн-матчинга. Если сказать кратко: список — это и есть "итератор" в ФП.
У абстрации не может быть конструкторов. Это костыли нужные классическим реализациям паттерн-матчинга. У абстрации должен быть интерфейс который может быть воспроизведен в разных структрах данных.
Вот классы типов Хаскеля — это отличная демонстрация такого интерфейсов. ОО-интерфейсы тоже.
Выходит, что ФП банально не предоставляет таких базовых вещей достижения полиморфизма. А значит он не совсем полноценный и требует введения этих концепций.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Quintanar, Вы писали:
Q>Вообще-то, в книгах по СТЛ рекомендуют не пытаться писать коллекционно-независимый код, каждая коллекция индивидуальна и имеет свои особенности, которые сильно влияют на производительность.
Странные ты книжки читаешь. СТЛ и есть набор независимых от контейнеров алгоритмов. А итераторы средство абстргирования (интерфейс).
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Gaperton, Вы писали:
G>Очень правильный вопрос. Строго говоря, описанное тобой свойство — это слабое место многих ФЯ,
Вот и мне так показалось. Только похоже проблема это не ФЯ, а ФП как такового. Я так и не увидил именно идеологических ФП-шных средств полиморфизма (не параметрического).
G> которое большинство обходит стороной. Однако, эта проблема решена в Scala и отстствует в Haskell.
Согласен с парой оговорок. В Скале (как в Немерле, ОКамле и т.п.) банально используется ООП. А Хаскель расширяет идеии ФП вводя механизм абстрагирования аналогичный ОО-интерфейсам и даже более гибкий чем в ООЯ механизм их реализации.
В общем, решение Хаскеля замечательно, но оно не основано на идеях ФП. Оно скорее их дополняет отсуствующим в них компонентом.
Вот и интересно почему все же в ФП нет таких идей изначально? И почему не смотря на такой пробел все же большинство ФЯ не расширятся такими средствами?
Так же интересно почему многие опологеты ФП просто таки борются с ООП вместо того, чтобы осознать, что его принцыпы отлично дополняют ФП?
G>1) В скале проблема решается тем, что ты можешь выполнять паттерн-матчинг на итераторах. В результате, вместо списка можно подпихнуть что угодно в функцию, которая рекурсивно через паттерн-матчинг пробегается по чему-то, что ей подпихнули. Для решения этой проблемы нужна возможность выполнять сопоставления с образцом на пользовательских абстрактных типах данных — это должен подделживать язык, и в Скале это есть. Или...
На самом деле паттерн-матчинг не обязателен. Пробежаться по коллекции можно и тупо вызвая метод Next(). Важно чтобы была бастракция вроде интерфейса. В Скале эту роль выполняют трэйтсы. По своим свойствам они полностью аналогичны интерфейсам.
G>2) язык должен быть ленивым. В Хаскеле проблемы нет, благодаря тому, что язык ленивый. Поэтому, достаточно для каждого контейнера определить функцию, перегоняющую его в список. В результате, функция обработки определенная на списке эффективно заработает на любом контейнере — благодаря ленивости и оптимизации deforestation промежуточный список компилятор вообще вырежет, и сгенерирует вместо него код однонаправленного итератора.
Недостаточно. Опять же нужен механим абстрагирования. Такой механизм в Хасклее — это классы типов. И по-моему, они мало чем отличаются от ООП-ных интефейсов. Более того при этом явно просматривается состояние. Другое дело, что в Хаскеле оно пропускается через стек и не выглядит как чистый ООП. Но приципы те же.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, <Аноним>, Вы писали:
А>первое. нужно противопоставить ООП и полиморфизм. при ООП каждый объект включает VMT, из которой берутся реализации операций. при полиморфном программировании реализации операций передаются отдельным (невидимым) аргументом. полиморфизм совместим с type inference. STL в C++ как я понимаю, это полиморфизм в чистом виде — никаких VMT, вывод типов, реализации алгоритмов не включены в состав объектов, хотя и не передаются отдельным аргументом — они просто подставляются во время компиляции. поравьте меня, если я плохо знаю STL, но там нет и не иожет быть никакого наследования алгоритмов, поскольку они сделаны на templates, a templates — это и есть compile-time polymorphism, не имеющий никакого отношения к ООП. в STL достаточно использовать стандартную схему наименования для новых коллекций, никакого ООП наследования не требуется, верно?
ООП никогда не упирался в VMT и другие проблемы реализации. В ООП есть главное, чего нет в ФП. В ООП есть понятие интерфейса. Чего-то абстрактного что определяет набор методов которые должен реализовать некий объект. Это позволяет применять к разнм (совсем, разные, не связанные ничем) объектам одни и те же функции/методы. Причем совершенно по фигу когда производится разрешение типов, в компайл-тайме (как в С++-шаблонах), или в рантайме (как в интерфейсах Явы/C# или трэйстах Скалы). Важно, что есть механизм полного абстрагирования от конкретного типа. Такой механизм есть и в Хаскеле. Это классы типов. Суть их полностью аналогична ОО-интерфейсам.
А>type classes отличаются от C++ templates тем, что реализация операций класса для конкретного обрабатываемого типа передаётся невидимым аргументом в функцию и это означает, что можно генерить один код, работающий с любым типом, а также что во время выполнения можно производить различные манипуляции над этими словарями
Какие еще невидимые аргументы? Если речь о Хаскле, то там все передается явно. Просто опят же присутствует интерфейс и порождаемый им полиморфизм.
Спасибо. Но мне смешно смотреть на противопоставления ООП ООП-у.
>>Замечательно. Только в Хаскеле классы типов — это фактически вариант интерфейсов. А их воплощения ни что иное как аналог реализации интерфейсов в классаях.
А>сейчас я бы так не сказал. скорее интерфейсы темплейтов с run-time передачей
Темплэйты тут не причем. В STL абстрация получается не только за их счет. Там важно то, что абстрактен итератор. А его абстрагирование достигается как раз за счет введения интерфейса.
VD>>Так есть ли что-то в ФП для создания действительно абстракных функций обработки всего что может быть абстрактно отнесено к спискам. Или все же ФП это стиль завязанный исключительно на односвязанные списки?
А>есть две библиотеки — collections и edison, которые жтим и занимаются, классы folfable, applicative и прочие тоже частично это делают.
Стоп. Это есть в Хаскеле. А где анлоги в других ФЯ?
А>кроме того, есть такая штука, как generic programming (это не generics из ООП языков). грубо говоря, она позволяет писать универсальные функции, работающие с любым типом. в ООП языках его можно сэмулировать с помощью RTTI или макросов. вот пример применения одной из таких библиотек: представь себе, что у тебя есть AST некоторой программы. тип, описывающий AST. может содержать десятки вариантов, сама AST может содержать тысячи узлов различной вложенности. и тем не менее напечатать все идентификаторы, начинающиеся на 'A', можно простой строчкой:
А>print (gfilter (\(ID ('a':_)) -> True) ast)
Это не то. Вот если бы ты мог применить свой gfilter к массиву, дереву и списку одновременно, тогда бы это было то.
В общем, меня не интересуют примеры из жизни. Мен интересно услышать объяснение механизмов ФП обеспечивающих полиморфизм на уровне ООП (классы типов Хаскеля опускаем как частный случай). Или признание того, что таких механизом в ФП нет и это упущение парадигмы.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
L>>в окамле есть классы...
VD>Аналогично. В прочем, классы опят будет ООП и стало быть гибридное решение. Получается, что как раз ФП-шного решения этой проблемы не существует?
Вопрос был
Так есть ли что-то в ФП для создания действительно абстракных функций обработки всего что может быть абстрактно отнесено к спискам.
Задача — создать набор функций, задаваемый над некоторым подмножеством допустимых типов данных, расширяемым впоследствии. Для этого необходимы языковые механизмы поддерживающие выделение такого специфического подмножества, и связывающие его с этим набором функций. В самой постановке задачи зашито объединение "какие-то типы данных"+"какая-то функциональность". Любой механизм такой склейки будет выглядеть как ООП.
В Хаскелле функциональность описывается в классах типов, а реализуется либо в instance declaration'ах для типов данных, если есть специфика реализации для конкретного полиморфного типа (List, Array), либо для всего класса типов по дефолту (с возможностью перегрузки).
D>Так есть ли что-то в ФП для создания действительно абстракных функций обработки всего что может быть абстрактно отнесено к спискам.
Ага.
D>Задача — создать набор функций, задаваемый над некоторым подмножеством допустимых типов данных, расширяемым впоследствии. Для этого необходимы языковые механизмы поддерживающие выделение такого специфического подмножества, и связывающие его с этим набором функций. В самой постановке задачи зашито объединение "какие-то типы данных"+"какая-то функциональность". Любой механизм такой склейки будет выглядеть как ООП.
Ага. Я даже скажу больше. Он будет требовать наличия и передачи состояния. Так как нам нужно не просто набор фунций, а некий объект позволющий с помощью этих фунций перебирать коллекции. Нам мало функции Next(). Нам еще нужно нечто, что инкапсулирует конкретную коллекцию и превратит ее в некую абстрацию. И это действительно в моем понимании очень похоже на ООП.
D>В Хаскелле функциональность описывается в классах типов, а реализуется либо в instance declaration'ах для типов данных, если есть специфика реализации для конкретного полиморфного типа (List, Array), либо для всего класса типов по дефолту (с возможностью перегрузки).
С Хаскелем у меня вопросов нет. У меня вопрос в том может ли сама парадигма ФП предоставить что-то для решения этой проблемы? Или все она нуждается в расширении некой идеологией сходной с иделогией ОО-интерфейсов или классов типов Хаскеля?
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Обоснуй это урверждение. Я метапрограммирования в них в упро не вижу. Оди в один идея явного воплощения абстрактных типов как в АДА.
Здравствуйте, VladD2, Вы писали:
VD>В ООП есть понятие интерфейса. Чего-то абстрактного что определяет набор методов которые должен реализовать некий объект. Это позволяет применять к разнм (совсем, разные, не связанные ничем) объектам одни и те же функции/методы.
Ну а в лиспе есть дженерики — позволяют "вызывать" методы, определённые вообще для чего угодно...
Re: ФП и абстракция списка
От:
Аноним
Дата:
02.06.07 09:28
Оценка:
Здравствуйте, VladD2, Вы писали:
VD>Внимание! Вопрос!
VD>Так есть ли что-то в ФП для создания действительно абстракных функций обработки всего что может быть абстрактно отнесено к спискам. Или все же ФП это стиоль завязанный исключительно на односвязанные списки?
Не совсем понятно, что именно тебе "надо"
Хаскель ты отмёл...
На списках можно сделать почти всё (см. SICP). Выглядеть это может несколько "необычно", но "вам шашечки или ехать"?
Здравствуйте, VladD2, Вы писали:
L>>Например, какие? На Лиспе, как известно, можно сделать всё,
VD>Дык, покажи.
Первое, что пришло в голову, определить два макроса define-overload и define-overload-instance.
Первый создает словарь, в котором по предикатам (или по каким другим ключам, например, сразу по типам) можно найти нужную реализацию и функцию, которая лазает по словарю в поисках нужной реализации, второй макрос пихает в словарь предикат и конкретную реализацию. Определяться, какая реализация будет вызвана, будет в рантайме или во время компиляции в зависимости от того, как напишем.
L>>в окамле есть классы...
VD>Аналогично. В прочем, классы опят будет ООП и стало быть гибридное решение. Получается, что как раз ФП-шного решения этой проблемы не существует?
Если представить перегруженную функцию как одну, но с реализацией, разбросанной по разным участкам кода — в зависимости от того по чему идёт диспач, то ОО — это одно решение, а классы типов — другое этой задачи. Они схожи только тем, что решают одну задачу — одна функция разбросана по разным местам в зависимости от диспача. Поэтому, если смотреть на проблему с этой точки зрения, говорить о том, что классы типов (или какая другая система диспача) — это ОО решение некорректно.
Но это уже философия. Я что сказать хочу — исходя из задачи и решение будет. Ведь вопрос был именно о перегрузке? Есть ли перегрузка в ФП? Есть. Из-за того, что она есть также и в ОО это не делает ее ОО решением.
Здравствуйте, VladD2, Вы писали:
VD>С Хаскелем у меня вопросов нет. У меня вопрос в том может ли сама парадигма ФП предоставить что-то для решения этой проблемы? Или все она нуждается в расширении некой идеологией сходной с иделогией ОО-интерфейсов или классов типов Хаскеля?
Здравствуйте, VladD2, Вы писали:
VD>Дык я то как раз только "за". Но вот я не раз встречал ФП-джидаев которые ООП на дух не переносят. Вот и интересно послушать про то, что же в этой области может предложить ФП. С Хаскелем все ясно, но это ООП вид сбоку. Про Немерле, Скалу и ОКамл опять же говорить не приходится, так как это чистые гибриды.
VD>Выходит, что борьба с ООП просто глупа. И без него в общем-то никуда.
Мне кажется, это вопрос взгляда. Смотришь на мир с точки зрения ООП — сравниваешь другие решения с ООП, но это всего лишь аналогия, а не ООП.
VD>О том и речь. Вот и интересно мнение наиболее ортодоксальных фунциональщиков. Ведь когда все крутится вокруг одних однораправленных связанных списков, то чувствуется какая-то ущербность.
Конечно Тут видимо от Лиспа, да и вообще от лямбда исчисления пошло — список наиболее простая абстракция для создания сколь угодно сложных абстракций представления данных. Особенно лисповый, где у элементов могут быть элементы любого типа. С ним много примеров, на нем показываются различные приемы, новичку может показаться, что ФП — это сплошные списки, но на самом деле это не так. Как и в языках, не являющихся ФП, в ФП в нужном месте используются нужные контейнеры.
Здравствуйте, <Аноним>, Вы писали:
А>при обработке самих списков — да. а вот если у тебя есть операция, генерящая списки... то наверно тоже да. a stream fusion — это как я понял каокй-то другой способ достижения той же цели, который уже применён в bytestring и как я понял, им собираются заменить foldr/build систему. в общем, я тоже только краем уха слышал
foldr/build как раз при операциях генерящих и сворачивающих списки, элиминация заключается в создании "прямой" функции. Два недостатка — не работает над несколькими списками (zip), и над левым fold. Ещё есть destroy/unfoldr. Тоже какие то недостатки есть.
Насколько я понял, там основная проблема — рекурсия. Компилятор плохо (по моему совсем не) оптимизирует рекурсивные функции. Имеется в виду разумеется элиминация промежуточных данных. Поэтому в stream fusion списки преобразовывают в потоки, функцию получаются не рекурсивными. А то, что, кажется, что мы меняем шило на мыло — это не так. Остальную работу по элиминации потоков выполняет компилятор, т.к. в нерекурсивных функциях он может это делать. Там есть интересные тонкости, в конце я приведу список литературы
Duncan Coutts и Don Stewart расширили эту технику на вложенные списки и зипы (работа с несколькими списками). Мало того, эта техника оказалась пригодной для работы не только над списками, но и над массивами. Т.е. функциональный код превращается в близкий к сишному.
Здравствуйте, VladD2, Вы писали:
А>>print (gfilter (\(ID ('a':_)) -> True) ast)
VD>Это не то. Вот если бы ты мог применить свой gfilter к массиву, дереву и списку одновременно, тогда бы это было то.
Он и применяет. ast — это некий (в принципе, любой) тип данных, который внутри (сколь угодно глубоко) содержит идентификатор(ы).
Здравствуйте, lomeo, Вы писали:
L>Первое, что пришло в голову, определить два макроса define-overload и define-overload-instance. L>Первый создает словарь, в котором по предикатам (или по каким другим ключам, например, сразу по типам) можно найти нужную реализацию и функцию, которая лазает по словарю в поисках нужной реализации, второй макрос пихает в словарь предикат и конкретную реализацию. Определяться, какая реализация будет вызвана, будет в рантайме или во время компиляции в зависимости от того, как напишем.
Хм. Закат солнца вручную?
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, lomeo, Вы писали:
L>Мне кажется, это вопрос взгляда. Смотришь на мир с точки зрения ООП — сравниваешь другие решения с ООП, но это всего лишь аналогия, а не ООП.
Какая разница как и куда я смотрю. Если в ФП нет концептуальных решений для данной проблемы, то их нет независимо от того как и куда я смотрю.
Хаскель отровенно расширен похожен на ООП технологией. ОКамл просто ООЯ. Я не сомневаюсь, что его создатели исходили из разных предпосылок, но пришли они к очень похожим решениям.
L>Конечно Тут видимо от Лиспа, да и вообще от лямбда исчисления пошло — список наиболее простая абстракция для создания сколь угодно сложных абстракций представления данных.
В том то и дело, что список не абстракция, а конкретика. Подходить, то он конечно подходит. Но конкретика есть кокретика. Он не всегда хорошо подхдит для всех задач. А о производительности вообще говорить не приходится.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
ОО отдыхает.
(Подробный анализ массивов в ФП можно найти у Криса Окасаки).
