[m-users.] Efficient circular lists in pure Mercury?

[jfondren at minimaltype.com]

Howdy,

Advent of Code is a yearly contest that takes place during Advent and
that poses programming puzzles with Christmas themes. The contest isn't
very serious (it's first to get the answer regardless of method), but
it's good fun.

2018's day 9 puzzle benefits a lot from a circular list, or at least a
normal list if some extra pointers are maintained to parts of the list.

The puzzle's described here: https://adventofcode.com/2018/day/9

If you want to try this puzzle without being spoiled further, you might
want to stop here.

Without a login you can't see what the puzzle inputs are, or what part 2
involves (a lot of the fun from these puzzles is coding with an eye for
surprises in part 2; will you have solved it automatically, or will you
need a completely different solution?), but the game description and the
example inputs should be enough to work with my solutions here:

   $ ./day9 30 37305
   30 players; last marble of 37305 points -> high score of 1356365

I have two Mercury solutions that differ in their data structures. One
uses my attempt at a pure Mercury 'circular list':

   :- type cons(T)
       --->    nil
       ;       cons(
                   prev :: int,
                   this :: T,
                   next :: int
               ).

   :- type circle(T)
       --->    circle(
                   cells :: array(cons(T)),
                   fill :: int,
                   current :: int
               ).

Which uses indexes into a growable array instead of pointers. I make no
effort to reclaim gaps in the array that appear as cells are deleted,
which is good enough for this task.

The other solution uses an actual circular list with pointers, doing it
all in C:

   :- pragma foreign_decl("C", "
   #include <stdlib.h>
   struct DLL_cons {
       int car;
       struct DLL_cons *next;
       struct DLL_cons *prev;
   };
   ").

The C solution (circular_list.m) beats the pants out of the
indexes-into-an-array solution (circle.m), with an Ada solution (using
Doubly_Linked_Lists) for reference:

| Speed | Part1 | Language | Variant         | Runtime  | MaxRSS   |
|-------|-------|----------|-----------------|----------|----------|
|    1x |       | Ada      |                 | 12.49 ms | 3.5 MB   |
| 3.76x |       | Mercury  | circle.m        | 46.95 ms | 52.2 MB  |
| 2.61x |       | Mercury  | circular_list.m | 43.9 ms  | 43.9 MB  |
|-------|-------|----------|-----------------|----------|----------|
| Speed | Part2 | Language | Variant         | Runtime  | MaxRSS   |
|-------|-------|----------|-----------------|----------|----------|
| 26.9x |    1x | Ada      |                 | 330.1 ms | 200.6 MB |
|  211x | 8.14x | Mercury  | circle.m        | 2636 ms  | 540.6 MB |
| 35.13 | 1.29x | Mercury  | circular_list.m | 438.8 ms | 265.6 MB |

I have two question:

1. Do you recommend some other way to implement circular lists, or a
data structure suitable for this task?

2. How bad is circular_list.m? I thought it didn't even have any
uniqueness protections, but in some simple tests I'm prevented from
reusing intermediate states.

Cheers,
Julian