Academic Tutorials



English | French | Portugese | German | Italian
Home Advertise Payments Recommended Websites Interview Questions FAQs
News Source Codes E-Books Downloads Jobs Web Hosting
Chats

Lisp Programming
Introduction to Lisp
Expressions
Editing, Loading and Compiling LISP Programs
Control Stuctures
Multiple Recursions
Lists
Structural Recursion
Symbols
Examples
Using Lists as Sets

HTML Tutorials
HTML Tutorial
XHTML Tutorial
CSS Tutorial
TCP/IP Tutorial
CSS 1.0
CSS 2.0
HLML
XML Tutorials
XML Tutorial
XSL Tutorial
XSLT Tutorial
DTD Tutorial
Schema Tutorial
XForms Tutorial
XSL-FO Tutorial
XML DOM Tutorial
XLink Tutorial
XQuery Tutorial
XPath Tutorial
XPointer Tutorial
RDF Tutorial
SOAP Tutorial
WSDL Tutorial
RSS Tutorial
WAP Tutorial
Web Services Tutorial
Browser Scripting
JavaScript Tutorial
VBScript Tutorial
DHTML Tutorial
HTML DOM Tutorial
WMLScript Tutorial
E4X Tutorial
Server Scripting
ASP Tutorial
PERL Tutorial
SQL Tutorial
ADO Tutorial
CVS
Python
Apple Script
PL/SQL Tutorial
SQL Server
PHP
.NET (dotnet)
Microsoft.Net
ASP.Net
.Net Mobile
C# : C Sharp
ADO.NET
VB.NET
VC++
Multimedia
SVG Tutorial
Flash Tutorial
Media Tutorial
SMIL Tutorial
Photoshop Tutorial
Gimp Tutorial
Matlab
Gnuplot Programming
GIF Animation Tutorial
Scientific Visualization Tutorial
Graphics
Web Building
Web Browsers
Web Hosting
W3C Tutorial
Web Building
Web Quality
Web Semantic
Web Careers
Weblogic Tutorial
SEO
Web Site Hosting
Domain Name
Java Tutorials
Java Tutorial
JSP Tutorial
Servlets Tutorial
Struts Tutorial
EJB Tutorial
JMS Tutorial
JMX Tutorial
Eclipse
J2ME
JBOSS
Programming Langauges
C Tutorial
C++ Tutorial
Visual Basic Tutorial
Data Structures Using C
Cobol
Assembly Language
Mainframe
Forth Programming
Lisp Programming
Pascal
Delphi
Fortran
OOPs
Data Warehousing
CGI Programming
Emacs Tutorial
Gnome
ILU
Soft Skills
Communication Skills
Time Management
Project Management
Team Work
Leadership Skills
Corporate Communication
Negotiation Skills
Database Tutorials
Oracle
MySQL
Operating System
BSD
Symbian
Unix
Internet
IP-Masquerading
IPC
MIDI
Software Testing
Testing
Firewalls
SAP Module
ERP
ABAP
Business Warehousing
SAP Basis
Material Management
Sales & Distribution
Human Resource
Netweaver
Customer Relationship Management
Production and Planning
Networking Programming
Corba Tutorial
Networking Tutorial
Microsoft Office
Microsoft Word
Microsoft Outlook
Microsoft PowerPoint
Microsoft Publisher
Microsoft Excel
Microsoft Front Page
Microsoft InfoPath
Microsoft Access
Accounting
Financial Accounting
Managerial Accounting
Network Sites


Examples


Previoushome Next






LISP defines a function (nth N L) that returns the N'th member of list L (assuming that the elements are numbered from zero onwards):


