Как я могу предотвратить рекурсивную функцию хвоста от изменения порядка List? - PullRequest
Новая
       42

Как я могу предотвратить рекурсивную функцию хвоста от изменения порядка List?

0 голосов
/ 12 мая 2018

Я экспериментирую с функциональным типом List и структурным разделением.Поскольку в Javascript нет оптимизации Tail Recursive Modulo Cons , мы не можем просто написать List комбинаторы, подобные этой, потому что они не безопасны для стека: 

const list =
  [1, [2, [3, [4, [5, []]]]]];


const take = n => ([head, tail]) =>
  n === 0 ? []
    : head === undefined ? []
    : [head, take(n - 1) (tail)];


console.log(
  take(3) (list) // [1, [2, [3, []]]]
);

Теперь я попытался рекурсивно реализовать take tail, чтобы я мог либо полагаться на TCO (все еще неустановленный Promise в Ecmascript), либо использовать батут (опущенв примере, чтобы все было просто): 

const list =
  [1, [2, [3, [4, [5, []]]]]];


const safeTake = n => list => {
  const aux = (n, acc, [head, tail]) => n === 0 ? acc
    : head === undefined ? acc
    : aux(n - 1, [head, acc], tail);

  return aux(n, [], list);
};


console.log(
  safeTake(3) (list) // [3, [2, [1, []]]]
);

Это работает, но новый созданный список находится в обратном порядке.Как я могу решить эту проблему чисто функциональным образом?

Ответы [ 2 ]

0 голосов
/ 13 мая 2018

Лень дает вам хвост рекурсии по модулю минусов бесплатно. Следовательно, очевидное решение состоит в том, чтобы использовать thunks. Тем не менее, мы не хотим, чтобы какой-то вид. Мы хотим, чтобы выражение для слабая голова нормальной формы . В JavaScript мы можем реализовать это, используя lazy getters следующим образом: 

const cons = (head, tail) => ({ head, tail });

const list = cons(1, cons(2, cons(3, cons(4, cons(5, null)))));

const take = n => n === 0 ? xs => null : xs => xs && {
    head: xs.head,
    get tail() {
        delete this.tail;
        return this.tail = take(n - 1)(xs.tail);
    }
};

console.log(take(3)(list));

Есть много преимуществ использования ленивых геттеров:

  1. Обычные и ленивые свойства используются одинаково.
  2. Вы можете использовать его для создания бесконечных структур данных.
  3. Вам не нужно беспокоиться о том, чтобы взорвать стек.

Надеюсь, это поможет.

0 голосов
/ 12 мая 2018

Один из способов предотвратить переворачивание списка - использовать стиль передачи продолжения. Теперь просто положите его на батут на ваш выбор ... 

const None =
  Symbol ()

const identity = x =>
  x

const safeTake = (n, [ head = None, tail ], cont = identity) =>
  head === None || n === 0
    ? cont ([])
    : safeTake (n - 1, tail, answer => cont ([ head, answer ]))

const list =
  [ 1, [ 2, [ 3, [ 4, [ 5, [] ] ] ] ] ]

console.log (safeTake (3, list))
// [ 1, [ 2, [ 3, [] ] ] ]

Вот он на батуте 

const None =
  Symbol ()

const identity = x =>
  x

const call = (f, ...values) =>
  ({ tag: call, f, values })

const trampoline = acc =>
{
  while (acc && acc.tag === call)
    acc = acc.f (...acc.values)
  return acc
}

const safeTake = (n = 0, xs = []) =>
{
  const aux = (n, [ head = None, tail ], cont) =>
    head === None || n === 0
      ? call (cont, [])
      : call (aux, n - 1, tail, answer =>
          call (cont, [ head, answer ]))
  return trampoline (aux (n, xs, identity))
}

const list =
  [ 1, [ 2, [ 3, [ 4, [ 5, [] ] ] ] ] ]

console.log (safeTake (3, list))
// [ 1, [ 2, [ 3, [] ] ] ]
...