Golf my iteration function

5

Here is my ungolfed Ruby code for a function I want to try and golf:

Iter =-> k {
    str = ""
    (0..k).map{|m| str += "-> f#{m} {"}
    str += "f#{k}.times{f1 = f0[f1]};f1"
    (2..k).map{|m| str += "[f#{m}]"}
    eval(str + "}" * (k+1))
}

The best I can do to golf this is essentially shortening variable names, removing spaces, and rearranging the code to reduce the amount of loops:

I=->k{s="f#{k}.times{f1=f0[f1]};f1"
(2..k).map{|m|s+="[f#{m}]"}
(0..k).map{|m|s="->f#{k-m}{"+s+?}}
eval s}

Try it online!

This function can be compacted so that it avoids a lot of defining new functions. You can think of it like this:

$$\operatorname{Iter}(k;f_0,f_1,\dots,f_k)=f_0^{f_k}(f_1)(f_2)(f_3)\dots(f_k)$$

where

$$f^n(x)=\underbrace{f(f(\dots f(}_nx)\dots))$$

denotes function iteration. The types of arguments are given as:

$$\operatorname{Iter}(\text{int};\dots,(\text{int}\mapsto\text{int})\mapsto(\text{int}\mapsto\text{int}),\text{int}\mapsto\text{int},\text{int})$$

That is, the last argument is an integer, and each previous argument maps from T to T, where T is the type of the next argument on the right.

It is true that accepting all arguments at once would allow me to golf the above code further:

I=->k,*a{a[-1].times{a[1]=a[0][a[1]]};(2..k).map{|m|a[1]=a[1][a[m]]};a[1]}

However, the issue is that I need to curry this function. This way, I may treat objects such as

$$\operatorname{Iter}(k)(f_0)$$

as their own object, and thus be able to pass this into Iter(k) to get things such as

$$\operatorname{Iter}(k)(\operatorname{Iter}(k)(f_0))$$

As a specific example of what this function does, we have

\begin{align}\operatorname{Iter}(2)(\operatorname{Iter}(1))(x\mapsto x+1)(2)&=\operatorname{Iter}(1)(\operatorname{Iter}(1)(x\mapsto x+1))(2)\\&=\operatorname{Iter}(1)(x\mapsto x+1)(\operatorname{Iter}(1)(x\mapsto x+1)(2))\\&=\operatorname{Iter}(1)(x\mapsto x+1)(2+1+1)\\&=\operatorname{Iter}(1)(x\mapsto x+1)(4)\\&=4+1+1+1+1\\&=8\end{align}

I'm interested in seeing if this can be golfed down further, with the restriction that the arguments must be curried in the order provided.

Simply Beautiful Art

Posted 2019-06-28T01:00:23.687

Reputation: 2 140

Mind if anyone explain the "unclear" close vote? I really did try my best to explain everything, so if there's any part that's unclear, just ask. – Simply Beautiful Art – 2019-06-28T01:37:29.683

1It's a bit unclear because you have tagged this "tips", but it's written almost like a challenge. I'd remove the tips tag and make it more clearly a challenge. Otherwise, perhaps make it clear that you're looking for golfing tips for this specific program. Your last statement makes us unsure of what you want. – mbomb007 – 2019-06-28T02:47:54.280

1

Not sure if this is what you're looking for, but in J >: is the increment function, and your example I[2][I[1]][->x{x+1}][2] can be written >:^:2^:3 (2). Try it online!. ^: is the power of conjunction, and iteratively applies the verb on its left the number of times specified by the number on its right, with 1 being normal application f(x), 2 being f(f(x), etc.

– Jonah – 2019-06-28T06:17:27.260

@mbomb007 okay, I cleared that part up. – Simply Beautiful Art – 2019-06-28T10:17:20.987

1@lirtosiast Thanks and done – Simply Beautiful Art – 2019-06-28T10:17:54.013

@Jonah interesting syntax, though it seems I'm no longer looking for non-Ruby answers. Am still a bit curious as to how you would write something like I[1][I[2][I[1]]][s][2]. – Simply Beautiful Art – 2019-06-28T10:25:54.383

Apparently with your golfed code (and my solution that improves on your golfed code) hits an infinite loop when you change the last argument to 3 instead of 2... This shouldn't happen, right? Or am I missing something? Try it online!

– Value Ink – 2019-06-29T00:49:46.347

1@ValueInk that's not an infinite loop. The issue there is the end result is 3 times 2^402653191 (3<<402653191) – Simply Beautiful Art – 2019-06-29T01:55:08.173

That definitely means I missed something lol... I thought the output was going to be something closer to, I don't know, 12. – Value Ink – 2019-06-29T01:57:57.620

@ValueInk Let s[n] = n+1. See that I[1][s][n] = 2n and I[1][I[1][s]][n] = n2ⁿ = n<<n. From that point, you can directly compute your example with n = 3; 3.times{n <<= n}... – Simply Beautiful Art – 2019-06-29T02:02:22.313

Erm, miscalculation, it ought to be 3 << 402653211. – Simply Beautiful Art – 2019-06-29T02:10:05.597

Answers

3

Ruby, 94 96 bytes

Using loops to do concatenations that followed such a simple pattern felt cumbersome, so I utilized the creative use of join instead, further golfed by the fact that array*str is equivalent to array.join(str)

+2 bytes to fix a typo I made that just so happened to return the same result on the test example by chance.

I=->k{eval"->f#{[*0..k]*'{->f'}{f#{k}.times{f1=f0[f1]};f1#{"[f#{[*2..k]*'][f'}]"if k>1}"+?}*-~k}

Try it online!

Value Ink

Posted 2019-06-28T01:00:23.687

Reputation: 10 608

Oh wow I never knew you could use array*str in Ruby, and like that! So much to learn... – Simply Beautiful Art – 2019-06-28T22:31:27.563

2

Ruby, 87 bytes

I=->k{eval ("->f%d{"*-~k+"f%d.times{f1=f0[f1]};f1"+"[f%d]"*~-k+?}*-~k)%[*0..k,k,*2..k]}

Try it online!

G B

Posted 2019-06-28T01:00:23.687

Reputation: 11 099