Constructing ListsConstructing Listsldots Examining ListsExamining Listsldots Examining Listsldots Lists of ListsList EquivalenceList Equivalenceldots Predicates on ListsList Functions --- Examplesldots Recursion over Lists --- cdr-recursionRecursion over Lists --- car-cdr-recursionRecursion Over Lists --- Returning a ListRecursion Over Two ListsRecursion Over Two Listsldots AppendDeep Recursion --- { t equal?}Patterns of Recursion --- cdr-recursionPatterns of Recursion --- car-cdr-recursionPatterns of Recursion --- MapsExample: Binary TreesExample: Binary Treesldots Example: Binary Treesldots Binary Trees using StructuresBinary Trees using Structuresldots Homework520—Spring 2005—7CSc 520Principles of ProgrammingLanguages7: Scheme — List ProcessingChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—7Constructing ListsThe most important data structure in Scheme is the list.Lists are constructed using the function cons:(cons first rest)consreturns a list where the first element is first,followed by the elements from the list rest.> (cons ’a ’())(a)> (cons ’a (cons ’b ’()))(a b)> (cons ’a (cons ’b (cons ’c ’())))(a b c)[2]520—Spring 2005—7Constructing Lists...There are a variety of short-hands for constructing lists.Lists are heterogeneous, they can contain elements ofdifferent types, including other lists.> ’(a b c)(a b c)> (list ’a ’b ’c)(a b c)> ’(1 a "hello")(1 a "hello")[3]520—Spring 2005—7Examining Lists(car L) returns the first element of a list. Someimplementations also define this as (first L).(cdr L) returns the list L, without the first element.Some implementations also define this as (rest L).Note that car and cdr do not destroy the list, justreturn its parts.> (car ’(a b c))’a> (cdr ’(a b c))’(b c)[4]520—Spring 2005—7Examining Lists...Note that (cdr L) always returns a list.> (car (cdr ’(a b c)))’b> (cdr ’(a b c))’(b c)> (cdr (cdr ’(a b c)))’(c)> (cdr (cdr (cdr ’(a b c))))’()> (cdr (cdr (cdr (cdr ’(a b c)))))error[5]520—Spring 2005—7Examining Lists...A shorthand has been developed for looking deep into alist:(clist of "a" and "d"r L)Each "a" stands for a car, each "d" for a cdr.For example, (caddar L) stands for(car (cdr (cdr (car L))))> (cadr ’(a b c))’b> (cddr ’(a b c))’(c)> (caddr ’(a b c))’c[6]520—Spring 2005—7Lists of ListsAny S-expression is a valid list in Scheme.That is, lists can contain lists, which can contain lists,which...> ’(a (b c))(a (b c))> ’(1 "hello" ("bye" 1/4 (apple)))(1 "hello" ("bye" 1/4 (apple)))> (caaddr ’(1 "hello" ("bye" 1/4 (apple))))"bye"[7]520—Spring 2005—7List Equivalence(equal? L1 L2) does a structural comparison oftwo lists, returning #t if they “look the same”.(eqv? L1 L2) does a “pointer comparison”,returning #t if two lists are “the same object”.> (eqv? ’(a b c) ’(a b c))false> (equal? ’(a b c) ’(a b c))true[8]520—Spring 2005—7List Equivalence...This is sometimes referred to as deep equivalence vs.shallow equivalence.> (define myList ’(a b c))> (eqv? myList myList)true> (eqv? ’(a (b c (d))) ’(a (b c (d))))false> (equal? ’(a (b c (d))) ’(a (b c (d))))true[9]520—Spring 2005—7Predicates on Lists(null? L) returns #t for an empty list.(list? L) returns #t if the argument is a list.> (null? ’())#t> (null? ’(a b c))#f> (list? ’(a b c))#t> (list? "(a b c)")#f[10]520—Spring 2005—7List Functions — Examples...> (memq ’z ’(x y z w))#t> (car (cdr (car ’((a) b (c d)))))(c d)> (caddr ’((a) b (c d)))(c d)> (cons ’a ’())(a)> (cons ’d ’(e))(d e)> (cons ’(a b) ’(c d))((a b) (c d))[11]520—Spring 2005—7Recursion over Lists — cdr-recursionCompute the length of a list.This is called cdr-recursion.(define (length x)(cond[(null? x) 0][else (+ 1 (length (cdr x)))]))> (length ’(1 2 3))3> (length ’(a (b c) (d e f)))3[12]520—Spring 2005—7Recursion over Lists — car-cdr-recursionCount the number of atoms in an S-expression.This is called car-cdr-recursion.(define (atomcount x)(cond[(null? x) 0][(list? x)(+ (atomcount (car x))(atomcount (cdr x)))][else 1]))> (atomcount ’(1))1> (atomcount ’("hello" a b (c 1 (d))))6[13]520—Spring 2005—7Recursion Over Lists — Returning a ListMap a list of numbers to a new list of their absolutevalues.In the previous examples we returned an atom — herewe’re mapping a list to a new list.(define (abs-list L)(cond[(null? L) ’()][else (cons (abs (car L))(abs-list (cdr L)))]))> (abs-list ’(1 -1 2 -3 5))(1 1 2 3 5)[14]520—Spring 2005—7Recursion Over Two Lists(atom-list-eq? L1 L2) returns #t if L1 and L2are the same list of atoms.(define (atom-list-eq? L1 L2)(cond[(and (null? L1) (null? L2)) #t][(or (null? L1) (null? L2)) #f][else (and(atom? (car L1))(atom? (car L2))(eqv? (car L1) (car L2))(atom-list-eq? (cdr L1) (cdr L2)))]))[15]520—Spring 2005—7Recursion Over Two Lists...> (atom-list-eq? ’(1 2 3) ’(1 2 3))#t> (atom-list-eq? ’(1 2 3) ’(1 2 a))#f[16]520—Spring 2005—7Append(define (append L1 L2)(cond[(null? L1) L2][else(cons (car L1)(append (cdr L1) L2))]))> (append ’(1 2) ’(3 4))(1 2 3 4)> (append ’() ’(3 4))(3 4)> (append ’(1 2) ’())(1 2)[17]520—Spring 2005—7Deep Recursion — equal?(define (equal? x y)(or (and (atom? x) (atom? y) (eq? x y))(and (not (atom? x))(not (atom? y))(equal? (car x) (car y))(equal? (cdr x) (cdr y)))))> (equal? ’a ’a)#t> (equal? ’(a) ’(a))#t> (equal? ’((a)) ’((a)))#t[18]520—Spring 2005—7Patterns of Recursion — cdr-recursionWe process the elements of the list one at a time.Nested lists are not descended into.(define (fun L)(cond[(null? L) return-value][else ...(car L) ...(fun (cdr L)) ...]))[19]520—Spring 2005—7Patterns of Recursion — car-cdr-recursionWe descend into nested lists, processing every atom.(define (fun x)(cond[(null? x) return-value][(atom? x) return-value][(list? x)...(fun (car x)) ......(fun (cdr x)) ...][elsereturn-value]))[20]520—Spring 2005—7Patterns of Recursion — MapsHere we map one list to another.(define (map L)(cond[(null? L) ’()][else (cons (...(car L) ...)(map (cdr L)))]))[21]520—Spring 2005—7Example: Binary TreesA binary tree can be represented as nested lists:(4 (2 () () ( 6 ( 5 () ()) ())))Each node is represented by a triple(data left-subtree right-subtree)Empty subtrees are represented by ().[22]520—Spring
View Full Document
Unlocking...