Вычисление факториала на числах Чёрча

[dvapelnik]

выносим мозг со вкусом!
спасибо за статью

[tagir_valeev]

Интересно, сколько памяти жрёт вычисление факториала 10, например.

[StarMarine]

Насколько я понимаю, это иллюстрирует красоту общей алгебры.

[mayorovp]

Причем тут общая алгебра? Это иллюстрирует красоту лямбда-исчисления.

[xGromMx]

А вот если еще и через arrow function написать, то вообще красотища то какая будет =)

[Keyten]

habrahabr.ru/post/254587 сделал :)

[dginz]

Вопроса «зачем так делать?» нет. Есть вопрос «зачем так делать на языке, который для этого вообще не предназначен?», на haskell'е те же функции выглядели бы сильно проще.

[mayorovp]

Вопрос «зачем так делать на языке, который для этого вообще не предназначен?» в хабе «Ненормальное программирование» задавать неприлично.

PS если на Хаскеле, как и в этой статье, не использовать никаких имен — то получившийся однострочник едва ли будет понятнее приведенного тут кода

[dginz]

Ну, если сравнивать такой код

var NatToChurch = function (n) {
  return n == 0 ? Zero : function (f) {
    return function (x) {
      return f(NatToChurch(n - ChurchToNat(Succ(Zero)))(f)(x));
    };
  };
};

var ChurchToNat = function (n) {
  return n(function (x) {
    return x + 1;
  })(0);
};

с вот таким:

natToChurch 0 = \f -> id
natToChurch n = \f -> f . (natToChurch (n - 1))

churchToNat f = f (+1) 0

то выбор очевиден, несмотря на какие-либо наличия имён

[f0rk]

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

[f0rk]

К ответу на этот вопрос можно подойти с разных сторон.

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

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

fact n = product [1..n]

Или без использования стандартной библиотеки:

fact 0 = 1
fact n = n * fact (n - 1)

Ничего страшного и непонятного в таком коде нет, какие-то подходы могут быть непривычны, но это далеко не rocket science. Подтверждением этому факту служит то, что многие подходы ФП (map, reduce, лябмды, замыкания и т.д.) благополучно переползли в императивные языки и не вызывают проблем у среднестатистического программиста.

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

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

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

[f0rk]

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

Ну обычно тут приводят в пример быструю сортировку (не очень корректный пример, т.к. она не in-place, но оценить выразительность дает):

qsort [] = []
qsort (x:xs) = qsort [a | a <- xs, a <= x] ++ [x] ++ qsort [a | a <- xs, a > x]

Императивный код с циклами и индексами выглядит намного ужаснее.

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

solve x = go where go = fmap ($ go) x          
          
main = print $ solve [const 42      -- константа 42
                    , succ . (!! 0) -- нулевая ячейча + 1
                    , sum . take 2] -- сумма первых двух ячеек

Это валидная программа на haskell, а теперь попробуйте написать то же самое в императивном стиле.

Что касается GUI, тут я соглашусь, задачи программирования GUI очень хорошо мапятся на ООП.

А на том же C++ можно по всякому — и так, и эдак, и с подвывертом.

Можно. Ценой кошмарных синтаксических конструкций.

[f0rk]

Быстрая сортировка ведь есть в стандартной библиотеке C++?

Ну а что вы хотели? Чтобы я привел пример задачи, которую никто еще раньше не решал?

Что касается программы с ячейками — во-первых, я не очень понял задачу.

Реализовать табличный процессор, на входе имеем список констант и функций от этих констант, на выходе тот же самый список, в котором все функции вычислены.

Могу еще пример привести, некогда один хабраюзер решал задачу генерации JSON на C++ http://habrahabr.ru/post/230079/ и даже написал статью на эту тему. Я в комментариях привел пример того, как ту же самую задачу решить на haskell http://habrahabr.ru/post/230079/#comment_7786101. Сравните объем и понятность кода из комментария и код из статьи.

Но ни разу почему-то не пришлось решать задачи, которые я посчитал бы удобным решать на чисто функциональных языках

