Extending Compose block

I am not sure which category this should fall, so pardon me in advance if it's the wrong category.

In snap, there are so many amazing library functions one can find, so maybe what I am trying to discuss here may already have been covered and I had not had the opportunity to discover it.

So let's start with compose, in it's mathematical term is simply the composition of two functions: f and g
compose (f, g) (x) = f ( g(x) ) would take an input x, run through g and then to f to get the answer, and it has been provided by the compose block, which is extreme simple yet powerful.

But I found that I needed something a little extra, for example, the following scenario: I would like to have a function f which accepts two inputs, but g is a function which accepts one input, and the composition of f and g would accept two inputs, I would call such a composition a lift op. As follows:
lift (f, g) (x, y) = f(g(x), g(y))
The name lift (I originally called it my compose. :smiling_face:) is not originated by me, I searched on the internet, to see whether there is a pattern for this kind of things, of course, many many...
Or even in general, f is an n-ary function, and g1...gn are all unary function.
lift(f g1,..., gn) (x1, ..., xn) = f(g1(x1), ..., gn(xn))

So it's beneficial to implement such a block. I will share with you my implementation of lift2, and I tried to implement the general lift which would accept n, f, gs... as input, but I didn't go very far. I also will share with you a block to illustrate the application.

First, the lift2 implementation, which is extremely easy, thanks to the amazing power of snap.

lift2 definition - 2
(updated: Sept 30, fixed errors in the comment of the lift2 definition)

When only one g is selected, it will do: lift(f, g) (x, y) = f(g(x), g(y))

Now the application:

merge sort a list of lists according to the length of each sublists

The above is simply saying: Merge sort a list of lists according the length of each sublists.

Welcome any comments and discussions.

Yeah, the trouble with the Internet is that it keeps rubbing in how little I know about anything.

You shouldn't need n as an input. You can


and call f with the result of the MAP as its input list.

It's awesome, I agree, that there's an algebra of functions. It just shows the power of the idea of abstraction.

PS I get the hint in your example! I haven't said anything in that other thread recently because I decided I have to write bottom-up mergesort myself to get a real grip on the issue. :~)

You are so humble, I know you have a huge mine of deep knowledge. You have my ultimate respect!

Thanks, that's beautiful - I have been trying to make it work, but still having trouble. As a matter of fact, I tried map but didn't think your way, now I can see it's so obvious from this angle. The reason I am keeping n is to have the possibility of specifying one g for n-ary f, so I could do lift (n, f, g) (x1, ..., xn) = f(g(x1), ... g(xn)).

Here is what I have tried so far:


Forgot to point out, the resulting lift function is also an n-ary function.
lift(n, f, g1, g2, ..., gn) (x1, ..., xn) = f(g1(x1), ..., gn(xn))
Unfortunately, as of now, the above does not work, could you take a look at it and help me to figure out what's the reason it's not working?

This shows failed call:

However, during debug, the map shows up correctly:

lift-map portion is working
That's before it's fed into the 2-ary f function.

I am puzzled.

Yes, I love the power of abstraction.

For the last week, I tried many different ways of implementing the merge sort, all of them work now. (I think I made 3 different variants). Of course, I tried to be functional, and I tried to use library functions as much as I could, so I didn't have to reinvent the wheels. I was excited when I found out the reshape function. I think I glanced through before in the manual, but never really paid attention. Until I wanted to reimplement merge sort from inside out (or bottom up, your terminology), ie, start with singletons, and merge them successively. Mind you, my own variants are not as fast as the library version, but that's not the point of the exercises. I was really trying to learn snap. Of course, other variants of my reimplementation does not use reshape, it works just fine as well. After I discussed with you, I did rewrite another variant using the original reshape, but this way will only work on atomic list, it's actually very exciting, and this version is considerably faster.

Coming from Scala, and with the super easy way of making blocks in snap, I made lots of blocks look alike Scala. I was hesitant of sharing, as I don't want others to think that I don't like snap - on the contrary, I love it, I love the simplicity and power of snap, yet full of possibilities of creating new things. I changed some blocks (mostly one line to make it look like Scala) simply for myself to easy to understand. It revealed in merge sort block that I built. But lift2 is easy enough to fix as it's very short.

Upon some further investigation, I think I am uncovering some further problems.

Something is not right - troublesome behavior

What I am expecting xs to be the input, the first item is a list of list(a, b), and second input is the list of list(1, 2), hum... but the result is surprising. zip was even worse. I changed to my own reshape++... still the inputs is treated in a weird way...

You have CALL F INPUT LIST: and then a ring. INPUT LIST has to be followed by a list! You have to put the unringed MAP (which provides a list) in the INPUT LIST slot, and ringify the entire CALL F with parameter XS.

