Paste # 89800: Y combinator in typed/racket

PasteRack.org

Paste # 89800
2015-05-19 04:56:36

Fork as a new paste.
Paste viewed 504 times.
Tweet
Embed:
<link type="text/css" rel="stylesheet" href="http://pasterack.org/scribble.css"/><link type="text/css" rel="stylesheet" href="http://pasterack.org/racket.css"/><link type="text/css" rel="stylesheet" href="http://fonts.googleapis.com/css?family=Droid+Sans+Mono"/><div style="font-family:'Droid Sans Mono',monospace;background-color:transparent"><ol start="0" style="font-size:70%;color:#A0A0A0"><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta">#lang</span><span class="hspace"> </span><span class="RktMeta"></span><a class="RktModLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/index.html"><span class="RktSym">typed/racket</span></a><span class="RktMeta"></span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"> </span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/special-forms.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fprims..rkt%29._define%29%29">define</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">Y</span><span class="RktMeta"></span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"></span><span class="hspace">  </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktCmt">;(ann</span><span class="hspace"> </span><span class="RktCmt">;;</span><span class="hspace"> </span><span class="RktCmt">Not</span><span class="hspace"> </span><span class="RktCmt">needed</span><span class="RktMeta"></span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"></span><span class="hspace">    </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/special-forms.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fprims..rkt%29._~ce~bb%29%29">λ</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym">f</span><span class="RktPn">)</span><span class="RktMeta"></span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"></span><span class="hspace">      </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym">f</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">f</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktMeta"></span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"></span><span class="hspace">   </span><span class="RktMeta"></span><span class="RktCmt">;(All</span><span class="hspace"> </span><span class="RktCmt">(A)</span><span class="hspace"> </span><span class="RktCmt">(→</span><span class="hspace"> </span><span class="RktCmt">(Rec</span><span class="hspace"> </span><span class="RktCmt">r</span><span class="hspace"> </span><span class="RktCmt">(→</span><span class="hspace"> </span><span class="RktCmt">r</span><span class="hspace"> </span><span class="RktCmt">A))</span><span class="hspace"> </span><span class="RktCmt">A)))</span><span class="hspace"> </span><span class="RktCmt">;;</span><span class="hspace"> </span><span class="RktCmt">Not</span><span class="hspace"> </span><span class="RktCmt">needed</span><span class="RktMeta"></span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"></span><span class="hspace">   </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/special-forms.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fprims..rkt%29._ann%29%29">ann</a></span><span class="RktMeta"></span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"></span><span class="hspace">    </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/special-forms.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fprims..rkt%29._~ce~bb%29%29">λ</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym">z</span><span class="RktPn">)</span><span class="RktMeta"></span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"></span><span class="hspace">      </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/special-forms.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fprims..rkt%29._~ce~bb%29%29">λ</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym">f</span><span class="RktPn">)</span><span class="RktMeta"></span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"></span><span class="hspace">        </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym">f</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/special-forms.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fprims..rkt%29._~ce~bb%29%29">λ</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym">x</span><span class="RktPn">)</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktPn">(</span><span class="RktPn">(</span><span class="RktSym">z</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">z</span><span class="RktPn">)</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">f</span><span class="RktPn">)</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">x</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktMeta"></span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"></span><span class="hspace">    </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/type-ref.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fbase-types-extra..rkt%29._.Rec%29%29">Rec</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">r</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/type-ref.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fbase-types-extra..rkt%29._~e2~86~92%29%29">→</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">r</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/type-ref.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fbase-types-extra..rkt%29._.All%29%29">All</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym">T</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">R</span><span class="RktPn">)</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/type-ref.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fbase-types-extra..rkt%29._~e2~86~92%29%29">→</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/type-ref.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fbase-types-extra..rkt%29._~e2~86~92%29%29">→</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/type-ref.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fbase-types-extra..rkt%29._~e2~86~92%29%29">→</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">T</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">R</span><span class="RktPn">)</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/type-ref.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fbase-types-extra..rkt%29._~e2~86~92%29%29">→</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">T</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">R</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/type-ref.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fbase-types-extra..rkt%29._~e2~86~92%29%29">→</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">T</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">R</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktMeta"></span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"> </span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/special-forms.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fprims..rkt%29._~3a%29%29">:</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">factorial</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/type-ref.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fbase-types-extra..rkt%29._~e2~86~92%29%29">→</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/type-ref.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fbase-types..rkt%29._.Real%29%29">Real</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/type-ref.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fbase-types..rkt%29._.Real%29%29">Real</a></span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktMeta"></span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/special-forms.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fprims..rkt%29._define%29%29">define</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">factorial</span><span class="RktMeta"></span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"></span><span class="hspace">  </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym">Y</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/special-forms.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fprims..rkt%29._~ce~bb%29%29">λ</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktPn">[</span><span class="RktSym">recursive-factorial</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/special-forms.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fprims..rkt%29._~3a%29%29">:</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/type-ref.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fbase-types-extra..rkt%29._~e2~86~92%29%29">→</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/type-ref.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fbase-types..rkt%29._.Real%29%29">Real</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/type-ref.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fbase-types..rkt%29._.Real%29%29">Real</a></span><span class="RktPn">)</span><span class="RktPn">]</span><span class="RktPn">)</span><span class="RktMeta"></span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"></span><span class="hspace">       </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/special-forms.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fprims..rkt%29._~ce~bb%29%29">λ</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktPn">[</span><span class="RktSym">x</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/special-forms.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fprims..rkt%29._~3a%29%29">:</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/ts-reference/type-ref.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fbase-types..rkt%29._.Real%29%29">Real</a></span><span class="RktPn">]</span><span class="RktPn">)</span><span class="RktMeta"></span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"></span><span class="hspace">         </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktStxLink" data-pltdoc="x" href="http://docs.racket-lang.org/reference/if.html#%28form._%28%28quote._~23~25kernel%29._if%29%29">if</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktValLink" data-pltdoc="x" href="http://docs.racket-lang.org/reference/generic-numbers.html#%28def._%28%28quote._~23~25kernel%29._~3c~3d%29%29"><=</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">x</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktVal">0</span><span class="RktPn">)</span><span class="RktMeta"></span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"></span><span class="hspace">             </span><span class="RktMeta"></span><span class="RktVal">1</span><span class="RktMeta"></span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"></span><span class="hspace">             </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktValLink" data-pltdoc="x" href="http://docs.racket-lang.org/reference/generic-numbers.html#%28def._%28%28quote._~23~25kernel%29._%2A%29%29">*</a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">x</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym">recursive-factorial</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym"><a class="RktValLink" data-pltdoc="x" href="http://docs.racket-lang.org/reference/generic-numbers.html#%28def._%28%28quote._~23~25kernel%29._-%29%29"><span class="nobreak">-</span></a></span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktSym">x</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktVal">1</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktPn">)</span><span class="RktMeta"></span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"> </span></span></li><li><span style="font-family:'Droid Sans Mono',monospace;font-size:125%"><span class="RktMeta"></span><span class="RktPn">(</span><span class="RktSym">factorial</span><span class="RktMeta"></span><span class="hspace"> </span><span class="RktMeta"></span><span class="RktVal">5</span><span class="RktPn">)</span><span class="RktMeta"></span></span></li></ol><p>=></p><blockquote><table style="font-size:90%;table-layout:fixed;width:100%;word-wrap:break-word"><tr><td><p><span class="RktOut">- : Real</span></p></td></tr><tr><td><p><span class="RktRes">120</span></p></td></tr></table></blockquote></div>