extra/rosetta-code/y-combinator/y-combinator.factor

   1 ! Copyright (c) 2012 Anonymous
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: combinators kernel math ;
   4 IN: rosetta-code.y-combinator
   5
   6 ! http://rosettacode.org/wiki/Y_combinator
   7
   8 ! In strict functional programming and the lambda calculus,
   9 ! functions (lambda expressions) don't have state and are only
  10 ! allowed to refer to arguments of enclosing functions. This rules
  11 ! out the usual definition of a recursive function wherein a
  12 ! function is associated with the state of a variable and this
  13 ! variable's state is used in the body of the function.
  14
  15 ! The Y combinator is itself a stateless function that, when
  16 ! applied to another stateless function, returns a recursive
  17 ! version of the function. The Y combinator is the simplest of the
  18 ! class of such functions, called fixed-point combinators.
  19
  20 ! The task is to define the stateless Y combinator and use it to
  21 ! compute factorials and Fibonacci numbers from other stateless
  22 ! functions or lambda expressions.
  23
  24 : Y ( quot -- quot )
  25     '[ [ dup call call ] curry @ ] dup call ; inline
  26
  27 ! factorial sequence
  28 : almost-fac ( quot -- quot )
  29     '[ dup zero? [ drop 1 ] [ dup 1 - @ * ] if ] ;
  30
  31 ! fibonacci sequence
  32 : almost-fib ( quot -- quot )
  33     '[ dup 2 >= [ 1 2 [ - @ ] bi-curry@ bi + ] when ] ;
  34
  35 ! Ackermann–Péter function
  36 :: almost-ack ( quot -- quot )
  37     [
  38         {
  39           { [ over zero? ] [ nip 1 + ] }
  40           { [ dup zero? ] [ [ 1 - ] [ drop 1 ] bi* quot call ] }
  41           [ [ drop 1 - ] [ 1 - quot call ] 2bi quot call ]
  42         } cond
  43     ] ;