Вышел 2-й выпуск журнала «Практика функционального программирования»

> Браво! Только не функтор, а эндофунктор: F: A -> A.

Ага, чем-то =<< определённо fmap напоминает.

> И еще два преобразования: mu: F^2 -> F

А это что означает применительно к Хаскеллу?

> и eta: 1 -> F, где 1 - единичная категория, содержащая только один объект.

Это return?

> Осталось решить что это за мифическая категория "А", т.е. что там является объектами и что там является морфизмами (стрелками).

Не томи. :)

Пошёл читать http://en.wikibooks.org/wiki/Haskell/Category_theory

Может кто-нибудь знает другие хорошие статьи типа "теория категорий для чайников"?

> Может кто-нибудь знает другие хорошие статьи типа "теория категорий для чайников"?

Рискну предложить "Категории для работающего математика", Маклейн С. Перевод 2004 года.

> Может кто-нибудь знает другие хорошие статьи типа "теория категорий для чайников"?

http://community.livejournal.com/category_theory/2190.html

1. Barr, Wells. Category Theory.pdf 2. Adamek, Herrlich, Strecker. The Joy of Cats.pdf 3. Goguen. A Categorical Manifesto.pdf 4. Saunders Mac Lane. Categories for Working Mathematician.djvu

> Потому что они развиваются _уходя от_ императивной модели.

Потому что они развиваются в сторону высокоуровневости - увеличению своей выразительности, которая не обязательно будет чисто функциональной. Не подскажите, почему умные мужики из scheme и *ml _пришли_ к деструктивному присваиванию и фреймовой модели?

> И куда сейчас чем дальше тем больше идут такие языки? Все хотят на том или ином уровне компилить и осуществлять пфронт анализ исходников.

Что осуществлять? Вообще говоря, интерпретируемость/компилируемость (натив, байт-код) - не есть свойство языка - а свойство реализации, даже для си есть интерпертатор.

> Осталось решить что это за мифическая категория "А", т.е. что там является объектами и что там является морфизмами (стрелками).

К сожалению, тут речь идет о типах в качестве объектов, и о функциях, как о стрелках. Поэтому требования категориальных монад и хаскельных монад слегка отличаются(хаскельные монады задают более жесткие требования). Не к этом ли ведет мсье?

> У тебя сколько денег на счету? Не поделишься абстракцией?

213111,00

> Вот забавно откуда беруться люди которые делят вещи на реальные и абстрактные.

Потому что линейка реальна, а ее длина - абстрактна, это количественная характеристика.

> По твоему наличие яиц в холодильнике не описательная характеристика?

Описательная.

> Уход совершенно абстрактных чисел с твоего счета совершенно реально оставит тебя без яичницы и кровати.

Я тебе сказал число, давай "меняй" его - разоряй меня.

> Реально императивное программирование обладает реально императивными свойствами - ключевое из которых - мутация состояния. Если исключить это ключевое ствойство - это уже _не_ императивный подход.

Каждый раз, когда я использую монаду State в хаскелле - я использую императивный подход, но ведь хаскелл чисто-функциональный, как такое возможно? :)

> Я из тех людей котоыре не сушат в микроволновке которов потому что знает какой будет результат из сути происходящего, а не из инструкции по пользованию.

Ну тогда ты бы должен был понять, к чему приводит твой код.

> Любой инструмент которым можно воспользоваться неправильно - будет использован неправильно. Дальше все сводится к удобству инструмента.

Кухонным ножом можно зарезать - запретим ножи?

> Опять двадцать пять. Дай четкое определение объекта и не объекта согласно которому ты отнес числа к необектам а яйца к объектам.

Объект - это то, что обладает identity и состоянием. Яйцо - это реальный предмет, а число - это абстракция (просто по определению).

Яйца можно смоделировать как угодно, все зависит, что нам нужно от этой модели.

> Объявление сигнатуры функции вполне себе декларативно. Сам код можно писать как в императивном стиле, так и в декларативном.