Может быть дело не в задачах, а в вашем субъективном мнении на счет удобства тех или иных языков? На самом деле, в этом нет ничего плохого, я тоже предпочитаю использовать те инструменты, которые знаю лучше всего, и это к сожалению не haskell. Только это еще не повод отказывать себе в изучении чего-то нового.

[mayorovp]

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

[mayorovp]

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

[f0rk]

Вы действительно не поняли задачу, ну предположим, что синтаксис вам не понятен, но комментарии на русском прочесть же можно?

$ cat q.hs
solve x = go where go = fmap ($ go) x

main = print $ solve [const 42      -- константа 42
                    , succ . (!! 0) -- нулевая ячейча + 1
                    , sum . take 2] -- сумма первых двух ячеек
$ runhaskell q.hs
[42,43,85]

Получится элегантно решить в императивном стиле?

[f0rk]

Всё равно не понял.

Есть такая проблема. У меня, если честно, закончилось желание что либо вам объяснять. Не поняли, ну и ладно, видимо не сильно хотелось.

[alexanderzaytsev]

Тем который получил пиво, вместо заказа на пару месяцев?

[f0rk]

Наверное, тут уместен случай из жизни.

Не понимаю, каким образом он тут уместен?

[f0rk]

Я же вижу, что не всё в этом мире функция.

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

Бывают же константы, бывают процедуры, бывают контейнеры (объекты, структуры и т.п.)

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

[Yuuri]

зачем нужен подход «всё — функция»

Функциональщина этого и не утверждает. Любая функция есть значение, но не любое значение — функция (и не любая конструкция языка — значение).

[mayorovp]

Только потому что первый код был написан неоптимально. Вот этот код

function NatToChurch (n) {
  return n == 0 ? Zero : Succ(NatToChurch(n-1));
}

никак не сложнее своего эквивалента на Хаскеле.

PS только вот почему мы вдруг начали сравнивать удобочитаемость двух исключительно отладочных функций?

[dginz]

Можно и не отладочный, а более уместные:

var True = function (x) { 
  return function (y) {
    return x;
  }; 
};

var False = function (x) { 
  return function (y) {
    return y;
  }; 
};

var If = function (p) { 
  return function (t) {
    return function (e) {
      return p(t)(e);
    }
  };
};

опять же выглядит сильно страшнее, чем

true = \x -> \y -> x
false = \x -> y -> y

if = \cond -> \yes -> \no -> cond yes no

[mayorovp]

Для таких маленьких функций — согласен. Но перепишите определение fact на Хаскель, пожалуйста, тогда и сравним.

PS

var If = function (p) { return p; }

if = \cond -> cond

[f0rk]

if = \cond -> cond

тогда уж:

if = id

Хороший язык, спору нет :)

[mayorovp]

id — это уже стандартная библиотека, ей нельзя пользоваться в этой задаче

[f0rk]

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

[dginz]

Да, конечно, даже

if' = id

(UPD: да, не обновил перед отправкой)

fact получается явно не сложнее:

fact n = isZero (n) (id) (n . (fact $ dec $ n))

[mayorovp]

Автор поста не пользовался именованными функциями. Почему вы считаете, что можете написать одну строку на Хаскеле с их использованием, а потом сравнивать языки?

[dginz]

Как это не пользовался? А все эти succ, pred, isZero и т. д. — не именованные функции?

[mayorovp]

А спойлер в конце статьи вы смотрели?

[f0rk]

На хаскеле не получится тривиально реализовать рекурсию комбинатором, т.к. он типизирован.

[dginz]

Разве?
Вот, почитайте: en.wikibooks.org/wiki/Haskell/Fix_and_recursion

[f0rk]

Это не настоящий комбинатор, хотя и fixpoint. В хаскеле let аналогичен letrec

[f0rk]

Попробуйте реализовать fix только лямбдами, без доп. синтаксиса типа let и использования явной рекурсии.

[dginz]

Согласен, задача непростая, но решается: stackoverflow.com/questions/4273413/y-combinator-in-haskell