funcy.rb

I = -> x { x }
C = -> x { -> y { -> z { x[z][y] } } }
T = -> C[I]
K = -> x { -> y { x } }
U = -> f { f[f] }
# I know, this technically isn't the Y combinator,
# and it isn't exactly the Z combinator either (like Y, but for applicative order languages).
Y = -> g { U[-> f { -> x { g[U[f]][x] } } ] }


NOT = -> p -> { -> x { -> y { p[y][x] } } }
AND = -> p -> { -> q { p[q][p] } }
OR  = -> p -> { -> q { p[p][q] } }

TRUE  = K
FALSE = NOT[TRUE]
IF    = I


ZERO = FALSE


IS_ZERO    = -> n { n[-> x { FALSE }][TRUE] }
IS_LEQ     = -> m { -> n { IS_ZERO[SUB[m][n] } }
IS_EQ      = -> m { -> n { AND[IS_LEQ[m][n]][IS_LEQ[n][m]] } }

PAIR = -> x { -> y { -> f { f[x][y] } } }
FST  = -> p { p[TRUE]  }
SND  = -> p { p[FALSE] }


NIL     = -> PAIR[TRUE][TRUE]
IS_NIL  = FST
HEAD    = -> l { FST[SND[l]] }
TAIL    = -> l { SND[SND[l]] }
UNSHIFT = -> l { -> x { PAIR[FALSE][PAIR[x][l]] } }


SUCC    = -> n { -> f { -> x { f[n[f][x]] } } }
SHFTINC = -> p { PAIR[SECOND[p]][SUCC[SECOND[p]]] }
PRED    = -> n { FST[n[SHFTINC][PAIR[ZERO][ZERO]]] }


ADD = -> m { -> n { n[SUCC][m] } }
SUB = -> m { -> n { n[PRED][m] } }
MUL = -> m { -> n { n[ADD[m]][ZERO] } }
POW = -> m { -> n { n[MUL[m]][ONE] } }
MOD =
  Y[-> f { -> m { -> n {
    IF[IS_LEQ[n][m]][
      -> x { # η-expansion to prevent infinite recursion.
        f[SUB[m][n]][n][x]
      }
    ][
      m
    ]
  } } }]

RANGE =
  Y[-> f {
    -> m { -> n {
      IF[IS_LEQ[m][n]][
        -> x {
          UNSHIFT[f[SUCC[m]][n]][m][x]
        }
      ][
        NIL
      ]
    } }
  }]

FOLDL =
  Y[-> f {
    -> l { -> x { -> g {
      IF[IS_NIL[l]][
        x
      ][
        -> y {
          f[TAIL[l]][g[x][HEAD[l]][g][y]
        }
      ]
    } } }
  }]

FOLDR =
  Y[-> f {
    -> l { -> x { -> g {
      IF[IS_NIL[l]][
        x
      ][
        -> y {
          g[f[TAIL[l]][x][g]][HEAD[l]][y]
        }
      ]
    } } }
  }]

MAP =
  -> k { -> f {
    FOLDR[k][NIL][
      -> l { -> x { UNSHIFT[l][f[x]] } }
    ]
  } }

SUM =
  -> l {
    FOLDL[l][ZERO][ADD]
  }

PRODUCT =
  -> l {
    FOLDL[l][ONE][MUL]
  }

REVERSE =
  -> l {
    FOLDL[l][NIL][UNSHIFT]
  }




def to_integer(proc)
  proc[-> n { n + 1 }][0]
end

def to_boolean(proc)
  proc[true][false]
end

def to_array(proc)
  array = []
  until to_boolean(IS_NIL[proc])
    head = HEAD[proc]
    array << head
    proc = TAIL[proc]
  end

  array
end