Декларативное != функциональное. Декларативное - это более общее понятие. Хотя это вопрос определений.

> С функциональной точки зрения на входе функции мы имеем один мир, на выходе - другой. Только практической пользы от такой функции мало: доказать корректность работы,

> Только практической пользы от такой функции мало: доказать корректность работы,

> практической пользы

> доказать корректность

Б-же мой, от функции нет никакой пользы, если ее корректность не может быть доказана, узнаю фп-фанбоев Тем более, что доказать корректность можно только у чистой функции. Тем более, что доказать корректность можно не только чисто-функциональной фунцкии (извиняюсь за тавтоглогию), но даже - о б-же императивной, не сильно при этом страдая.

> даже просто оттестировать её нормально малореально.

Зачем ее тестировать, если мы доказали ее корректность? :)

> god@heaven:~/projects/homework#

> :)

Я не хочу жить в мире, в котором, исключение "разбитое яйцо" невозможно обработать.

Значицца намендни мы установили, что монада - это тройка: эндофунктор из категории Hask в категорию Hask и два преобразования eta и mu.

Как справедливо заметил clash, объектами каетогории Hask являются все возможные типы языка Haskell, а морфизмы - "программы" на языке Haskell.

Поскольку функтор у нас эндо-, то он сам является таким же равноправным типом языка Haskell т.е. объектом категории Hask.

Из этого следует два очень интересных вывода:
1. Множество объектов категории Hask бескончено и не требует формального определения (хотя, конечно, дать его можно). (Оно и понятно, в теории категорий морфизмы, а не объекты играют главную роль).
2. Множество морфизмов категории Hask бесконечно и не определено формально.

Т.е. нашу любимую категорию Hask мы рассматриваем на очень "абстрактном" уровне (если, конечно, такой термин применим к теории категорий :)).

Дополнительно в теории категорий определена операция композиции морфизмов для Hask - это (.) и у каждого объекта есть морфизм Id отображающий объект сам в себя.

Эндофунктор F ставит в соответствие каждому объекту a и категории Hask объект F A, и каждому морфизму f: A -> B морфизм F f : F A -> F B

В хаскеле полиморфный алгебраический тип F является эндофунктором F:Hask -> Hask. Применение эндофунктора к объекту каетгории Hask осуществляется с помощью вызова конструктора типа, который и явяется преобразованием eta.

Для применения функтора к морфизмам, используется функция fmap::(a->b) -> F a -> F b, определенная в типклассе Functor.

Ну вот мы в общих чертах разобрались с функторами. Но как говориться, "ее радость была бы не полной, без...". Проблема в том, что функциональный тип (первый прарметр функции fmap) сам является... ФУНКТОРОМ, и как любой уважающий себя функтор оперделен как instance типкласса Functor, и, забегая вперед, как instance типкласса Monad (!!!). Но это тема отдельного разговора.

>http://community.livejournal.com/category_theory/2190.html

И еще очень рекомендую:

1. Pablo Nogueira. When is an abstract data type a functor? http://babel.ls.fi.upm.es/~pablo/Papers/adt-functors.pdf.
2. Andrew Martin , Jeremy Gibbons. A Monadic Interpretation of Tactics http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.251

> Попробуй думать об "объектах" как о событиях, а о функциях как о реакциях на события.

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

> И еще очень рекомендую:

Кстати, bird есть в свободном доступе или что-нибудь на него похожее?

> Затем идёт декларативное описание (x — это a,b,c,...; выдай мне "нормальное", понятное мне x).

> Нужно описывать, _как_ получить x, а не то, _чем_ является x, и не то _что_ такое x вообще.

Выразительность можно получить не только с помощью чисто декларативного программирования. Тем более, если мы описываем класс ооп-объектов - с помощью задания его полей (мутабельных) и методов (пусть даже чисто функциональных) - почему это нельзя считать декларативным программированием?

