🚀 go-pugleaf

In article <2080@druhi.ATT.COM> kam@druhi.ATT.COM (MorrisseyKA) writes:
>	What is the formula for determining the number of LIs needed
>	to reverse a list of length N, using the following definition?
>
>       [ usual definition omitted ]

A logical inference is a succesful unification with the head if a clause.

 append([], L, L)
    requires one logical inference.
 append([X|L1], L2, [X|L3])
    requires one logical inference plus those required for append(L1, L2, L3).

 Writing a(N) for the logical inferences required for append with a first
 argument of length N, we have
    a(0) = 1
    a(N) = 1 + a(N-1)
 so ('trivially')
    a(N) = N+1.


 nairev([], [])
    requires one logical inference.
 nairev([X|Xs], Zs)
    requires one logical inference plus those required for nairev(Xs,Ys),
    plus those required for append(Ys, [X], Zs).

 Writing n(N) for the logical inferences required for reversing a list of N
 elements, we have
    n(0) = 1
    n(N) = 1 + n(N-1) + a(N-1)
         = N+1 + n(N-1)                          since a(N-1) is N
         = N+1 + N + n(N-2)                      expanding n(N-1)
         = N+1 + (N-1)+1 + ... + (2-1)+1 + n(2-2)
         = N+1 +  N      + ... +  2      +  1
         = (N+1)(N+2)/2                              as is well known (:-)

You could do the last bit by induction if you wanted to be rigorous.

In particular, n(30) = 496. 
-- 
Richard Tobin,                           JANET: R.Tobin@uk.ac.ed             
AI Applications Institute,               ARPA:  R.Tobin%uk.ac.ed@cs.ucl.ac.uk
Edinburgh University.                    UUCP:  ...!ukc!ed.ac.uk!R.Tobin