4 ms·

> general recursion using the y combinator isn't actually implementable in lisps I think the 'typed' bit is key. You can't implement Y in plain old Haskell be

• Mathnerd314 7y ago
  It's valid Haskell 98 with a type constructor: http://r6.ca/blog/20060919T084800Z.html http://r6.ca/blog/20060919T084800Z.html. But in GHC I think the first code snippet without NOINLINE still crashes, it's a perma-bug: https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/bugs.html#bugs-in-ghc https://downloads.haskell.org/~ghc/latest/docs/html/users_gu... Some type systems do support equi-recursive types without the type constructor, e.g. Whiley (http://whiley.org/2013/04/21/iso-recursive-versus-equi-recursive-types/ http://whiley.org/2013/04/21/iso-recursive-versus-equi-recur...). Maybe there you could implement Y without a type signature and have the recursive type inferred. The main problem is speed. Using the Y combinator is going to mess up whatever code flow analysis the compiler has, unless it's using some cutting edge optimization research that I haven't been able to find.
• carlehewitt 7y ago
  There is a strongly-typed definition of Y here: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3418003 https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3418003
  • ProfHewitt 7y ago
    Some enterprising hacker should research who should be credited for the strongly-typed recursive def of Y.