> Выразительность можно получить не только с помощью чисто декларативного программирования.

Я не могу придумать пример, где декларация имела бы меньшую выразительную силу, чем алгоритм.

> Тем более, если мы описываем класс ооп-объектов - с помощью задания его полей (мутабельных) и методов (пусть даже чисто функциональных) - почему это нельзя считать декларативным программированием?

Потому что нужно написать реализацию.

> Потому что они развиваются в сторону высокоуровневости - увеличению своей выразительности, которая не обязательно будет чисто функциональной.

Не важно куда они бегут, главное --- откуда. А бегут они как можно дальше от императивности.

> не обязательно будет чисто функциональной.

и какой же она будет?

> почему умные мужики из scheme и *ml _пришли_ к деструктивному присваиванию и фреймовой модели?

иногда нужна возможность отрубить себе ногу ржавым топором. Главное понимать что ты делаешь, почему и зачем.

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

Это... Может, хватит уже выяснять, что более "естественно" для человека? :) Это всё равно ни к чему не приведёт, потому что то, что "естественно", не обязательно будет самым простым, понятным и надёжным методом. Для человека естественнее всего было бы жрать сырое мясо и спать в голой пещере :-)

> Каждый раз, когда я использую монаду State в хаскелле - я использую императивный подход, но ведь хаскелл чисто-функциональный, как такое возможно? :)

Что тебя беспокоит?

В одном и том же коде можно увидеть разные абстракции. Вот, например, монада Maybe на C: http://www.reddit.com/r/programming/tb/1761q Естественно, можно там видеть просто сишную структуру и набор функций.

> И еще очень рекомендую:

А какую бы серьёзную книжку взять по теории категорий?

У меня есть Цаленко+Шульгейфер, но она от 60-х — 70-х годов, а этот раздел математики, afaik, очень быстро развивается.

Можно на английском, только чтобы была очень хорошая :)

>я использую императивный подход

Ты не используешь имепретивный подход. Оператор >>= типкласса Monad по сути дела оператор функциональной композиции. А do-нотация всего лишь удобный способ представления цепочек >>= и >>.

> Ты не используешь имепретивный подход. Оператор >>= типкласса Monad по сути дела оператор функциональной композиции. А do-нотация всего лишь удобный способ представления цепочек >>= и >>.

Я то знаю, что я его не использую, вы объясните это товарищу r.

> Каждый раз, когда я использую монаду State в хаскелле - я использую императивный подход, но ведь хаскелл чисто-функциональный, как такое возможно? :)

Я поэтому выше и отметил, что центром императивного подхода является шаг, инструкция — «statement».

А Monad State управляется вполне функционально.

> Что тебя беспокоит?

То, что r дает некорректные определения, на мой взгляд.

> например, монада Maybe на C: http://www.reddit.com/r/programming/tb/1761q

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

Там именно, что сишная структура и набор функций, которые реализуют определенную абстракцию (в данном случае монаду).

> Я поэтому выше и отметил, что центром императивного подхода является шаг,

Я уже говорил, что с таким подходом, мы приходим к тому, что у нас императивными будут только assembler да машинный код.

> инструкция — «statement».

под statement обычно понимается if-then-else и сотоварищи. В хаскелле и не только этих statement навалом.

> А Monad State управляется вполне функционально.

Я это знаю.

>А какую бы серьёзную книжку взять по теории категорий?

Не знаю. Я читал несколько. На английском. Как раз по ссылке category_programming@lj. Начни с Маклейна.

Еще дело в том, что нет слишком жесткой нотации, поэтому все-равно придется читать все.

У меня не стояло задачи разбираться в ТК, а задача найти теоретическое обонование того, что делают типклассы Functor, Monad и Arrow, так что в дебри я не лез.

> Я уже говорил, что с таким подходом, мы приходим к тому, что у нас императивными будут только assembler да машинный код.

