f0rk Jan 20 2015 at 13:39

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

5 min

26K

Abnormal programming*JavaScript*Functional Programming*

+51

Comments 47

dvapelnik Jan 20 2015 at 13:44

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

tagir_valeev Jan 20 2015 at 14:21

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

StarMarine Jan 20 2015 at 15:16

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

-3

mayorovp Jan 20 2015 at 16:51

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

xGromMx Jan 20 2015 at 17:53

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

Keyten Jun 26 2015 at 12:53

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

dginz Jan 20 2015 at 18:07

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

mayorovp Jan 20 2015 at 18:33

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

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

dginz Jan 20 2015 at 18:51

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

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 Jan 20 2015 at 19:00

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

UFO just landed and posted this here

f0rk Jan 21 2015 at 13:59

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

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

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

fact n = product [1..n]

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

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

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

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

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

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

UFO just landed and posted this here

f0rk Jan 21 2015 at 21:57

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

Ну обычно тут приводят в пример быструю сортировку (не очень корректный пример, т.к. она не 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++ можно по всякому — и так, и эдак, и с подвывертом.

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

UFO just landed and posted this here

f0rk Jan 22 2015 at 06:49

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

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

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

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

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

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

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

UFO just landed and posted this here

mayorovp Jan 22 2015 at 22:08

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

UFO just landed and posted this here

mayorovp Jan 23 2015 at 06:16

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

UFO just landed and posted this here

f0rk Jan 23 2015 at 11:41

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

$ 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]

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

UFO just landed and posted this here

f0rk Jan 24 2015 at 12:37

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

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

UFO just landed and posted this here

alexanderzaytsev Jan 23 2015 at 04:54

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

UFO just landed and posted this here

f0rk Jan 23 2015 at 11:42

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

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

UFO just landed and posted this here

f0rk Jan 23 2015 at 12:04

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

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

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

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

Yuuri Feb 5 2015 at 21:42

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

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

mayorovp Jan 20 2015 at 19:26

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

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

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

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

dginz Jan 20 2015 at 19:35

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

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 Jan 20 2015 at 19:38

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

PS

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

if = \cond -> cond

f0rk Jan 20 2015 at 19:57

if = \cond -> cond

тогда уж:

if = id

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

mayorovp Jan 20 2015 at 20:01

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

f0rk Jan 20 2015 at 20:08

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

dginz Jan 20 2015 at 20:02

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

if' = id

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

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

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

mayorovp Jan 20 2015 at 20:06

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

dginz Jan 20 2015 at 20:29

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

mayorovp Jan 20 2015 at 20:58

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

f0rk Jan 20 2015 at 18:56

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

dginz Jan 20 2015 at 18:57

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

f0rk Jan 20 2015 at 19:01

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

f0rk Jan 20 2015 at 19:03

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

dginz Jan 20 2015 at 19:21

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

Show the best of all time