EECS 111 Lecture Notes - Lecture 6: Linked List, London Academy Of Music And Dramatic Art, Mymusic

21 views6 pages
Lists%are%sequences%of%data%objects
Any%length%
Any%type%of%data%object
Different%types%can%be%mixed%in%the%same%list%
Sceme%and%Racket%use%a%particular%type%of%list%called%a%linked%list%
Example:%A%music%collection%
A%list%of%album%objects
123'42567'89:;'72'<;<2=>?;'@A;B>C>B'A=2B;43=;@
Simple%list%constructors%
(list%item1,%item%2,%itemX)
Creates%a%list%containing%the%specified%items,%in%order%
§
(append%%item1,%item%2,%itemX)
Creates%a%new%list%with%all%the%items%from%the%input%list,%in%order
§
Simple%list%accessors%
(C>=@7list),%(second%list),%…%(tenth%list)
Extracts%the%@A;B>C>;4';D;<;57 of%list
§
(=;@7 list)%
Returns%E))'F(. the%first%element%of%list
§
(D>@7G=;C list%index)
Extracts%the%element%at%position%index%(a%number)
Index%counts%from%zero%
§
(D;5H78 list)
(define%my-list%(list%1%2%3))
(list%1%2%3)
(append%my-list%(list%4%5%6))
(list%1%2%3%4%5%6)
(rest%(append%%my-list%(list%4%5%6)))
(list%2%3%4%5%6)
Empty%list%
empty
(list)
Examples
Lists%can%
Be%empty:%(list)
§
Mix%different%types%of%data:%(list%"a"%"b"%"c"%1%2%3)
§
Have%other%lists%inside%them%(list%"a"%(list%"b"%"c"))
§
The%length%of%a%list%is%the%number%of%elements%in%it%
When%a%list%has%a%list%I>78>5'>7,%the%sublist%only%counts%as%one%element
Lists%are%numbered%from%0%(first%item%=%item%0,%second%item%=%item%1)
Asking%for%an%element%past%the%end%of%the%list%gives%an%IdexOutOfRangeException
/"J'K$#-"L($"M'+%)."$'
(filter%predicate%list)
;;filter:%(X%->%Boolean)%(listofX)%->%(listofX)
Returns%ALL%THE%ITEMS%satisfying%predicate%(so%all%items%that%would%be%"true")
Examples:
(filter%odd?%(list%1%2%3%4%5%6))
(list%1%3%5)
§
(filter%number?%(list%1%2%"three))
(list%1%2)
§
Finding%all%the%Beatles%albums%
(filter%Beatles?%Mymusic)
(list%(make-album%"The%White%Album"
"The%Beatles"%"Rock")
(Make-album%"Name"
"The%Beatles"%"Rock"))
(filter%(lamda%(album)
(string=?%(album-artist%album)
"The%Beatles"))
mymusic)
Beatles?%Is%just%a%variable,%so%we%can%just%type%its%value%rather%than%the%name%
Filter%returns%a%list%of%equal%or%smaller%length%than%original%list%
#=<9A:%are%there%any%items%in%this%this%that%pass%the%Boolean?
Takes%a%predicate%and%a%list
E54<9A:%do%all%items%in%this%list%pass%the%Boolean?
Takes%a%predicate%and%a%list
!EKK%/N
(map%procedure%list)
;;%map:%(In%->%Out)%%(listofln)%->%(listofOut)
Runs%procedure on%;:;=O';D;<;57
Outputs%their%return%values%as%a%new%list%
Ex.%(map%proc%(list%a%b%c))%is%equivalent%to%(list%(proc%a)%(proc%b)%(proc%c))
§
Example
(map%-(list%1%2%3%4))%------->>>>>%%%%(list%-1%-2%-3%-4)
§
Input%list%and%list%of%results%are%the%same%length%
$;<2:;G43AD>B97;@ takes%a%list%and%returns%a%new%copy%of%it%with%duplicate%elements%removed
+#)L%/N
(foldl%proc%start-value%list)
(foldr%proc%start-value%list)
L%and%r%are%left%and%right
§
;;%foldl/foldr%:%(X%X%->%X)%X%(listofX)%->%X
Aggregates%all%values%of%list%together%using%procedure%proc%
Summing%or%multiplying%elements%of%a%list%
(foldl%proc%start%(list%a%b%c))%is%equivalent%to%(proc%c%(proc%b%(proc%a%start)))%%%%(starts%with%leftmost%item)
(foldr%proc%start%(list%a%b%c))%is%equivalent%to%(proc%a%(proc%b%(proc%c%start)))%%%(starts%with%rightmost%item)
Averaging%
;;sum:%(list%of%number)%->%number
;;%(define%sum%
(lambda%(lst)%(foldl%+%0%lst)))
Mean:%(listof%number)%->%number
Iterating%
(build-list%count%proc)
;;build-list:%number%(number%->%X)%->%(listofX)
Runs%proc%repeatedly%
These%are%the%same%thing
Lists
Monday,%January%29,%2018
12:02%PM
Unlock document

This preview shows pages 1-2 of the document.
Unlock all 6 pages and 3 million more documents.

Already have an account? Log in
Lists%are%sequences%of%data%objects
Any%length%
Any%type%of%data%object
Different%types%can%be%mixed%in%the%same%list%
Sceme%and%Racket%use%a%particular%type%of%list%called%a%linked%list%
Example:%A%music%collection%
A%list%of%album%objects
!"!#$%&"'$()"*'+#$'","-(.%#/'0000000'
123'42567'89:;'72'<;<2=>?;'@A;B>C>B'A=2B;43=;@
Simple%list%constructors%
(list%item1,%item%2,%itemX)
Creates%a%list%containing%the%specified%items,%in%order%
§
(append%%item1,%item%2,%itemX)
Creates%a%new%list%with%all%the%items%from%the%input%list,%in%order
§
Simple%list%accessors%
(C>=@7list),%(second%list),%…%(tenth%list)
Extracts%the%@A;B>C>;4';D;<;57 of%list
§
(=;@7 list)%
Returns%E))'F(. the%first%element%of%list
§
(D>@7G=;C list%index)
Extracts%the%element%at%position%index%(a%number)
Index%counts%from%zero%
§
(D;5H78 list)
(define%my-list%(list%1%2%3))
(list%1%2%3)
(append%my-list%(list%4%5%6))
(list%1%2%3%4%5%6)
(rest%(append%%my-list%(list%4%5%6)))
(list%2%3%4%5%6)
Empty%list%
empty
(list)
Examples
Lists%can%
Be%empty:%(list)
§
Mix%different%types%of%data:%(list%"a"%"b"%"c"%1%2%3)
§
Have%other%lists%inside%them%(list%"a"%(list%"b"%"c"))
§
The%length%of%a%list%is%the%number%of%elements%in%it%
When%a%list%has%a%list%I>78>5'>7,%the%sublist%only%counts%as%one%element
Lists%are%numbered%from%0%(first%item%=%item%0,%second%item%=%item%1)
Asking%for%an%element%past%the%end%of%the%list%gives%an%IdexOutOfRangeException
/"J'K$#-"L($"M'+%)."$'
(filter%predicate%list)
;;filter:%(X%->%Boolean)%(listofX)%->%(listofX)
Returns%ALL%THE%ITEMS%satisfying%predicate%(so%all%items%that%would%be%"true")
Examples:
(filter%odd?%(list%1%2%3%4%5%6))
(list%1%3%5)
§
(filter%number?%(list%1%2%"three))
(list%1%2)
§
Finding%all%the%Beatles%albums%
(filter%Beatles?%Mymusic)
(list%(make-album%"The%White%Album"
"The%Beatles"%"Rock")
(Make-album%"Name"
"The%Beatles"%"Rock"))
(filter%(lamda%(album)
(string=?%(album-artist%album)
"The%Beatles"))
mymusic)
Beatles?%Is%just%a%variable,%so%we%can%just%type%its%value%rather%than%the%name%
Filter%returns%a%list%of%equal%or%smaller%length%than%original%list%
#=<9A:%are%there%any%items%in%this%this%that%pass%the%Boolean?
Takes%a%predicate%and%a%list
E54<9A:%do%all%items%in%this%list%pass%the%Boolean?
Takes%a%predicate%and%a%list
!EKK%/N
(map%procedure%list)
;;%map:%(In%->%Out)%%(listofln)%->%(listofOut)
Runs%procedure on%;:;=O';D;<;57
Outputs%their%return%values%as%a%new%list%
Ex.%(map%proc%(list%a%b%c))%is%equivalent%to%(list%(proc%a)%(proc%b)%(proc%c))
§
Example
(map%-(list%1%2%3%4))%------->>>>>%%%%(list%-1%-2%-3%-4)
§
Input%list%and%list%of%results%are%the%same%length%
$;<2:;G43AD>B97;@ takes%a%list%and%returns%a%new%copy%of%it%with%duplicate%elements%removed
+#)L%/N
(foldl%proc%start-value%list)
(foldr%proc%start-value%list)
L%and%r%are%left%and%right
§
;;%foldl/foldr%:%(X%X%->%X)%X%(listofX)%->%X
Aggregates%all%values%of%list%together%using%procedure%proc%
Summing%or%multiplying%elements%of%a%list%
(foldl%proc%start%(list%a%b%c))%is%equivalent%to%(proc%c%(proc%b%(proc%a%start)))%%%%(starts%with%leftmost%item)
(foldr%proc%start%(list%a%b%c))%is%equivalent%to%(proc%a%(proc%b%(proc%c%start)))%%%(starts%with%rightmost%item)
Averaging%
;;sum:%(list%of%number)%->%number
;;%(define%sum%
(lambda%(lst)%(foldl%+%0%lst)))
Mean:%(listof%number)%->%number
Iterating%
(build-list%count%proc)
;;build-list:%number%(number%->%X)%->%(listofX)
Runs%proc%repeatedly%
These%are%the%same%thing
Lists
Monday,%January%29,%2018 12:02%PM
Unlock document

This preview shows pages 1-2 of the document.
Unlock all 6 pages and 3 million more documents.

Already have an account? Log in

Get OneClass Notes+

Unlimited access to class notes and textbook notes.

YearlyBest Value
75% OFF
$8 USD/m
Monthly
$30 USD/m
You will be charged $96 USD upfront and auto renewed at the end of each cycle. You may cancel anytime under Payment Settings. For more information, see our Terms and Privacy.
Payments are encrypted using 256-bit SSL. Powered by Stripe.