hyper-abstracted R contest

[gusl]


## `*` is the hyper of `+`, `^` is the hyper of `*`
> hyper <- function(fn) function(a,b) Reduce(fn, rep(a,b))

> compose <- function(fn1,fn2) function(x) fn1(fn2(x))

> hyperoperation <- function(n) Reduce(compose,listRep(hyper,n))(`+`)


('rep(obj,n)' and 'listRep(obj,n)' just return a list containing 'obj' n times. I had to invent 'listRep' for technical reasons, namely passing closures to 'rep' returns an error: "object of type 'closure' is not subsettable")



## 'hyper' clearly works:
> multiplication <- hyper(`+`)
> multiplication(2,3)
[1] 6
> exponential <- hyper(hyper(`+`))
> exponential(2,3)
[1] 8
> tetration <- hyper(hyper(hyper(`+`)))
> tetration(2,3) ##2^(2^2)
[1] 16


'compose' also works:

> compose(function(x) x^2, function(x) x+1)(4)
[1] 25


and so does 'hyperoperation', woohoo!

> hyperoperation(1)(2,3)
[1] 6


until R decided to be lame:

> hyperoperation(2)(2,3)
Error: evaluation nested too deeply: infinite recursion / options(expressions=)?
>


But I was impressed that I got this far with R! I suspect I could get further if I learn to use defmacro.

inspi#FF0000 by Scott Aaronson's essay, "Who Can Name the Bigger Number?"

Comments

[wjl.livejournal.com]

woohoo, functional programming! except *real* FPLs actually support recursion :P

P.S. that essay is great!

[gustavolacerda.livejournal.com]

yes it is. As of last week, he's my hero. Check out his other writings: http://www.scottaaronson.com/writings/

Have you seen the Gödel CAPTCHA: http://www.scottaaronson.com/writings/captcha.html

[gustavolacerda.livejournal.com]

R supports recursion:


> fact <- function(n) ifelse(n==1,1,n*fact(n-1))
> fact(7)
[1] 5040


I honestly don't know why it breaks down here.

[wjl.livejournal.com]

my off-the-cuff guess was that it has a far-too-conservative recursion depth limit to cut off "infinite looping". my tongue-in-cheek comment about supporting recursion is just to say that in a functional programming language, such deep recursion is *expected* :) it's really funny to me how some language designers have such a limited idea of how deep recursion can be and still be useful.

[gustavolacerda.livejournal.com]

well...
fact(7) goes to depth 7.

hyperoperation(2) doesn't go that deep.

[wjl.livejournal.com]

maybe it's in listRep?

[gustavolacerda.livejournal.com]

nope. It's not recursive.

[wjl.livejournal.com]

according to my quick and dirty stack depth trace debugging, fact(7) and hyperoperation(2) put the same number of function calls on the stack, so i don't know why one works and the other doesn't. does R handle fact(8)? what about fact(16)?

[gustavolacerda.livejournal.com]

fact(100) works no problem.

[gustavolacerda.livejournal.com]

and here's a really weird error:


> tetration <- hyper(hyper(hyper(`+`)))
> tetration(3,3) ##3^(3^3)
Error: cannot allocate vector of size 492.6 Mb


(this came back after a long time running)

however,
tetration(2,3) ##2^(2^2)
works fast, no problem.

(btw, I have fixed the code to use foldr)

[gustavolacerda.livejournal.com]

um, I think I need to use:

hyper <- function(fn) function(a,b) Reduce(fn, rep(a,b), right=TRUE)

foldr, not foldl.

[wjl.livejournal.com]

i don't see why it shouldn't work with either -- i just tried it in SML and both work fine

[wjl.livejournal.com]

or anyway, neither loops infinitely.. i think hyper is indeed incorrect if it's not a fold right

[gustavolacerda.livejournal.com]

yeah, that's what I was saying.