Является ли Y Combinator левой или правой складкой? - PullRequest
Новая
       101

Является ли Y Combinator левой или правой складкой?

1 голос
/ 17 января 2020

Y комбинатор (из статьи Википедии ) определяется как:

Y = \f.(\x.f(x x)) (\x.f(x x))

, поэтому, когда мы вызываем Y на g: 

Y g = (\f.(\x.f(x x)) (\x.f(x x))) g 

= (\x.g(x x)) (\x.g(x x))

= g((\x.g(x x)) (\x.g(x x)))

= g (Y g)

Повторение приводит к следующему: 

Y g = g(Y g) = g(g(Y g)) = g(...g(Y g)...)

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

Мое понимание левого сгиба состоит в том, что он похож на это (с двоичной функцией f): 

f (f (f (f 1 2) 3) 4) 5)

Тогда как правый сгиб по двоичной функции f выглядит так: 

f 1 (f 2 (f 3 (f 4 5)))

I Однако можно было бы предположить, что любая унарная функция будет выглядеть так же, как расширение влево или вправо: 

f (f (f (f (f x))))

Это правильно? Если нет, разворачивается ли Y-комбинатор в левый или правый сгиб?

1 Ответ

4 голосов
/ 17 января 2020

Комбинаторы с фиксированной точкой, такие как Y, просто позволяют анонимную рекурсию. То, что вы делаете с этой рекурсией, полностью зависит от вас. Вы можете определить как левую ассоциативную складку, так и правую ассоциативную складку. Надеюсь, вы не против, чтобы я проиллюстрировал это в Javascript: 

// simplified Y combinator with eta abstraction due to eager evaluation

const fix = f => x => f(fix(f)) (x);

// left fold

const foldl = fix(rec => f => acc => ([x, ...xs]) =>
  x === undefined
    ? acc
    : rec(f) (f(acc) (x)) (xs));
    
// right fold

const foldr = fix(rec => f => acc => ([x, ...xs]) =>
  x === undefined
    ? acc
    : f(x) (rec(f) (acc) (xs)));
    
    
 console.log(
   foldl(x => y => x - y) (0) ([1,2,3])); // -6
   
  console.log(
   foldr(x => y => x - y) (0) ([1,2,3])); // 2
...