A D V E R T I S E M E N T
USER(59): (nth 0 '(a b c d))
				A
				USER(60): (nth 2 '(a b c d))
				C
				We could implement our own version of nth by linear recursion. Given N and L, either L is nil or it is constructed by cons. 
  • Case 1: L is nil.
    Accessing the N'th element is an undefined operation, and our implementation should arbitrarily return nil to indicate this.
  • Case 2: L is constructed by a cons.
    Then L has two components: (first L) and (rest L). There are two subcases: either N = 0 or N > 0:
    • Case 2.1: N = 0.
      The zeroth element of L is simply (first L).
    • Case 2.2: N > 0.
      The N'th member of L is exactly the (N-1)'th member of (rest L).
The following code implements our algorithm:
(defun list-nth (N L)
				  "Return the N'th member of a list L."
				  (if (null L)
					  nil
					(if (zerop N) 
					(first L)
					  (list-nth (1- N) (rest L)))))
				
Recall that (1- N) is merely a shorthand for (- N 1). Notice that both our implementation and its correctness argument closely follow the standard pattern of structural recursion. Tracing the execution of the function, we get:
USER(61): (list-nth 2 '(a b c d))
				 0: (LIST-NTH 2 (A B C D))
				   1: (LIST-NTH 1 (B C D))
					 2: (LIST-NTH 0 (C D))
					 2: returned C
				   1: returned C
				 0: returned C
				C
				
USER(62): (last '(a b c d))
				(d)
				USER(63): (last '(1 2 3))
				(3)
				
Implement your own version of last using linear recursion. You may assume that (last nil) returns nil. Compare your implementation with the standard pattern of structural recursion.

Notice that we have a standard if-then-else-if structure in our implementation of list-nth. Such logic can alternatively be implemented using the cond special form.

(defun list-nth (n L)
				  "Return the n'th member of a list L."
				  (cond
				   ((null L)   nil)
				   ((zerop n)  (first L))
				   (t          (list-nth (1- n) (rest L)))))
				
The cond form above is evaluated as follows. The condition (null L) is evaluated first. If the result is true, then nil is returned. Otherwise, the condition (zerop n) is evaluated. If the condition holds, then the value of (first L) is returned. In case neither of the conditions holds, the value of (list-nth (1- n) (rest L)) is returned. Example: member

LISP defines a function (member E L) that returns non-NIL if E is a member of L.

USER(64): (member 'b '(perhaps today is a good day to die)) ; test fails
				NIL
				USER(65): (member 'a '(perhaps today is a good day to die)) ; returns non-NIL
				'(a good day to die)
				
We implement our own recursive version as follows:
(defun list-member (E L)
				  "Test if E is a member of L."
				  (cond
				   ((null L)          nil)   
				   ((eq E (first L))  t)     
				   (t                 (list-member E (rest L))))) 
				
The correctness of the above implementation is easy to justify. The list L is either constructed by nil or by a call to cons:
  • Case 1: L is nil.
    L is empty, and there is no way E is in L.
  • Case 2: L is constructed by cons
    Then it has two components: (first L) and (rest L). There are two cases, either (first L) is E itself, or it is not.
    • Case 2.1: E equals (first L).
      This means that E is a member of L,
    • Case 2.2: E does not equal (first L).
      Then E is a member of L iff E is a member of (rest L).

Tracing the execution of list-member, we get the following:

USER(70): (list-member 'a '(perhaps today is a good day to die))
				 0: (LIST-MEMBER A (PERHAPS TODAY IS A GOOD DAY TO DIE))
				   1: (LIST-MEMBER A (TODAY IS A GOOD DAY TO DIE))
					 2: (LIST-MEMBER A (IS A GOOD DAY TO DIE))
					   3: (LIST-MEMBER A (A GOOD DAY TO DIE))
					   3: returned T
					 2: returned T
				   1: returned T
				 0: returned T
				T
				

In the implementation of list-member, the function call (eq x y) tests if two symbols are the same. In fact, the semantics of this test determines what we mean by a member:

USER(71): (list-member '(a b) '((a a) (a b) (a c)))
				 0: (LIST-MEMBER (A B) ((A A) (A B) (A C)))
				   1: (LIST-MEMBER (A B) ((A B) (A C)))
					 2: (LIST-MEMBER (A B) ((A C)))
					   3: (LIST-MEMBER (A B) NIL)
					   3: returned NIL
					 2: returned NIL
				   1: returned NIL
				 0: returned NIL
				NIL
				
In the example above, we would have expected a result of t. However, since '(a b) does not eq another copy of '(a b) (they are not the same symbol), list-member returns nil. If we want to account for list equivalence, we could have used the LISP built-in function equal instead of eq. Common LISP defines the following set of predicates for testing equality:

 

Example: nth

(= x y) True if x and y evaluate to the same number.
(eq x y) True if x and y evaluate to the same symbol.
(eql x y) True if x and y are either = or eq.
(equal x y) True if x and y are eql or if they evaluate to the same list.
(equalp x y) To be discussed in Tutorial 4.
 

 

Example: append

LISP defines a function append that appends one list by another:

USER(72): (append '(a b c) '(c d e))
				(A B C C D E)
				
We implement a recursive version of append. Suppose we are given two lists L1 and L2. L1 is either nil or constructed by cons.
  • Case 1: L1 is nil.
    Appending L2 to L1 simply results in L2.
  • Case 2: L1 is composed of two parts: (first L1) and (rest L1). If we know the result of appending L2 to (rest L1), then we can take this result, insert (first L1) to the front, and we then have the list we want.

Formally, we define the following function:

(defun list-append (L1 L2)
				  "Append L1 by L2."
				  (if (null L1)
					  L2
					(cons (first L1) (list-append (rest L1) L2))))
				
An execution trace is the following:
USER(73): (list-append '(a b c) '(c d e))
				 0: (LIST-APPEND (A B C) (C D E))
				   1: (LIST-APPEND (B C) (C D E))
					 2: (LIST-APPEND (C) (C D E))
					   3: (LIST-APPEND NIL (C D E))
					   3: returned (C D E)
					 2: returned (C C D E)
				   1: returned (B C C D E)
				 0: returned (A B C C D E)
				(A B C C D E)
				


Be the first one to comment on this page.




  Lisp Programming eBooks

No eBooks on Lisp Programming could be found as of now.

 
 Lisp Programming FAQs
More Links » »
 
 Lisp Programming Interview Questions
More Links » »
 
 Lisp Programming Articles

No Lisp Programming Articles could be found as of now.

 
 Lisp Programming News

No News on Lisp Programming could be found as of now.

 
 Lisp Programming Jobs

No Lisp Programming Articles could be found as of now.


Share And Enjoy:These icons link to social bookmarking sites where readers can share and discover new web pages.
  • blinkbits
  • BlinkList
  • blogmarks
  • co.mments
  • connotea
  • del.icio.us
  • De.lirio.us
  • digg
  • Fark
  • feedmelinks
  • Furl
  • LinkaGoGo
  • Ma.gnolia
  • NewsVine
  • Netvouz
  • RawSugar
  • Reddit
  • scuttle
  • Shadows
  • Simpy
  • Smarking
  • Spurl
  • TailRank
  • Wists
  • YahooMyWeb

Previoushome Next

Keywords: Lisp string,lisp command,lisp comment,lisp manual,lisp programme,lisp function list,lisp object

HTML Quizzes
HTML Quiz
XHTML Quiz
CSS Quiz
TCP/IP Quiz
CSS 1.0 Quiz
CSS 2.0 Quiz
HLML Quiz
XML Quizzes
XML Quiz
XSL Quiz
XSLT Quiz
DTD Quiz
Schema Quiz
XForms Quiz
XSL-FO Quiz
XML DOM Quiz
XLink Quiz
XQuery Quiz
XPath Quiz
XPointer Quiz
RDF Quiz
SOAP Quiz
WSDL Quiz
RSS Quiz
WAP Quiz
Web Services Quiz
Browser Scripting Quizzes
JavaScript Quiz
VBScript Quiz
DHTML Quiz
HTML DOM Quiz
WMLScript Quiz
E4X Quiz
Server Scripting Quizzes
ASP Quiz
PERL Quiz
SQL Quiz
ADO Quiz
CVS Quiz
Python Quiz
Apple Script Quiz
PL/SQL Quiz
SQL Server Quiz
PHP Quiz
.NET (dotnet) Quizzes
Microsoft.Net Quiz
ASP.Net Quiz
.Net Mobile Quiz
C# : C Sharp Quiz
ADO.NET Quiz
VB.NET Quiz
VC++ Quiz
Multimedia Quizzes
SVG Quiz
Flash Quiz
Media Quiz
SMIL Quiz
Photoshop Quiz
Gimp Quiz
Matlab Quiz
Gnuplot Programming Quiz
GIF Animation Quiz
Scientific Visualization Quiz
Graphics Quiz
Web Building Quizzes
Web Browsers Quiz
Web Hosting Quiz
W3C Quiz
Web Building Quiz
Web Quality Quiz
Web Semantic Quiz
Web Careers Quiz
Weblogic Quiz
SEO Quiz
Web Site Hosting Quiz
Domain Name Quiz
Java Quizzes
Java Quiz
JSP Quiz
Servlets Quiz
Struts Quiz
EJB Quiz
JMS Quiz
JMX Quiz
Eclipse Quiz
J2ME Quiz
JBOSS Quiz
Programming Langauges Quizzes
C Quiz
C++ Quiz
Visual Basic Quiz
Data Structures Using C Quiz
Cobol Quiz
Assembly Language Quiz
Mainframe Quiz
Forth Programming Quiz
Lisp Programming Quiz
Pascal Quiz
Delphi Quiz
Fortran Quiz
OOPs Quiz
Data Warehousing Quiz
CGI Programming Quiz
Emacs Quiz
Gnome Quiz
ILU Quiz
Soft Skills Quizzes
Communication Skills Quiz
Time Management Quiz
Project Management Quiz
Team Work Quiz
Leadership Skills Quiz
Corporate Communication Quiz
Negotiation Skills Quiz
Database Quizzes
Oracle Quiz
MySQL Quiz
Operating System Quizzes
BSD Quiz
Symbian Quiz
Unix Quiz
Internet Quiz
IP-Masquerading Quiz
IPC Quiz
MIDI Quiz
Software Testing Quizzes
Testing Quiz
Firewalls Quiz
SAP Module Quizzes
ERP Quiz
ABAP Quiz
Business Warehousing Quiz
SAP Basis Quiz
Material Management Quiz
Sales & Distribution Quiz
Human Resource Quiz
Netweaver Quiz
Customer Relationship Management Quiz
Production and Planning Quiz
Networking Programming Quizzes
Corba Quiz
Networking Quiz
Microsoft Office Quizzes
Microsoft Word Quiz
Microsoft Outlook Quiz
Microsoft PowerPoint Quiz
Microsoft Publisher Quiz
Microsoft Excel Quiz
Microsoft Front Page Quiz
Microsoft InfoPath Quiz
Microsoft Access Quiz
Accounting Quizzes
Financial Accounting Quiz
Managerial Accounting Quiz
Testimonials | Contact Us | Link to Us | Site Map
Copyright ? 2008. Academic Tutorials.com. All rights reserved Privacy Policies | About Us
Our Portals : Academic Tutorials | Best eBooksworld | Beyond Stats | City Details | Interview Questions | Discussions World | Excellent Mobiles | Free Bangalore | Give Me The Code | Gog Logo | Indian Free Ads | Jobs Assist | New Interview Questions | One Stop FAQs | One Stop GATE | One Stop GRE | One Stop IAS | One Stop MBA | One Stop SAP | One Stop Testing | Webhosting in India | Dedicated Server in India | Sirf Dosti | Source Codes World | Tasty Food | Tech Archive | Testing Interview Questions | Tests World | The Galz | Top Masala | Vyom | Vyom eBooks | Vyom International | Vyom Links | Vyoms | Vyom World | Important Websites
Copyright ? 2003-2024 Vyom Technosoft Pvt. Ltd., All Rights Reserved.