serialiser

rfi-p> 
style lisp
rfi-l> destroy
rfi-l> consult "/home/rfm/RFM/extensions/serialiser.rf"
; Reading file "/home/rfm/RFM/extensions/serialiser.rf" ..
rfi-l> listing
(hn (serialise _l _r)
    (pairlists _l _r _a)
    (arrange _a _t)
    (numbered _t 1 _n) )
(hn (pairlists
     (tup _x | _l)
     (tup _y | _r)
     (tup (pair _x _y) | _a) )
    (pairlists _l _r _a) )
(hn (pairlists (tup) (tup) (tup)))
(hn (arrange
     (tup _x | _l)
     (tree _t1 _x _t2) )
    (partition _l _x _l1 _l2)
    (arrange _l1 _t1)
    (arrange _l2 _t2) )
(hn (arrange (tup) void))
(hn (partition (tup _x | _l) _x _l1 _l2)
    (partition _l _x _l1 _l2) )
(hn (partition
     (tup _x | _l)
     _y
     (tup _x | _l1)
     _l2 )
    (before _x _y)
    (partition _l _y _l1 _l2) )
(hn (partition
     (tup _x | _l)
     _y
     _l1
     (tup _x | _l2) )
    (before _y _x)
    (partition _l _y _l1 _l2) )
(hn (partition (tup) _y (tup) (tup)))
(hn (before (pair _x1 _y1) (pair _x2 _y2))
    (string< _x1 _x2) )
(hn (numbered
     (tree _t1 (pair _x _n1) _t2)
     _n0
     _n )
    (numbered _t1 _n0 _n1)
    (is _n2 (+ _n1 1))
    (numbered _t2 _n2 _n) )
(hn (numbered void _n _n))
rfi-l> style prolog
rfi-p> listing
serialise(L, R) :- pairlists(L, R, A), arrange(A, T), numbered(T, 1, N).
pairlists([X | L], [Y | R], [pair[X, Y] | A]) :- pairlists(L, R, A).
pairlists([], [], []).
arrange([X | L], tree[T1, X, T2]) :- partition(L, X, L1, L2),
                                     arrange(L1, T1),
                                     arrange(L2, T2).
arrange([], void).
partition([X | L], X, L1, L2) :- partition(L, X, L1, L2).
partition([X | L],
          Y,
          [X | L1],
          L2) :- before(X, Y), partition(L, Y, L1, L2).
partition([X | L],
          Y,
          L1,
          [X | L2]) :- before(Y, X), partition(L, Y, L1, L2).
partition([], Y, [], []).
before(pair[X1, Y1], pair[X2, Y2]) :- string<(X1, X2).
numbered(tree[T1, pair[X, N1], T2], N0, N) :- numbered(T1, N0, N1),
                                              N2 is +(N1, 1),
                                              numbered(T2, N2, N).
numbered(void, N, N).