Большинство императивных языков унаследовали это от языков ассемблера (а что делать, «не мы такие, машина такая» :) Конечно, появились абстракции, но семантика осталась. Здесь идут исключением некоторые языки вроде Smalltalk.

> под statement обычно понимается if-then-else и сотоварищи. В хаскелле и не только этих statement навалом.

В ИП if-then[-else] — это просто высокоуровневый аналог jz/jnz. В ФП — это аналог математического определения, например, модуля числа: x = if x>=0 then x else -x. Там нельзя выполнить действие.

Может, я просто неправильно понимаю, что означает statement.

А вообще-то нет: http://en.wikipedia.org/wiki/Statement_%28programming%29

Потому что они развиваются в сторону высокоуровневости - увеличению своей выразительности,

А ты можешь оперировать более техническими терминами, чем высокоуровневость или выразительность?

Что осуществлять?

апфронт анализ.

print "aaaaaa"

vsiakij bred

  File "x.py", line 3
    vsiakij bred
               ^
SyntaxError: invalid syntax

>213111,00

Поделиться - в данном случае было фактически - а не "информацией".

>Потому что линейка реальна, а ее длина - абстрактна, это количественная характеристика.

Твоя линейка для меня не абстрактна? Серьезно?!?

>Я тебе сказал число, давай "меняй" его - разоряй меня.

При чем тут кто? Дай характеристику свойств абстрактных объектов и реальных в кеоторых они различаются и по чем ты их разделил.

> В ИП if-then[-else] — это просто высокоуровневый аналог jz/jnz. В ФП — это аналог математического определения, например, модуля числа: x = if x>=0 then x else -x. Там нельзя выполнить действие.

[code] Prelude> let func x = if x > 0 then putStrLn "Yes" else putStrLn "No" Prelude> func 4 Yes Prelude> func (-5) No [/code]

? :)

case-statement в do? - это не конструкция? Только не надо говорить, что это синтаксический сахар, я это и так знаю.

> А вообще-то нет: http://en.wikipedia.org/wiki/Statement_%28programming%29

Ну если следовать их логике, а она у них какая-то ну совсем противоречивая, ты тоже не прав. Вот тут.

> Я поэтому выше и отметил, что центром императивного подхода является шаг, инструкция — «statement».

Потому как в например, common lispe вообще нет statements - однако это императивный язык (там есть setf и прочие императивные прелести).

> Ты не используешь имепретивный подход. Оператор >>= типкласса Monad по сути дела оператор функциональной композиции. А do-нотация всего лишь удобный способ представления цепочек >>= и >>.

Я думаю, разруха^Wимперативный подход в головах. Можно в do-нотации видеть императивный код, хотя это, на самом деле, функциональная композиция. Разные теории могут давать разные модели одного и того же. Но, конечно же, не все модели одинаково удобны. :)

>Каждый раз, когда я использую монаду State в хаскелле - я использую императивный подход,

Монада как раз изолирует изменение с целью создать чистоту. В то время как императивное изменение - имеет целью создать сайд эффект. Монада стейт "добавляет параметр" в функцию и "передает дополнительный результат как параметр" в следующую. Это "эмуляция" императивщины.

Грубо говоря сахар для

(b, s1) = f(a, s)
(c, s2) = g(x, s1)
(d, s3) = z(y, s2)

> Там именно, что сишная структура и набор функций, которые реализуют определенную абстракцию (в данном случае монаду).

Там набор буков. :-D

>Ну тогда ты бы должен был понять, к чему приводит твой код.

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

>Кухонным ножом можно зарезать - запретим ножи?

Нет - будем делать столовые ножи с выемкой для балансировки, по модели боевого ножа, добавим гарду. Будем нарезать колбаску самурайским мечем.

Как только ищобретут нож которым можно нарезакть колбаску но нельзя зарезать - ты удивишься куда денуться обычные ножи из обихода.

>Объект - это то, что обладает identity и состоянием. Яйцо - это реальный предмет, а число - это абстракция (просто по определению).

