Pull to refresh

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

Reading time5 min
Views26K
Доброго дня, друзья!

Тема функционального программирования раскрыта на Хабре весьма неплохо, есть целая куча статей посвященных λ-исчислению, числам Чёрча и подобным темам, так что ничего нового я не открою, зато мы напишем одну бесполезную и крайне неэффективную программу.

Для того, чтоб жизнь мёдом не казалась, ограничим себя небольшим подмножеством языка JavaScript, а именно, будем использовать только анонимные функции от одного аргумента. Больше нам ничего не потребуется (ну почти).

Начнем с определения факториала, и посмотрим, что нам понадобится в процессе решения задачи:

var fact = function (n) {
  if (n === 0) return 1;
  return n * fact(n - 1);
};


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

Готовы?

Начнем с простого, с логических значений True, False и функции If. True и False представлены каррированными функциями двух аргументов осуществляющими выбор первого либо второго аргумента. True выбирает первый аргумент, а False — второй. If принимает три аргумента, логическое значение, ветку then и ветку else.

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);
    }
  };
};


Можно побаловаться в консоли выполняя код типа:

console.log(If(True)('foo')('bar'));
console.log(If(False)('foo')('bar'));


Дальше нам потребуются числа. Множество натуральных чисел можно получить определив значение числа НОЛЬ и операцию ПЛЮС_ОДИН. Числа Чёрча, грубо говоря, представляют собой функции двух аргументов, применяющие первый аргумент ко второму n раз, где n — это соответствующее натуральное число.

var Zero = function (f) {
  return function (x) {
    return x;
  };
};

var Succ = function (n) {
  return function (f) {
    return function (x) {
      return f(n(f)(x));
    };
  };
};


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

var IsZero = function (n) {
  return n(function (x) { 
    return False;
  })(True);
};


Проверьте как работают числа:

Succ(Succ(Succ(Zero)))(function (x) { return x + 1; })(0);
console.log(If(IsZero(Zero))('zero')('not zero'));
console.log(If(IsZero(Succ(Zero)))('zero')('not zero'));


Как видите, к нулю трижды прибавилась единица, а предикат корректно распознает переданное число.

Теперь, когда у нас есть все натуральные числа определим функцию умножающую два числа, результат умножения — это функция, которая n раз по m раз применяет свой аргумент.

var Mul = function (n) {
  return function (m) {
    return function (f) {
      return n(m(f));
    };
  };
};


Осталось научиться отнимать единицу от числа. Тут все немного сложнее. Идея вычитания состоит в том, что строится пара чисел (n, n — 1) и берется второй элемент пары. Таким образом нам нужно получить конструктор пары, а так же функции получения первого и второго элемента. После чего мы сможем определить функцию получения предыдущего числа.

var Pair = function (a) {
  return function (b) {
    return function (t) {
      return t(a)(b);
    };
  };
};

var Fst = function (p) {
  return p(True);
};

var Snd = function (p) {
  return p(False);
};

var Pred = function (n) {
  return function (s) {
    return function (z) {
      return Snd(n(function (p) {
        return Pair(s(Fst(p)))(Fst(p)); 
      })(Pair(z)(z)));
    };
  };
};


Поиграемся с парами и вычитанием:

Fst(Pair('foo')('bar')); // => "foo"
Snd(Pair('foo')('bar')); // => "bar"
Pred(Succ(Succ(Zero)))(function (x) { return x + 1; })(0); // => 1


Казалось бы, все уже готово и можно реализовать факториал:

var fact = function (n) {
  return If(IsZero(n))(Succ(Zero))(Mul(n)(fact(Pred(n))));
};


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

var fact = function (n) {
  return If(IsZero(n))(Succ(Zero))(function (x) {
    return Mul(n)(fact(Pred(n)))(x);
  });
};


Теперь функция работает корректно:

fact(Succ(Succ(Succ(Zero))))(function (x) { return x + 1; })(0); // => 6


Осталась последняя проблема. Вначале я обещал использовать только анонимные функции, а тут мы видим рекурсивный вызов по имени fact. Нужно от него избавиться и в этом нам поможет Y-комбинатор. Объяснять принцип его работы я не буду, на эту тему есть статьи и на Хабре и вне пределов Хабра. Рекомендую например вот эту блогозапись. Y-комбинатор в аппликативном языке выглядит так:

var Y = function (f) {
  return function (x) {
    return x(x);
  }(function (x) {
    return function (y) {
      return f(x(x))(y);
    };
  });
};


Проверить корректность его работы можно так:

Y(function (f) {
  return function (n) {
    return If(IsZero(n))(Succ(Zero))(function (x) {
      return Mul(n)(f(Pred(n)))(x);
    });
  };
})(Succ(Succ(Succ(Zero))))(function (x) { return x + 1; })(0); // => 6


Теперь подставим факториал в Y-комбинатор и получим конечный вариант:

var fact = function (x) {
  return x(x);
}(function (x) {
  return function (y) {
    return function (f) {
      return function (n) {
        return If(IsZero(n))(Succ(Zero))(function (x) {
          return Mul(n)(f(Pred(n)))(x);
        });
      };
    }(x(x))(y);
  };
});


Для большего удобства определим функции NatToChurch и ChurchToNat:

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);
};


Теперь можно ставить эксперименты в консоли:

ChurchToNat(fact(NatToChurch(5))); // => 120


Последний шаг, сделать все подстановки и получить финальную функцию:

Осторожно, очень много функций
var fact = function (x) {
  return x(x);
}(function (x) {
  return function (y) {
    return function (f) {
      return function (n) {
        return function (p) { 
          return function (t) {
            return function (e) {
              return p(t)(e);
            }
          };
        }(function (n) {
          return n(function (x) { 
            return function (x) { 
              return function (y) {
                return y;
              }; 
            };
          })(function (x) { 
            return function (y) {
              return x;
            }; 
          });
        }(n))(function (n) {
          return function (f) {
            return function (x) {
              return f(n(f)(x));
            };
          };
        }(function (f) {
          return function (x) {
            return x;
          };
        }))(function (x) {
          return function (n) {
            return function (m) {
              return function (f) {
                return n(m(f));
              };
            };
          }(n)(f(function (n) {
            return function (s) {
              return function (z) {
                return function (p) {
                  return p(function (x) { 
                    return function (y) {
                      return y;
                    }; 
                  });
                }(n(function (p) {
                  return function (a) {
                    return function (b) {
                      return function (t) {
                        return t(a)(b);
                      };
                    };
                  }(s(function (p) {
                    return p(function (x) { 
                      return function (y) {
                        return x;
                      }; 
                    });
                  }(p)))(function (p) {
                    return p(function (x) { 
                      return function (y) {
                        return x;
                      }; 
                    });
                  }(p)); 
                })(function (a) {
                  return function (b) {
                    return function (t) {
                      return t(a)(b);
                    };
                  };
                }(z)(z)));
              };
            };
          }(n)))(x);
        });
      };
    }(x(x))(y);
  };
});



Осталось ответить на вопрос «Зачем так делать?». Признаюсь честно, на этот вопрос у меня ответа нет. Всем добра!
Tags:
Hubs:
Total votes 51: ↑51 and ↓0+51
Comments47

Articles