Custom order in order_by

Help!
1

Hello,

I created a nested list of pairs, where each pair has an index and value. The index is “indented” based on nesting level. For example:

item(1, i1).
item(2.1, i2.1).
item(2.2, i2.2).
item(3, i3).

I’d like to retrieve them by custom order, i.e. 1, 2.1., 2.2., 3, however, order_by retrieves it as 1, 3, 2.1, 2.2 …

Edit:

I guess what happens here is that i have numbers 1 and 3, and compounds 2.1. and 2.2 and ordering of ‘.’ is after numbers, but, somehow, i want it to use the first arg and second arg in the ‘.’ pair for ordering.

Is there a simple way to achieve a “natural” custom ordering by “indent”

thank you,

Dan

2

If you are using library(solution_sequences), keep in mind that that is using findall/3 and sort/4, then member/2. You can do this explicitly (instead of using order_by/2) and replace the call to sort/4 with your specialized sorting.

Next thing: you have in the first argument of item/2 in your example “numbers”, but those are actually integers and floats. Normally, those are compared according to the standard order of terms, and really, they should sort as expected. Here:

?- sort(0, @=<, [1, 2.1, 2.2, 3], Sorted).
Sorted = [1, 2.1, 2.2, 3].

But the second argument of item/2 from your example is not valid Prolog, unless you have somehow redefined the operators. In other words, your example is not reproducible; you need to provide a minimal reproducible example that includes whatever operators you might have defined.

The solution to your problem might involve a custom comparison predicate and predsort/3, but lets wait until you show the rest of your code.

3

Hi Boris,

Many thanks.

The example is a bit contrived.

What i actually did was to create a dot via atomic_list_concat/2, as i traverse a nested structure, something like this:

X=1, Y=1, atomic_list_concat([X, '.', Y], Term),

Not noticing that i am actually creating something that looks like a float, but actually is an atom.

The dot is merely a way to indicate “indenting” nesting, and can be exchanged for any other symbol:

I now wonder to use float as a means for generating nested, with the decimal dot indeed moved for each level … perhaps that’s the easiest way to get things in standard order.

Wonder if there is a way to translate an atom to a float

Edit: looks like atom_number/2 also works with float

Dan

4

Without going into whatever else you are doing, yes, there are many ways to do that. One obvious choice is atom_number/2. Here it is (stuffed inside a maplist so that I don’t have to type 4 different queries):

?- maplist(atom_number, ['1.1', '-3', '0.3e-4', '22r7'], Numbers).
Numbers = [1.1, -3, 3.0e-5, 22r7].

You see here a float, a negative integer, a float in “scientific notation”, and a rational.

5

I overlooked that the nesting can be arbitrariliy deep, so i could end up with:

1
2.1
2.1.1
2.1.2
2.2
3
these aren’t float anymore.

But, if i keep the first “decimal” point only, the ordering would still work …
1
2.1
2.11
2.12
2.2
3

Dan

6

Take a look at three things.

  1. The sort/4 predicate. In particular, it takes a list in the first argument; you still need to know how the term you are sorting is nested. Not sure if that works for your use case.
  2. The predsort/3 predicate. There you can do whatever you feel like. Just remember that if two terms compare equal, you will lose one of them. There is a trick where you make sure that equivalent elements do not compare equal with your comparison predicate, but it is a bit of a hack.
  3. This is probably the cleanest solution if the first option doesn’t work for you: write a predicate that creates a key for your elements that sorts correctly using the standard order of terms.

For the last option, there is a short example in the docs for keysort/2.

7

thanks.

I will look into this. I guess currently the nested structure is “context free” i.e. I have no access to the higher level nestings – only the last two – i guess i could pass along the path and use this to create a key for sorting.

8

The second and third option above are equivalent really. Those are two different approaches to the same problem. This SO Q/A goes a bit into it (it is a bit of a rabbit hole though, in terms of why the question was asked and why it was answered… if you want to understand, you’d have to read the question, all the answers, and probably follow the links… not sure if it is worth your time).

Similarly, first and third option are also equivalent. Read the docs to sort/4 and keysort/2, it is all written in there, in a fashion.

9

Sorry for the multiple replies. So actually, there is a very simple solution to this. Do not make an atom; just keep the list of integers as they are. That should sort correctly with the standard order of terms. So instead of 2.1.1 use [2, 1, 1], instead of 3.1 use [3, 1] and so on. This will sort correctly with sort/2, sort/4, msort/2, keysort/2…

I will leave the rest of my replies above for posterity. I think we have a great example of the XY problem and for some reason I found those delightful.

10

Great. thank you.

To avoid dealing with custom sorting, I redid the code a bit and now retrieve by sorted index, using between/3.

This now retrieves in a sorted manner each nested list item, but there is, naturally, quite a bit of backtracking for each list item retrieved (each list item has an index 1…list-length stored with it) – i think your solution with lists will be much more efficient.

thanks,

Dan

11

I now redid it again using lists and it works very nicely …

many thanks @Boris

Dan

1 Like