Y combinator: Difference between revisions
Content deleted Content added
m Added missing final "echo()". |
GordonBGood (talk | contribs) →{{header|Ceylon}}: added Chapel language version... |
||
Line 1,946: | Line 1,946: | ||
given Args satisfies Anything[] |
given Args satisfies Anything[] |
||
=> flatten((Args args) => f(y3(f))(*args));</lang> |
=> flatten((Args args) => f(y3(f))(*args));</lang> |
||
=={{header|Chapel}}== |
|||
Strict (non-lazy = non-deferred execution) languages will race with the usually defined Y combinator (call-by-name) so most implementations are the Z combinator which lack one Beta Reduction from the true Y combinator (they are call-by-value). Although one can inject laziness so as to make the true Y combinator work with strict languages, the following code implements the usual Z call-by-value combinator using records to represent closures as Chapel does not have First Class Functions that can capture bindings from outside their scope other than from global scope: |
|||
{{works with|Chapel version 1.24.1}} |
|||
<lang chapel>proc fixz(f) { |
|||
record InnerFunc { |
|||
const xi; |
|||
proc this(a) { return xi(xi)(a); } |
|||
} |
|||
record XFunc { |
|||
const fi; |
|||
proc this(x) { return fi(new InnerFunc(x)); } |
|||
} |
|||
const g = new XFunc(f); |
|||
return g(g); |
|||
} |
|||
record Facz { |
|||
record FacFunc { |
|||
const fi; |
|||
proc this(n: int): int { |
|||
return if n <= 1 then 1 else n * fi(n - 1); } |
|||
} |
|||
proc this(f) { return new FacFunc(f); } |
|||
} |
|||
record Fibz { |
|||
record FibFunc { |
|||
const fi; |
|||
proc this(n: int): int { |
|||
return if n <= 1 then n else fi(n - 2) + fi(n - 1); } |
|||
} |
|||
proc this(f) { return new FibFunc(f); } |
|||
} |
|||
const facz = fixz(new Facz()); |
|||
const fibz = fixz(new Fibz()); |
|||
writeln(facz(10)); |
|||
writeln(fibz(10));</lang> |
|||
{{out}} |
|||
<pre>3628800 |
|||
55</pre> |
|||
One can write a true call-by-name Y combinator by injecting one level of laziness or deferred execution at the defining function level as per the following code: |
|||
{{works with|Chapel version 1.24.1}} |
|||
<lang chapel>// this is the longer version... |
|||
/* |
|||
proc fixy(f) { |
|||
record InnerFunc { |
|||
const xi; |
|||
proc this() { return xi(xi); } |
|||
} |
|||
record XFunc { |
|||
const fi; |
|||
proc this(x) { return fi(new InnerFunc(x)); } |
|||
} |
|||
const g = new XFunc(f); |
|||
return g(g); |
|||
} |
|||
// */ |
|||
// short version using direct recursion as Chapel has... |
|||
// note that this version of fix uses function recursion in its own definition; |
|||
// thus its use just means that the recursion has been "pulled" into the "fix" function, |
|||
// instead of the function that uses it... |
|||
proc fixy(f) { |
|||
record InnerFunc { const fi; proc this() { return fixy(fi); } } |
|||
return f(new InnerFunc(f)); |
|||
} |
|||
record Facy { |
|||
record FacFunc { |
|||
const fi; |
|||
proc this(n: int): int { |
|||
return if n <= 1 then 1 else n * fi()(n - 1); } |
|||
} |
|||
proc this(f) { return new FacFunc(f); } |
|||
} |
|||
record Fiby { |
|||
record FibFunc { |
|||
const fi; |
|||
proc this(n: int): int { |
|||
return if n <= 1 then n else fi()(n - 2) + fi()(n - 1); } |
|||
} |
|||
proc this(f) { return new FibFunc(f); } |
|||
} |
|||
const facy = fixy(new Facy()); |
|||
const fibz = fixy(new Fiby()); |
|||
writeln(facy(10)); |
|||
writeln(fibz(10));</lang> |
|||
The output is the same as the above. |
|||
=={{header|Clojure}}== |
=={{header|Clojure}}== |