В рамках чистого ФП функции map и filter реализуются через reduce, так что ваш вопрос сводится к такому: какой класс задач можно решить с помощью свёртки (катаморфизма)? Не претендуя на исчерпывающий и математически точный ответ можно сказать, что одна только свёртка позволяет обрабатывать конечные индуктивные данные. С её помощью можно построить конечный автомат, или автомат с магазинной памятью. Они не эквивалентны машине Тьюринга, но способны вычислять примитивно рекурсивные функции. На вскидку, с помощью reduce и без изменяемых состояний можно построить программу, эквивалентную программе, использующей только цикл for (точнее, foreach, C-шный for это переодетый while). Это хороший и полезный класс программ, гарантирующий тотальность. Для реализации цикла while потребуется ленивый генератор данных для свёртки: анаморфизм. Их композиция — хиломорфизм, уже Тьюринг полна. Повторюсь, все эти рассуждения имеют смысл при отсутствии изменяемого состояния, так как если сворачивающая функция может получить доступ к ссылке на сворачиваемые данные и изменять их на ходу, то это уже не катаморфизм, а бардак. В таком случае ответ на ваш вопрос будет таким: да, свёртка тьюринг-полна, но она тут ни при чём, это просто цикл. Кстати, в С# изменять итератор цикла foreach запрещено на уровне языка.
Увы, о композиции в С-подобном синтаксисе говорить очень неудобно. А рассуждать о её изяществе даже опасно, засмеют и композицию заругают. Недаром у Lisp, Haskell, F# и J такой "странный" синтакис :)
Вот про функторы автор зря начал говорить. В контексте статьи речь идёт о контейнерах. Слово функтор, конечно, красивое, но оно накладывает бОльшие ограничения, чем указано в статье и даёт больше преимуществ, чем в ней указано. Понятно, что это перевод и что из песни слов не выкинешь, но для понимания того как использовать map в JS этот термин и его общность ни к чему. Вот если объяснить как построить reduce а вместе с ним и map для дерева, очереди, объектов (не всяких), или каких-либо других самописных стуктур, тогда становится понятнее зачем может понадобиться этот термин. Впрочем, хорошо что говоря о reduce автор не упоминает катаморфизмы.
А теперь вопрос. Кто должен разруливать все эти риски? Язык? Или это работа программиста?
А кто должен писать тесты? Язык? Или это работа программиста?
Строгая, стройная система типов без «нельзя, но если очень хочется, то можно» даёт возможность использовать системы автоматической генерации тестов, типа QuickCheck, что позволяет упростить работу программиста.
А ещё странно, что ни автор, ни комментаторы не упоминают лекцию Роберта Мартина "The last programming language", в которой эта тема подробнейшим образом освещается. Очень рекомендую её всем интересующимся историей ЯП.
Соглашусь с вами в том, что понимание понятия группы и связанных с ними понятий симметрия и инвариант, не менее важно, чем понимание композиции. Что же, это очень хорошо, что к моноидам можно подойти как со стороны групп, как и со стороны теории категории. И у нас есть выбор своего удобного пути.
Полезно помнить, что отношение порядка определено не на всех множествах. Нельзя сказать, что одна точка в пространстве больше другой, нельзя сравнивать комплексные числа. Когда об этом забывают начинаются священные войны — все правы и никто не прав.
Сравнивая эволюционные ветви, можно обратить внимание на численность представителей вида, семейства или отряда. В этом смысле Земля — планета жуков, а не людей. Мы построили города, а поселились в них тараканы и голуби. В IT-сфере в этом смысле победят не С, не Haskell и не Ruby, а HTML, CSS и плохие программисты, их просто много и они постоянно откуда-то появляются, хватают самый простой для пищеварения язык, что непонятно выплёвывают и пишут, пишут… :) Новые успешные в этом смысле языки появляются вместе с новыми технологиями и новыми потребностями (например, веяниями моды).
Можно сравнить кто кого победит в схватке. Тут на Земле человеку с автоматом нет равных. В программировании во время соревнований сильнейший язык выбрать трудно. Я бы, если мне нужно было выбирать язык для себя, выбрал Haskell или Mathematica :) в первом можно быстро написать мощную и корректную программу, во втором — воспользоваться гигантской базой знаний и гибкостью, унаследованной от Лиспа. Python и R — тоже подходят, но мне они не практически нужны были в моей работе. Новый сильный язык родится тогда, например, когда параллельные вычисления станут формализованы до такой степени, чтобы об этом мог позаботиться компилятор. Мы наблюдали такое, когда родились сборщики мусора — классная история!
Можно сравнивать живучесть. Бактерии термофилы заняли нишу экстремальных температур и ни с кем не конкурируют. Их никто не съест — сварится, а они съедят кого угодно, варёного. Ледяные черви научились жить в снегу, а человек на вездеходе есть повсюду. В программировании такие экстремальные ниши будут появляться всегда. И всегда будут рождаться разновидности FORTH или того же Лиспа, просто в силу простоты реализации и интерпретации. И человек с С (или, возможно, с Rust) тоже будет повсюду.
Наконец, есть долгожители. Это тоже эволюционный успех! Хрящевые рыбы, гаттерии, гинкго и другие представители живой природы, хоть и немногочисленны, пережили массовые вымирания и населяют планету миллионы лет. Лямбда-исчисление, насление Дональда Кнута, а также Лисп, с нами надолго и, похоже, навсегда. И они не просто существуют, они развиваются! Mascyma, Wolfram Mathematica, Maple — это достижения Лиспа и филигранно отточенных алгоритмов! Haskell развивается медленно, и каждый свой шаг обмозговывает, обсуждает, но при этом рьяно ощупывает множество перспективных направлений. Может быть, он эволюционирует и изменится, но идеи, родившиеся благодаря ему, никуда уже не денутся. Именно на Haskell реализованы языки для формального доказательства теорем: Agda, Coq и Idris. Это тоже кусочек будущего.
Сила биосферы Земли в её разнообразии. Если человек, как самый сильный всех победит, ему же хуже будет. То что языков программирования много это очень хорошо, а вот сравнивать их и называть победителя неверно.
Боюсь, что опыт Closure и Emacs вы не учитываете. Попытки построить рефлексию в современных языках показывают, что Лисп нужен и нужен, похоже, будет всегда, как нужна математика.
Вот если бы Брендан Эйх выполнил требования спецификации к языку для Netscape и написал Scheme-подобный язык (да с макросами, и с оптимизацией хвостовой рекурсии...) то масса новичков-программистов не удивлялась бы скобочкам, а бодро изучала SCIP и это, правда, пошло бы им и всем нам на пользу.
Уверяю вас, о Лиспе в том или ином виде, вы будете слышать всегда. Он невероятно живуч. Это ли не победа в эволюционной борьбе?
А разве так страшно? :) Термин моноид мне нравится больше чем полугруппа с единицей. Второй термин сложный (в лингвистическом смысле) — он состоит из двух понятий, каждое из которых требует определения. Более того, полугруппа — тоже сложный термин, наводящий на мысль о том, что же такое группа, а она, увы, определяется вовсе не так просто и несколько уводит в сторону от понятия моноид.
Алгебраическое понимание моноида очень хорошо ложится на принцип декомпозиции и композиции в программировании. Более того, освоив это понятие, становится проще понять смысл категории, как набора объектов и морфизмов образующих моноид (агебраический) по отношению к композиции. И моноид в теории категории определяется естественно, и вполне понятно почему он там так называется.
Наконец, пресловутая монада, при ясном понимании, что такое моноид становится, наконец, просто специальным способом композиции.
Хорошее слово, ёмкое. И означающее что-то одно и фундаментальное. В «полугруппе с единицей» есть что-то неполноценное, и группа-то наполовинку, и единицы могло бы не быть… :)
Перешёл на NixOS c Arch. Полёт нормальный, хотя на взлёте пришлось учиться летать. Для моих задач: Haskell, серфинг, книгописание… работает отлично! Эксперименты с системой и обновление, откаты к стабильным версиям, декларативность конфигурации — полный кайф! Однако, не стал бы сравнивать по гибкости с Gentoo, всё зависит от собственного владения магией nix, nixpkgs или от доброй воли добровольцев, пополняющих каналы (репозиторий). Из минусов — мало документации (после ArchWiki, NixOs Manual — кажется брошюркой с указанием особенностей местных диалектов, но после 8-ми лет с Arch многое умеешь и сам), и малая пользовательская аудитория: возник вопрос — надо лезть в git или читать рассылки. Со сторонними пакетами печаль и магия nix. В общем, моё мнение: этот дистрибутив пока не для ленивых, но направление развития очень хорошее (учтите мою повернутость на Lisp-Haskell :). Это по-настоящему один из концептуальных прорывов в развитии дистрибутивов Linux.
Спасибо, это очень хорошая статья.
Она могла бы быть отличным введением к разделу «Семантика языков программирования» в курсе «Теория ЯП». Теперь, по её прочтении, можно смело рассказывать студентам о том, зачем нужны такие «скучные» вещи, как операционная, аксиоматическая и денотационная семантика; что такое контракты, для чего появился язык Racket и чем силён Eiffel; почему в Haskell и Scala используют такие странные слова, как «моноид», «функтор» или «комонада» (что это не «хипстерская мода» и не умничание, а денотационная семантика соответствующих конструкций, которые можно обнаружить и в других языках); зачем, наконец, имея в своём распоряжении С, С++ и Java, сочинять и развивать новые языки программирования, подчас, странные, «академические» (с плохо проработанной операционной семантикой) или вовсе «фриковские».
Излагаемая в статье проблема — это проблема программирования, а не Computer Science. Параллельно с изобретением новых конструкций и концепций программирования (которое и порождает разнообразие и несогласованность терминов) идёт долгий и сложный процесс открытия этих концепций — поиск их денотационной семантики и доказательство точных связей между разными концепциями. Computer Science — это именно об этом, и там это не «сложнейшая проблема», а вполне решаемая задача.
В рамках чистого ФП функции
mapиfilterреализуются черезreduce, так что ваш вопрос сводится к такому: какой класс задач можно решить с помощью свёртки (катаморфизма)? Не претендуя на исчерпывающий и математически точный ответ можно сказать, что одна только свёртка позволяет обрабатывать конечные индуктивные данные. С её помощью можно построить конечный автомат, или автомат с магазинной памятью. Они не эквивалентны машине Тьюринга, но способны вычислять примитивно рекурсивные функции. На вскидку, с помощьюreduceи без изменяемых состояний можно построить программу, эквивалентную программе, использующей только циклfor(точнее,foreach, C-шныйforэто переодетыйwhile). Это хороший и полезный класс программ, гарантирующий тотальность. Для реализации циклаwhileпотребуется ленивый генератор данных для свёртки: анаморфизм. Их композиция — хиломорфизм, уже Тьюринг полна. Повторюсь, все эти рассуждения имеют смысл при отсутствии изменяемого состояния, так как если сворачивающая функция может получить доступ к ссылке на сворачиваемые данные и изменять их на ходу, то это уже не катаморфизм, а бардак. В таком случае ответ на ваш вопрос будет таким: да, свёртка тьюринг-полна, но она тут ни при чём, это просто цикл. Кстати, в С# изменять итератор циклаforeachзапрещено на уровне языка.Увы, о композиции в С-подобном синтаксисе говорить очень неудобно. А рассуждать о её изяществе даже опасно, засмеют и композицию заругают. Недаром у Lisp, Haskell, F# и J такой "странный" синтакис :)
Вот про функторы автор зря начал говорить. В контексте статьи речь идёт о контейнерах. Слово функтор, конечно, красивое, но оно накладывает бОльшие ограничения, чем указано в статье и даёт больше преимуществ, чем в ней указано. Понятно, что это перевод и что из песни слов не выкинешь, но для понимания того как использовать
mapв JS этот термин и его общность ни к чему. Вот если объяснить как построитьreduceа вместе с ним иmapдля дерева, очереди, объектов (не всяких), или каких-либо других самописных стуктур, тогда становится понятнее зачем может понадобиться этот термин. Впрочем, хорошо что говоря оreduceавтор не упоминает катаморфизмы.А кто должен писать тесты? Язык? Или это работа программиста?
Строгая, стройная система типов без «нельзя, но если очень хочется, то можно» даёт возможность использовать системы автоматической генерации тестов, типа QuickCheck, что позволяет упростить работу программиста.
А ещё странно, что ни автор, ни комментаторы не упоминают лекцию Роберта Мартина "The last programming language", в которой эта тема подробнейшим образом освещается. Очень рекомендую её всем интересующимся историей ЯП.
Сравнивая эволюционные ветви, можно обратить внимание на численность представителей вида, семейства или отряда. В этом смысле Земля — планета жуков, а не людей. Мы построили города, а поселились в них тараканы и голуби. В IT-сфере в этом смысле победят не С, не Haskell и не Ruby, а HTML, CSS и плохие программисты, их просто много и они постоянно откуда-то появляются, хватают самый простой для пищеварения язык, что непонятно выплёвывают и пишут, пишут… :) Новые успешные в этом смысле языки появляются вместе с новыми технологиями и новыми потребностями (например, веяниями моды).
Можно сравнить кто кого победит в схватке. Тут на Земле человеку с автоматом нет равных. В программировании во время соревнований сильнейший язык выбрать трудно. Я бы, если мне нужно было выбирать язык для себя, выбрал Haskell или Mathematica :) в первом можно быстро написать мощную и корректную программу, во втором — воспользоваться гигантской базой знаний и гибкостью, унаследованной от Лиспа. Python и R — тоже подходят, но мне они не практически нужны были в моей работе. Новый сильный язык родится тогда, например, когда параллельные вычисления станут формализованы до такой степени, чтобы об этом мог позаботиться компилятор. Мы наблюдали такое, когда родились сборщики мусора — классная история!
Можно сравнивать живучесть. Бактерии термофилы заняли нишу экстремальных температур и ни с кем не конкурируют. Их никто не съест — сварится, а они съедят кого угодно, варёного. Ледяные черви научились жить в снегу, а человек на вездеходе есть повсюду. В программировании такие экстремальные ниши будут появляться всегда. И всегда будут рождаться разновидности FORTH или того же Лиспа, просто в силу простоты реализации и интерпретации. И человек с С (или, возможно, с Rust) тоже будет повсюду.
Наконец, есть долгожители. Это тоже эволюционный успех! Хрящевые рыбы, гаттерии, гинкго и другие представители живой природы, хоть и немногочисленны, пережили массовые вымирания и населяют планету миллионы лет. Лямбда-исчисление, насление Дональда Кнута, а также Лисп, с нами надолго и, похоже, навсегда. И они не просто существуют, они развиваются! Mascyma, Wolfram Mathematica, Maple — это достижения Лиспа и филигранно отточенных алгоритмов! Haskell развивается медленно, и каждый свой шаг обмозговывает, обсуждает, но при этом рьяно ощупывает множество перспективных направлений. Может быть, он эволюционирует и изменится, но идеи, родившиеся благодаря ему, никуда уже не денутся. Именно на Haskell реализованы языки для формального доказательства теорем: Agda, Coq и Idris. Это тоже кусочек будущего.
Сила биосферы Земли в её разнообразии. Если человек, как самый сильный всех победит, ему же хуже будет. То что языков программирования много это очень хорошо, а вот сравнивать их и называть победителя неверно.
Вот если бы Брендан Эйх выполнил требования спецификации к языку для Netscape и написал Scheme-подобный язык (да с макросами, и с оптимизацией хвостовой рекурсии...) то масса новичков-программистов не удивлялась бы скобочкам, а бодро изучала SCIP и это, правда, пошло бы им и всем нам на пользу.
Уверяю вас, о Лиспе в том или ином виде, вы будете слышать всегда. Он невероятно живуч. Это ли не победа в эволюционной борьбе?
Алгебраическое понимание моноида очень хорошо ложится на принцип декомпозиции и композиции в программировании. Более того, освоив это понятие, становится проще понять смысл категории, как набора объектов и морфизмов образующих моноид (агебраический) по отношению к композиции. И моноид в теории категории определяется естественно, и вполне понятно почему он там так называется.
Наконец, пресловутая монада, при ясном понимании, что такое моноид становится, наконец, просто специальным способом композиции.
Хорошее слово, ёмкое. И означающее что-то одно и фундаментальное. В «полугруппе с единицей» есть что-то неполноценное, и группа-то наполовинку, и единицы могло бы не быть… :)
Поздравляю с окончанием работы над учебником!
Она могла бы быть отличным введением к разделу «Семантика языков программирования» в курсе «Теория ЯП». Теперь, по её прочтении, можно смело рассказывать студентам о том, зачем нужны такие «скучные» вещи, как операционная, аксиоматическая и денотационная семантика; что такое контракты, для чего появился язык Racket и чем силён Eiffel; почему в Haskell и Scala используют такие странные слова, как «моноид», «функтор» или «комонада» (что это не «хипстерская мода» и не умничание, а денотационная семантика соответствующих конструкций, которые можно обнаружить и в других языках); зачем, наконец, имея в своём распоряжении С, С++ и Java, сочинять и развивать новые языки программирования, подчас, странные, «академические» (с плохо проработанной операционной семантикой) или вовсе «фриковские».
Излагаемая в статье проблема — это проблема программирования, а не Computer Science. Параллельно с изобретением новых конструкций и концепций программирования (которое и порождает разнообразие и несогласованность терминов) идёт долгий и сложный процесс открытия этих концепций — поиск их денотационной семантики и доказательство точных связей между разными концепциями. Computer Science — это именно об этом, и там это не «сложнейшая проблема», а вполне решаемая задача.