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?
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