В каком месте ты здесь дал определение?

Дай определение почему A -> B а С -> !B.

Ты сказал. А -> B потому что A -> B, а С -> !B по определению.

Гениальное определение!

>Объект - это то, что обладает identity и состоянием. Яйцо - это реальный предмет, а число - это абстракция (просто по определению).

Ну так дай ты определение императивного подхода. А то пока не видно ни одного.

> [code] Prelude> let func x = if x > 0 then putStrLn "Yes" else putStrLn "No" Prelude> func 4 Yes Prelude> func (-5) No [/code]

> ? :)

> case-statement в do? - это не конструкция? Только не надо говорить, что это синтаксический сахар, я это и так знаю.

Case — это тоже не императивный оператор (или что имеется ввиду под "конструкцией"?), это расширенная if. Вспомните определение модуля: можно случай x = 0 вынести в третью ветку определения, вот и будет вам case.

> Ну если следовать их логике, а она у них какая-то ну совсем противоречивая, ты тоже не прав.

Почему? В смысле что не так описано в Википедии?

> Потому как в например, common lispe вообще нет statements - однако это императивный язык (там есть setf и прочие императивные прелести).

Lisp — это вообще отдельная тема :) Языки лисп-семейства не императивны по сути (равно как и не строго функциональны).

>Я уже говорил, что с таким подходом, мы приходим к тому, что у нас императивными будут только assembler да машинный код.

Я еще в начале треда сказал что ассемблер - самый идеоматический императивный язык и сказал причину этого - фоннейман. А ты мне уже три страницы доказываешь то что я сказал в самом начале.

> Проблема в том, что функциональный тип (первый прарметр функции fmap) сам является... ФУНКТОРОМ, и как любой уважающий себя функтор оперделен как instance типкласса Functor, и, забегая вперед, как instance типкласса Monad (!!!). Но это тема отдельного разговора.

Лучше сходи на http://migmit.vox.com где Miguel Mitrofanov приводит простенький код на хаскеле (инспирированный ТК), который вроде бы требует template virtual и следовательно, не ложится легко на С++. Переформулируй его пример в некатегорных понятиях и расскажи тут (сам мигель говорит, что потерял интерес).

З.Ы. Подозреваю, что от ТК пользы намного меньше, чем от топологии например. Вот ты исписал много букаф -- а где профит? ( Профитом могло бы быть организация двух вроде бы разных конструкций языка программирования как частных случаев одной и т.д.)

рекомендую посмотреть на FranTK --- http://www.dcs.gla.ac.uk/~meurig/research/icfp.pdf

Вполне наглядная выгода от использования теории категорий.

> Подозреваю, что от ТК пользы намного меньше, чем от топологии например.

А какой профит от топологии?

>> Подозреваю, что от ТК пользы намного меньше, чем от топологии например.

>А какой профит от топологии?

По идее это математический механизм для анализа конструкций типа транспортных развязок.

Да, но как это соотносится с темой беседы?

>Да, но как это соотносится с темой беседы?

На ЛОР-е бесполезно искать смысл даже начиная со второй страницы.

Фи. Чтобы в это воткнуть Маклейна читать не надо. Достаточно одной таблЭтки: http://en.wikibooks.org/wiki/Haskell/Category_theory

> А какой профит от топологии?

Унификация доказательств (из матанализа в основном) и выяснение, какие посылки были существенны, а какие -- нет.

Теорию категорий практически не знаю, посему сразу предупреждаю, что наезд на нее будет несколько предвзятым.

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

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

Кстати (насчет пользы от топологии) -- гомотопические и гомологически группы позволяют различить 2 пространства, т.е. доказать их негомеоморфность, что напрямую очень затруднительно -- как вы будете доказывать, что *не* существует гомеоморфизма?

Потом на этой основе можно сделать исчерпывающую классификацию простанств... правда в многомерном случае все это уперлось в сложность.