Может ли fix быть хвостовым рекурсивным и, таким образом, выражаться простым l oop? - PullRequest
Новая
       74

Может ли fix быть хвостовым рекурсивным и, таким образом, выражаться простым l oop?

2 голосов
/ 23 января 2020

Я не могу понять, как express fix как хвостовой рекурсивный алгоритм. Или это уже хвост рекурсивный? Я, наверное, переосмысливаю это ... 

const fix = f => x => f(fix(f)) (x); // redundant eta abstraction due to eager eval

const sum = fix(go => acc => ([x, ...xs]) =>
  x === undefined
    ? acc
    : go(acc + x) (xs)) (0);
    
const main = sum([1,2,3,4,5]);

console.log(main); // 15

Я много пробовал, но пока не нашел ничего полезного. Хвостовой рекурсивный алгоритм может быть легко преобразован в стек с безопасностью l oop. Это реальная цель.

1 Ответ

2 голосов
/ 27 января 2020

Я не могу понять, как express fix использовать в качестве хвостового рекурсивного алгоритма.

Сначала преобразуем определение fix в A- нормальная форма . 

// fix :: ((a -> b) -> a -> b) -> a -> b
const fix = f => x => {
    const g = fix(f);
    const h = f(g);
    const y = h(x);
    return y;
};

Затем преобразуйте полученную программу в стиль продолжения . 

// type Cont r a = (a -> r) -> r

// fix :: ((a -> Cont r b) -> Cont r (a -> Cont r b)) -> Cont r (a -> Cont r b)
const fix = f => k => k(x => k =>
    fix(f) (g =>
    f(g)   (h =>
    h(x)   (y =>
    k(y)))));

Теперь fix является хвостовой рекурсивной , Однако, это, вероятно, не то, что вам нужно.

Хвостовой рекурсивный алгоритм может быть легко преобразован в стек, безопасный для l oop. Это реальная цель.

Если все, что вам нужно, это безопасность стека, то вы можете использовать Trampoline монаду. 

// Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ({ bounce: true, func, args });

// Return :: a -> Trampoline a
const Return = value => ({ bounce: false, value });

// trampoline :: Trampoline a -> a
const trampoline = result => {
    while (result.bounce) result = result.func(...result.args);
    return result.value;
};

// fix :: ((a -> Trampoline b) -> a -> Trampoline b) -> a -> Trampoline b
const fix = f => Bounce(x => f(fix(f))(x));

// id :: a -> a
const id = x => x;

// reachable code
console.log("begin"); // open the console in your browser

// infinite loop
trampoline(fix(id)(0));

// unreachable code
console.log("end");

Однако для этого потребуется также изменить определение sum. 

// Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ({ bounce: true, func, args });

// Return :: a -> Trampoline a
const Return = value => ({ bounce: false, value });

// trampoline :: Trampoline a -> a
const trampoline = result => {
    while (result.bounce) result = result.func(...result.args);
    return result.value;
};

// fix :: ((a -> Trampoline b) -> a -> Trampoline b) -> a -> Trampoline b
const fix = f => Bounce((...args) => f(fix(f))(...args));

// _sum :: (Number, [Number]) -> Trampoline Number
const _sum = fix(recur => (acc, xxs) => {
    if (xxs.length === 0) return Return(acc);
    const [x, ...xs] = xxs;
    return recur(acc + x, xs);
});

// sum :: [Number] -> Trampoline Number
const sum = xxs => _sum(0, xxs);

// result :: Number
const result = trampoline(sum([1,2,3,4,5]));

// 15
console.log(result);

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

...