Is the Y Combinator a left fold or a right fold?

Question

The Y combinator (from the wikipedia article) is defined as:

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

so when we call Y on 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)

The repetition results in this:

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

Because this expansion is over a unary function, I can't tell if this is a left fold or a right fold.

My understanding of a left fold is that it resembles this (with a binary function f):

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

Whereas a right fold over binary function f looks like this:

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

I would imagine that any unary function, however, would look the same as a left-fold or right-fold expansion:

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

Is this correct? If not, does the Y combinator expand into a left-fold or a right-fold?

user5536315 · Accepted Answer · 2020-01-17 12:49:31Z

Fixed point combinators like Y merely enable anonymous recursion. What you do with this recursion is totally up to you. You can define both a left associative fold and a right associative fold with it. I hope you don't mind me illustrating this in 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

Collectives™ on Stack Overflow

Is the Y Combinator a left fold or a right fold?

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related