Как реализовать вариадическую чистую функцию без классов типов?

Question

[thewizardplusplus]

Суть задачи в следующем. Я хочу создать вариадическую функцию создания списка/массива:

list(1)(2)(3)(4)(5)() === [1, 2, 3, 4, 5]

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

sum(1)(2)(3)(4)(5)() === 1 + 2 + 3 + 4 + 5 === 15

Вообще, решение для Haskell я нашёл (stackoverflow.com/questions/3467279/how-to-create-...):

class SumRes r where
    sumOf :: Integer -> r

instance SumRes Integer where
    sumOf = id

instance (Integral a, SumRes r) => SumRes (a -> r) where
    sumOf x = sumOf . (x +) . toInteger

sumOf 1 4 7 10 2 5 8 22 == 59

Но оно использует классы типов. Мне же нужны простые лямбда-функции.

Классы типов нужны в Haskell, так как это статически строго типизированный язык. Предположим же, что у нас язык динамический - JavaScript. Следовательно, по идее, реализовать это должно быть возможно без классов типов (точнее симулировать их работу через условия и проверку типов аргументов). Но я, к сожалению, никак не придумаю, как же это сделать.

Основные ограничения:

• чистота функции - никаких ни внешних, ни внутренних переменных-аккумуляторов быть не должно, важно решение именно в терминах чистых лямбда-функций, т. е. без наличия хранимого состояния;
  
• арность функции (и всех, ей возвращаемых) должна быть 1 (т. е. они должны принимать только 1 аргумент).
  

Фактически, я хочу преобразовать вышеприведённый код на Haskell в код на JavaScript с учётом ограничений.

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

Помогите, пожалуйста.

Answer 1

[thewizardplusplus]

Пока описал задачу, сам понял, как её нужно решать. ))

function add(x) {
	return function(y) {
		return x + y;
	};
}

function sum(a) {
	return function(b) {
		if (b) {
			return sum(add(a)(b));
		} else {
			return a;
		}
	};
}

sum(1)(2)(3)(4)(5)() === 15

function cons(x) {
	return function(y) {
		return [x, y];
	};
}

function list(a) {
	return function(b) {
		if (b) {
			return list(cons(a)(b));
		} else {
			return a;
		}
	};
}

list(1)(2)(3)(4)(5)() === [[[[1, 2], 3], 4], 5]

Update

Скорректированный код для второго случая, возвращающий более каноничный вид списка:

function cons(x) {
  return function(y) {
    return [x, y];
  };
}

function list(a) {
  return function(b) {
    if (typeof b !== 'undefined') {
      if (a instanceof Array) {
          return list(cons(b)(a));
      } else {
          return list(cons(b)(cons(a)('NIL')));
      }
    } else {
      return a;
    }
  };
}

list(1)(2)(0)(4)(5)() === [5,[4,[0,[2,[1,"NIL"]]]]]

Хотя список всё равно создаётся в обратном порядке.

Answer 2

[Юрий Пузыня]

Вы уверены что хотели получить именно такой массив?

По поводу той же суммы дам вам интересную идею на поиграться:

function sum(a) {
  var sum = a;
  
  function _sum(b) {
    if (b === undefined) return sum;
    
    sum += b;
    return _sum;
  }
  
  _sum.toString = function() {
    return sum;
  };
  
  return _sum;
}

sum(1)(2)(3) + sum(2)(2) + sum(sum(1)(2)(3))(4)(5); // 25

Некоторые отличия в этой реализации:
1. Чуть реже создаются новые функции (у вас новая функция появляется при каждом вызове).
2. Не обязателен последний вызов, чтобы получить значение. Т.е. так же есть возможность получить промежуточное значение и продолжить вычисления. Вообще если вы уверены что в операциях будут участвовать только числа, было бы правильнее определить valueOf, но toString универсальнее.
3. Ваша реализация не учитывает sum(1)(2)(0)(3)()

Comments

[thewizardplusplus]

Вы уверены что хотели получить именно такой массив?

Да, я специально назвал вспомогательную функцию cons - по аналогии с Lisp. Фактически, она должна создавать не массивы из двух элементов, а так называемые точечные пары (терминология Lisp). Из них и строится список.

То есть это просто такой способ представления списков. Он удобен, в частности, для реализации самых типовых функций для работы со списками в функциональном программировании - head (взятие головы) и tail (взятие хвоста, т. е. всего, кроме головы) (в терминологии Lisp, соответственно, это CAR и CDR).

Хотя, если честно, конкретно у меня список строится немного не правильно. Во-первых, самая внутренняя пара должна иметь вид [число, NIL], где NIL - некий символ пустого списка. Во-вторых, канонический Lisp-список должен быть вида [1, [2, [3, [4, [5, NIL]]]]], а не то, что получилось. Так что да, над моей функцией ещё надо поработать.

По поводу той же суммы дам вам интересную идею на поиграться

Благодарю, но такой вариант я знаю, и он мне не подходит. Я именно поэтому и написал "Основные ограничения" в конце вопроса. Именно в их удовлетворении и была главная задача.

Ваше решение хранит состояние:

var sum = a;

И меняет его:

sum += b;

Т. о. это уже не чисто функциональный подход. А мне хотелось найти решение именно в терминах чистых лямбда функций арности 1.

[thewizardplusplus]

Ваша реализация не учитывает sum(1)(2)(0)(3)()

Это верно, я написал слишком простое условие. Конечно же там нужно строгое сравнение с undefined, как в вашем примере.