7 ms·
The Y Combinator in Go with generics
- skybrian 4y agoNice! Once you read the explanation, the explicit types make this more understandable and usable than the more usual definition. It seems no more difficult than constructing a Promise from a callback in JavaScript. (It's still pretty opaque without reading the explanation, though.)
- nemo1618 4y agoGood example of pounding a square peg into a round hole!
- deleted 4y ago[deleted]
- unsignednoop 4y ago
- mgdlbp 4y agoAh, now I get the name, a company/function applied to a company/function to make it self-sustaining/referential.
- asplake 4y agohttps://en.m.wikipedia.org/wiki/Fixed-point_combinator#Fixed-point_combinators_in_lambda_calculus https://en.m.wikipedia.org/wiki/Fixed-point_combinator#Fixed...
- Iceland_jack 4y agoY 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 agoThat'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 agoThe first example will lead to infinite recursion. There is no base case.
- bidirectional 4y agoUnder 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 agofix :: (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 agoI think the trick is that Haskel is lazily evaluated. The Y combinator has a different formulation on strict languages.
- lupire 4y agoA general fixed point combinator cannot have a base case; it relies on the parameter to terminate the computation.
- tel 4y agoMuch 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)
- RcouF1uZ4gsC 4y agoIn C++23 you can do recursive lambdas by deducing this auto gcd = [](this auto self, int a, int b) -> int { return b == 0 ? a : self(b, a % b); } std::cout << gcd(20, 30) << std::endl;
- dataangel 4y agowhy isn't it "auto this"? That that would make it <type> <name> like everything else in the language
- kaashif 4y agoThe name is "self" not "this". "this" is a keyword indicating it's the explicit object parameter, it's not even actually a type. C++ seems to be trying to maximise confusion these days.
- jcelerier 4y agostruct foo { void bar(int a, int b) { auto lambda = [&] (auto this self) { this->compute(); }; } void compute(); }; if the variable name was "auto this" you wouldn't be able to refer to "compute" through the "this" of the parent class here
- tromp 4y agoY combinator in obfuscated C [1][2] [1] https://www.ioccc.org/2014/wiedijk/prog.c https://www.ioccc.org/2014/wiedijk/prog.c [2] https://www.ioccc.org/2014/wiedijk/hint.html https://www.ioccc.org/2014/wiedijk/hint.html
- khaledh 4y agoI admire how someone passionate about a subject can provide in-depth explanation of _how_ that thing works. But to me, I still have absolutely no idea _why_ or _when_ I would need to apply this (even after reading the original post[0]). A motivating practical example would go a long way as an introduction before getting into the nitty-gritty details. [0] https://eli.thegreenplace.net/2016/some-notes-on-the-y-combinator/ https://eli.thegreenplace.net/2016/some-notes-on-the-y-combi...
- mseepgood 4y agoIt's a plaything, it's not meant to be applied in the real world. It's like asking for a "motivating practical example" for a quine.
- grumpyprole 4y agoKnowledge of the Y-combinator helps avoid making your language divergent (sometimes desirable), disallowing explicit recursion is not enough! The typed lambda calculus uses static types to prevent the Y-combinator and give a sound logic for proofs.
- dataangel 4y agoStatic types doesn't seem sufficient? Typed languages have no problem expressing passing functions as parameters. Where does it break when you apply static types?
- saghm 4y agoI think it's because the y-combinator needs to be passed to itself as an argument, and it's hard to come up with a static type for a function where one of the parameters is the type itself.
- octachron 4y agoThe Y-combinator require (equi)recursive types for the intermediary step `x x` where `x` has type `('a -> 'b as 'a) -> 'b` using OCaml notation.
- aryamaan 4y agoToday I learnt Y Combinator has some meaning outside of what I knew so far.
- deleted 4y ago[deleted]
- deleted 4y ago[deleted]
- lukehoban 4y agoFun! Reminds me of a little tangent I went down when I realized the untyped lambda calculus could be embedded within the single Go type `type V func(v V) V`, including a Y Combinator, church numerals and factorial function with no values other than instances of type V. https://medium.com/@lukeh/untyped-lambda-calculus-church-numerals-and-the-y-combinator-in-go-e123d076f99d https://medium.com/@lukeh/untyped-lambda-calculus-church-num... https://gist.github.com/lukehoban/0ec2a3dbbb9a13338d338a3fbbb039ff#file-lambda_test-go https://gist.github.com/lukehoban/0ec2a3dbbb9a13338d338a3fbb...