Lists
Definition : A list over set S is defined as follows : ~
Listsy = Set of all lists over S
·
base case : The empty list [J is a list
·
Step case :
IfI is a list over S and SES S: l is a list over S
. > How are lists built ?
,
S =
IN
[J ,
1 : []
,
2 : (1 ; 53)
,
1 :
(2 (1 : :
[]))
[i] ta ,
is in aii)
Operations on recursive data structures
Idea : ·
Define operation for base case (s) Example : Want binary operation Listsgx Lists -
Listsy ,
which
takes 2 lists and concatenates them
.
Assume know how to define operation structures built
·
we on so far.
·
Define operation for new structures built using step case(s).
Let (i I' be I concatenated with
Example Define :
operation Sum : Lists
N
IN adding all the elements
of the list. base case [I H 11 = 1
given
Step case (5 : () + l = s : ((II))
base case sum[] = 0
Step case sum(5 () : =
s + Sum( [1 21 H 10
, ,
2
,
11 =
(1 : [2]) [3 ,
2
, 1] Sc concat
=
1 :
((2 [l) + :
[3 ,
2
, 11) Sc concat
Sum [1 ,
2
,
1] = sum (1 : [2, 1] sc Sum
= 1 : (2 ([I
:
+ [3 , 2, 11) s concat
= 1 + sum(2 : [1]) Sc Sum
=
1 : (2 : [3 , 2
, 17) bc concat
=
1 + 2 + sum(1 : []) Sc Sum
=
[1 ,
2 3
, ,
2
,
1 append
= 1 + 2 + 1 + sum[] sc sum
= 1 + 2 + 1 + 0 be sum
Example : ForI t given by base case [l + 11 = 1
=
4 Step case (5 : 1) H = 5 : ((11 ()
Show that for all Le Lists (+ [T =
,
[J
So is unit for it
Example Define : a operation rev : Lists >
Lists that reverses a list.
Proof by induction :
L
L
base rev[] = [] base case [J + []
=
[]
case
Step case rev(s : 1) = revL #ISI Step case (5 : (15) =
5 :
((it)) #
base Case !
=
S
: step case
Example : Show summer) = sum for all Le Lists
You may use sum (1H1') =
Suml + suml Example : Show forthat all 1, 11E Lists IN
,
sum((H(1) = sum) + Sum(
Proof by induction :
base case Sumrev[] =
SumI] be nev Proof by induction :
Step case sum rev (5 : 1) =
Sum(rov1H [s]) Sc rev base case Sum([]111) = Sum I' be concat
("
=
Sum(rev() + sum(s : []) ind . hyp
.
= O + Sum
= sumY + 5 + sumI]
Sc Sum = sum[I + sumI' be sum
Suml
=
+ 5 + 0 be Sum
=
S + sum Step case Sum(15 : 1) H() =
sum(s : (1 + 1)) Sc concert
= Sum(5 : () = S + Sum(( + 1) sc sum
= S + sum) + suml' ind .
hyp .
= Sum (s : 1) + suml" sc Sum
Definition : A list over set S is defined as follows : ~
Listsy = Set of all lists over S
·
base case : The empty list [J is a list
·
Step case :
IfI is a list over S and SES S: l is a list over S
. > How are lists built ?
,
S =
IN
[J ,
1 : []
,
2 : (1 ; 53)
,
1 :
(2 (1 : :
[]))
[i] ta ,
is in aii)
Operations on recursive data structures
Idea : ·
Define operation for base case (s) Example : Want binary operation Listsgx Lists -
Listsy ,
which
takes 2 lists and concatenates them
.
Assume know how to define operation structures built
·
we on so far.
·
Define operation for new structures built using step case(s).
Let (i I' be I concatenated with
Example Define :
operation Sum : Lists
N
IN adding all the elements
of the list. base case [I H 11 = 1
given
Step case (5 : () + l = s : ((II))
base case sum[] = 0
Step case sum(5 () : =
s + Sum( [1 21 H 10
, ,
2
,
11 =
(1 : [2]) [3 ,
2
, 1] Sc concat
=
1 :
((2 [l) + :
[3 ,
2
, 11) Sc concat
Sum [1 ,
2
,
1] = sum (1 : [2, 1] sc Sum
= 1 : (2 ([I
:
+ [3 , 2, 11) s concat
= 1 + sum(2 : [1]) Sc Sum
=
1 : (2 : [3 , 2
, 17) bc concat
=
1 + 2 + sum(1 : []) Sc Sum
=
[1 ,
2 3
, ,
2
,
1 append
= 1 + 2 + 1 + sum[] sc sum
= 1 + 2 + 1 + 0 be sum
Example : ForI t given by base case [l + 11 = 1
=
4 Step case (5 : 1) H = 5 : ((11 ()
Show that for all Le Lists (+ [T =
,
[J
So is unit for it
Example Define : a operation rev : Lists >
Lists that reverses a list.
Proof by induction :
L
L
base rev[] = [] base case [J + []
=
[]
case
Step case rev(s : 1) = revL #ISI Step case (5 : (15) =
5 :
((it)) #
base Case !
=
S
: step case
Example : Show summer) = sum for all Le Lists
You may use sum (1H1') =
Suml + suml Example : Show forthat all 1, 11E Lists IN
,
sum((H(1) = sum) + Sum(
Proof by induction :
base case Sumrev[] =
SumI] be nev Proof by induction :
Step case sum rev (5 : 1) =
Sum(rov1H [s]) Sc rev base case Sum([]111) = Sum I' be concat
("
=
Sum(rev() + sum(s : []) ind . hyp
.
= O + Sum
= sumY + 5 + sumI]
Sc Sum = sum[I + sumI' be sum
Suml
=
+ 5 + 0 be Sum
=
S + sum Step case Sum(15 : 1) H() =
sum(s : (1 + 1)) Sc concert
= Sum(5 : () = S + Sum(( + 1) sc sum
= S + sum) + suml' ind .
hyp .
= Sum (s : 1) + suml" sc Sum
