Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!seismo!mcvax!ukc!its63b!aiva!richard
From: richard@aiva.ed.ac.uk (Richard Tobin,                           JANET: R.Tobin@uk.ac.ed             )
Newsgroups: comp.lang.prolog
Subject: Re: naive reverse
Message-ID: <118@aiva.ed.ac.uk>
Date: Fri, 31-Jul-87 11:24:53 EDT
Article-I.D.: aiva.118
Posted: Fri Jul 31 11:24:53 1987
Date-Received: Sun, 2-Aug-87 09:51:31 EDT
References: <2080@druhi.ATT.COM>
Reply-To: richard@uk.ac.ed.aiva (Richard Tobin)
Distribution: world
Organization: AI Applications Institute, Edinburgh University
Lines: 44
Keywords: lips,benchmark,prolog

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