List & Set Object II for MMF2

I’ve got a little distracted with my main projects and have started making another extension.

I wrote for MMF1.5 an object that allows you to do simple set operations, by the request of KenSingleton. I managed to completely ignore how appropriate his username was at the time. I wonder if it was on purpose?

Anyway, a recent thread on the MMF forums was this: Somebody has a list of 60 elements, and then wanted to find the sum of each subset of 8 elements of it. This is fairly difficult to do in MMF really. What is more, they attempted to do it with ordered sub-lists instead of unordered subsets.

So it gave me an idea: How about a new set object? And in fact, sometimes order is useful, and duplicated items are useful, so lets make it a list object.

At the centre of the idea is that you can have a list, add elements to it, extract elements, adjoin lists and so forth. That is all straight forward and easy. Let us call these types of lists concrete lists. (Except you can’t actually to anything more than add and extract elements at the moment. That is just because none of the problems I’ve wanted to solve have required anything more than this yet!)

But the object also supports virtual lists. These are lists which are, in some way, not just a list of elements in memory.

The first type implemented is K-Subsets. You can assign a set-ID to the first K-Subset of another set (either concrete or virtual) and then iterate through its K-sized subsets. It doesn’t duplicate the lists at all: It basically just creates a mask and iterates through that. So if you are looking at singleton sets of {1,2,3} and then you change the set to  {1,2,5}, then the singleton{3} will change to the singleton {5}. The virtual list really represents a transform on another set. It is more of a description on how to generate a list rather than a list in itself. All virtual lists are like this.

If you try and add an element to a K-Subset, it will automatically change it into a concrete list. But then you can’t go to the next subset. I might change it in future so you can’t do this. I’m not so sure yet.

The second type of virtual list is an equation list. This is just a function (of the element number n), input as a string. So for instance, if you put in “n*n” then you get the (infinite) list [0,1,4,9,16,…]. You can still do things like iterate through the K-Subsets of this set.

The third type is a bit different because you don’t use it directly, but it is prime list, which is just a list of prime numbers. It is automatically stored in the list “<prime>” (and also “<primes>” and “<p>”) and it caches the results.

As an example of what you can do at the moment, you can look at the size 2 subsets of <prime>, look at their sum (which there is an expression for) and then keep looking at the next subset until the sum is equal to the even number of your choice, thus looking at Goldbach’s Conjecture.

Another type is a mapping. This is based upon another list, but each element of the new list is the value of the element in the old list with a function applied to it. For instance, if we generated the list [0,1,2,3,…] using the equation list type, we could define a new list to be this with the operation “x*x” applied to it (x is the value of the element, n is its index) to get the list [0,1,4,9,…].

A variation of this is the mapped pair. You specify a formula and two lists, and the newly defined list gets the value of its element from applying the formula to the two corresponding elements in the old list. For instance, if you had the lists [1,2,3] and [4,5,6] and you specified the equation “a+b” (a is the element from list 1, b the element from list 2. n is still the index ) then you get the list [5,7,9].

The final implemented type is the subsequence list. Given a list, this allows you to define a new list which is a subsequence of the old list. For instance, if you had the list [0,1,2,3,4,5,…] you could specify the new list with the equation “2*n”. This gives you the set [0,2,4,6,…]. So the n-th element of this list in the 2n-th element of the old list.

So to put the last three into symbols:

  • For a given function f and set B, define the mapped list A(n) := f(B(n))
  • For a given function f and set B, define the subsequence list A(n) := B(f(n))
  • For a given function f of two parameters, and sets B and C, define the mapped pair A(n) := f( B(n) , C(n) )

Let us say we want to find the sums of consecutive prime numbers. You can do it as follows: Make the set ShiftedPrimes by taking <primes> and defining the subsequence with the equation “n+1”. That gives you the set [3,5,7,…]. Now you can use the mapped pair type to add each element of <primes> to the corresponding ShiftedPrimes. We could store this set as, say, sum. We should have that sum is [5, 8, 12, 18, 24, 30, …].

In future, I might want to add the following sets if there is demand for it:

  • Unions, Intersections, Symmetric Differences can be virtual sets (but can also be concrete if all underlying sets are finite).
  • Something along the lines of A(n) = f( … , A(n-2) , A(n-1) , A(n) , A(n+1) , A(n+2) , … ). Obviously this is effort to evaluate, and must be cached.
  • Filtered List. So the list of elements that some condition is true on.

So at the moment it isn’t massively useful in that you can’t check if elements are in a list or count the number of times it is an element of it. But I’m not programming that unless somebody is going to use it, as for my purposes it wasn’t required Obviously any set which is derived, in any way, from an equation defined list cannot do things like determine if an element is a member of it unless some sort of clue is given (for instance, that it is an increasing or decreasing set).

I’m quite excited by this because, for mathematical purposes, it is really quite powerful! You can manipulate data in this much easier than you ever have been in MMF before. (At least, most types of data. Ini++ will still be better at some types.)

Each element in a list can either be a string or a double. They are completely convertible but if it is added as a double it really is stored like that. This is in order to avoid constant converting.


Update: Please see this post.


2 Responses to List & Set Object II for MMF2

  1. Pingback: Iterating Subsets of a Specific Size « Jack's Personal Blog

  2. Pingback: List & Set Object interacts with default MMF List Control « Jack's Personal Blog

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: