5 ms·

Y combinator in Haskell fix :: (a -> a) -> a fix f = f (fix f) Y combinator (with sharing) -- https://hackage.haskell.org/package/base/docs/Data-Functi

Y combinator in Haskell fix :: (a -> a) -> a fix f = f (fix f) Y combinator (with sharing) -- https://hackage.haskell.org/package/base/docs/Data-Function.html#v:fix -- https://stackoverflow.com/questions/53715841/sharing-vs-non-sharing-fixed-point-combinator fix :: (a -> a) -> a fix f = let x = f x in x Y combinator (type level) type Fix :: (Type -> Type) -> Type newtype Fix f = Fix (f (Fix f))

lupire 4y ago
That's a fixed point combinator, not the Y Combinator. https://stackoverflow.com/questions/4273413/y-combinator-in-haskell https://stackoverflow.com/questions/4273413/y-combinator-in-...
philip-b 4y ago
The first example will lead to infinite recursion. There is no base case.
- bidirectional 4y ago
  Under Haskell's evaluation strategy `(fix f)` will not be evaluated until it is used, if the definition of `f` ignores its parameter under some scenario, then evaluation will terminate.
- vq 4y ago
  fix :: (a -> a) -> a fix f = f (fix f) f :: [Int] -> [Int] f xs = 1 : map (*2) xs take 7 (fix f) ==> [1,2,4,8,16,32,64] Looks right to me.
- gpderetta 4y ago
  I think the trick is that Haskel is lazily evaluated. The Y combinator has a different formulation on strict languages.
- lupire 4y ago
  A general fixed point combinator cannot have a base case; it relies on the parameter to terminate the computation.
tel 4y ago
Much of the point of the Y combinator is the construction of a fixed point operator without appealing to self-definition. Using fix in its own definition violates that, one could say that the recursion arises due to Haskell's recursive bindings. The standard definition in untyped lambda calculus is \f -> (\x -> f (x x)) (\x -> f (x x)) but if we try to give a type to x, let's call it X, we'll see something funny X = i -> o -- we know it's a function type because it's applied X = X -> o -- it's self-applied, so the input must be X X = (X -> o) -> o -- expanding the inner reference X = ((X -> o) -> o) -> o -- oh no Unfortunately, this won't type in Haskell because `type X = (X -> o) -> o` is invalid and would loop the type checker. We must introduce an explicit indirection. This explicitness forces us to control if and when this type expands and prevents the checker from looping. newtype Loop a = Loop (Loop a -> a) defer :: (Loop a -> a) -> Loop a defer f = Loop f apply :: Loop a -> (Loop a -> a) apply (Loop f) = f This type is exactly a solution to `X = (X -> o) -> o` but with the recursion explicitly tagged, as x :: Loop o apply x :: Loop o -> o apply x . defer :: (Loop o -> o) -> o So now we can type the type Y combinator without utilizing Haskell's self-referential bindings. y f :: (a -> a) -> a y f = apply half half where half :: Loop a -- the type of X half x = defer (f (apply x x)) -- i.e. \x -> f (x x) Still pretty concise compared to Go! (Probably saw this first at https://r6.ca/blog/20060919T084800Z.html https://r6.ca/blog/20060919T084800Z.html)
dmead 4y ago
pretty sure the point of the Y combinator is to server as a definition for recursion in languages that do not support it natively (ie, lambda calc) if you're making a recursive function call then you're just making something that kinda looks like Y but isn't. FWIW i don't think you can write Y in haskell, it would not make much sense. according to this thread you can't, because it doesn't type check. https://stackoverflow.com/questions/4273413/y-combinator-in-haskell https://stackoverflow.com/questions/4273413/y-combinator-in-...

lupire 4y ago

That's a fixed point combinator, not the Y Combinator. https://stackoverflow.com/questions/4273413/y-combinator-in-haskell https://stackoverflow.com/questions/4273413/y-combinator-in-...

philip-b 4y ago

The first example will lead to infinite recursion. There is no base case.

bidirectional 4y ago
Under Haskell's evaluation strategy `(fix f)` will not be evaluated until it is used, if the definition of `f` ignores its parameter under some scenario, then evaluation will terminate.
vq 4y ago
fix :: (a -> a) -> a fix f = f (fix f) f :: [Int] -> [Int] f xs = 1 : map (*2) xs take 7 (fix f) ==> [1,2,4,8,16,32,64] Looks right to me.
gpderetta 4y ago
I think the trick is that Haskel is lazily evaluated. The Y combinator has a different formulation on strict languages.
lupire 4y ago
A general fixed point combinator cannot have a base case; it relies on the parameter to terminate the computation.

tel 4y ago

Much of the point of the Y combinator is the construction of a fixed point operator without appealing to self-definition. Using fix in its own definition violates that, one could say that the recursion arises due to Haskell's recursive bindings. The standard definition in untyped lambda calculus is \f -> (\x -> f (x x)) (\x -> f (x x)) but if we try to give a type to x, let's call it X, we'll see something funny X = i -> o -- we know it's a function type because it's applied X = X -> o -- it's self-applied, so the input must be X X = (X -> o) -> o -- expanding the inner reference X = ((X -> o) -> o) -> o -- oh no Unfortunately, this won't type in Haskell because `type X = (X -> o) -> o` is invalid and would loop the type checker. We must introduce an explicit indirection. This explicitness forces us to control if and when this type expands and prevents the checker from looping. newtype Loop a = Loop (Loop a -> a) defer :: (Loop a -> a) -> Loop a defer f = Loop f apply :: Loop a -> (Loop a -> a) apply (Loop f) = f This type is exactly a solution to `X = (X -> o) -> o` but with the recursion explicitly tagged, as x :: Loop o apply x :: Loop o -> o apply x . defer :: (Loop o -> o) -> o So now we can type the type Y combinator without utilizing Haskell's self-referential bindings. y f :: (a -> a) -> a y f = apply half half where half :: Loop a -- the type of X half x = defer (f (apply x x)) -- i.e. \x -> f (x x) Still pretty concise compared to Go! (Probably saw this first at https://r6.ca/blog/20060919T084800Z.html https://r6.ca/blog/20060919T084800Z.html)

dmead 4y ago

pretty sure the point of the Y combinator is to server as a definition for recursion in languages that do not support it natively (ie, lambda calc) if you're making a recursive function call then you're just making something that kinda looks like Y but isn't. FWIW i don't think you can write Y in haskell, it would not make much sense. according to this thread you can't, because it doesn't type check. https://stackoverflow.com/questions/4273413/y-combinator-in-haskell https://stackoverflow.com/questions/4273413/y-combinator-in-...