Hacker News Reader

Comment by Iceland_jack | Hacker News Reader

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

View on HN

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)

That's a fixed point combinator, not the Y Combinator.

https://stackoverflow.com/questions/4273413/y-combinator-in-...

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

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

I think the trick is that Haskel is lazily evaluated. The Y combinator has a different formulation on strict languages.

  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.

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.

A general fixed point combinator cannot have a base case; it relies on the parameter to terminate the computation.

Reply on news.ycombinator.com