Always think about domain and range, the 2nd and 3rd most important words in computer science (after abstraction). The domain of F is a set of n values provided by calling a G on each X. The range of LIFT is functions from X values onto whatevers. And so on.

Notice you said the input. That ring expects one input, a list of X values. But also you seem to be mapping the identity function over something; why?

I am testing why it's not working.
I am expecting the length would match List(a, b) as the first input, and rank would match list(1, 2) as the second input...

But you're running a block outward mergesort script pic which means that it takes exactly one input! Also, since you gave an explicit formal parameter to the block, Snap! does not substitute actual arguments into empty slots in the body.

Something is not right - troublesome behavior 2

I am getting somewhere. xs is the input list... that's why I am testing...

What I really want a variable input lists...

Oh! You want "input name list:"! Sorry, no such animal. But you can


and then map over each of them separately.

So my original implementation is really working... I was stuck on the inputs... as long as I specified my inputs as ONE list of values (xs) in the domain of gs... it's fine. I had trouble, I thought I could specify xs as a variable inputs... Thanks for the hint on one-input...

Something is not right - troublesome behavior 3

Something is not right - troublesome behavior 4

Yay!!

Is it not possible to extend the ring definition to include variable input?

Alternatively:
Is there a workaround that you could see that result function from lift would be able to accept variable input instead of one input and one has to specify as a list of those inputs...

Another related question, if I am doing partial application or currying an n-ary function, I really want to get a new function with n-1, n-2, ..., 1 input, instead of a single input as a list ...

(partial app) f(x1, ..., xt) where t < n, can be constructed as f_new(x_(t+1), ..., xn) = f(x1, ..., xt, x_(t+1), ..., xn), here x1, ..., xt are fixed input to f

Yeah, you may have to use the new metaprogramming features to build exactly what you want. Same for the question about variadic rings.

I will try, thanks for the suggestions.

I still need to work out a solution involving metaprogramming, thanks for the suggestion. Metaprogramming facility is really powerful, I spent a day yesterday on trying to find the index of a block, and I made lots of progress. I found your reference of deep index in the manual, I generalize it to deep index a sublist inside a list, and it's working as well - this may solve the problem of ambiguity of replacement, if two blocks having the input of 90, one is degree, the other is number of steps, you really only want to replace the 90 associated with turning, you can find the sublist location, and replace that 90 instead. In a recent snapcon2022 talk, someone was asking you about this exact question. I also made a deep index which can find all the locations of the item (including sublists)., I am really trying to solve this problem: what if I want to replace a block of codes by another block of codes inside your block. - Maybe we could have another discussion under metaprogramming?

However, I woke up today and thought about an easier solution to our current problem.

First, take a look at the following:

general lift solution

What's under the hood is this:

It will unarify any variadic input into a single input of a list, here is the definition, I love how easy and simple snap is, it's almost like magic. :slight_smile:
unarify definition
Basically it's doing this: (x1, x2, ..., xn) => List[x1, x2, ..., xn] => feed into unary function such as lift...

Using this method, we can rewrite the original solution for the sorting - that's where all this got started:

You can compare this with the solution in the very fist post using a customized lift2 function.

A little too magic for me to understand; how did you make a variadic upvar slot?

Not so sure I understand your question here, but I will explain one more time.

The lift block I am trying to implement was hoping to accept variadic input (really should match the number inputs required by f in the composition), except, until yesterday, I only succeeded to the point of accepting one input, and to achieve that, I have to cheat - ie, make all the inputs into a list of all the inputs. In the midst of trying, it occurs to me if I could somehow accept a variable input, and turn it into a list, and compose it with the previous lift implementation, that will work perfectly, it did not occur to me until this morning that accept variable inputs and turning into a list in built into snap automatically when you chose the arguments as multi-input...
That's where the unarify function comes from, I chose to use ( args... ) as the name, it's almost like the conventional function call... (x1, x2, ..., xn) => List(x1, ..., xn), now the later list is exactly what my lift function is expecting.
Remember I had trouble of understanding why my lift function was not working, since I was feeding x1, ..., xn as individual input, but only x1 was recognized by the lift function, after feeding through unarify, x1, ..., xn can be correctly recognized by my lift function...or I have to manually pack List(x1, ..., xn) and feed into lift.

However, as a comparison function to feed into merge sort, one has to feed a binary function, not a unary function who accepts a tuple as input, therefore, it's important to be able to get the correct number of inputs. unarify is the obvious solution here. Basically, as I mentioned, it's compose (lift, unarify) to get the correct solution.
unarify (n => 1), lift (1=>m => n)=>1 result: (n=>n)=>1

Unless I am not understanding your question correctly.