Question:
produce a deep-reverse procedure that takes a list as argument
and returns as its value the list with its elements reversed
and with all sublists deep-reversed as well.
For example:
(define x (list (list 1 2) (list 3 4)))
x
((1 2) (3 4))
(reverse x)
((3 4) (1 2))
(deep-reverse x)
((4 3) (2 1))
Code:
( define tree ( list 1 ( list 2 ( list 3 4 ) 5 ) ( list 6 7 ) ) )
( define nil '() )
( define ( my-reverse items )
( define ( rev-imp items result )
( if ( null?
items )
result
( rev-imp ( cdr items )
( cons ( car items ) result ) ) ) )
( rev-imp items nil ) )
( my-reverse items )
Output:
> ( my-reverse tree )
((6 7) (2 (3 4) 5) 1)
Code:
( define ( deep-reverse items )
( define ( deep-rev-if-required item )
( if ( not ( pair? item ) )
item
( deep-reverse item ) ) )
( define ( deep-rev-imp items result )
( if ( null? items )
result
( deep-rev-imp ( cdr items )
( cons ( deep-rev-if-required( car items ) )
result ) ) ) )
( deep-rev-imp items nil ) )
Output:
> ( deep-reverse tree )
((7 6) (5 (4 3) 2) 1)
or Code as:
( define ( deep-reverse items )
( if ( pair?
items )
( my-reverse ( map deep-reverse items ) )
items ) )
Output:
> ( deep-reverse tree )
((7 6) (5 (4 3) 2) 1)
Question:
Write a procedure fringe that takes as argument a tree (represented as a list) and
returns a list whose elements are all the leaves of the tree arranged in left-to-right order.
For example:
(define x (list (list 1 2) (list 3 4)))
(fringe x)
(1 2 3 4)
(fringe (list x x))
(1 2 3 4 1 2 3 4)
Code:
( define ( fringe tree )
( define ( search items res )
( cond ( ( null? items )
res )
( ( not ( pair? items ) )
( cons items res ) )
( else ( search ( car items )
( search ( cdr items ) res ) ) ) ) )
( search tree nil ) )
or Code as:
( define ( fringe tree )
( cond ( ( null? tree )
nil )
( ( not ( pair? tree ) )
( list tree ) )
( else ( append ( fringe ( car tree ) )
( fringe ( cdr tree ) ) ) ) ) )
Output:
> ( fringe tree )
(1 2 3 4 5 6 7)
Question:
We can represent a set as a list of distinct elements,
and we can represent the set of all subsets of the set as a list of lists.
For example, if the set is (1 2 3), then the set of all subsets is
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)).
Complete the following definition of a procedure that
generates the set of subsets of a set and give a clear explanation of why it works:
For example:
( define ( subsets s )
( if ( null? s )
( list nil )
( let ( ( rest ( subsets ( cdr s ) ) ) )
( append rest ( map <??> rest ) ) ) ) )
Code:
( define nil '() )
( define ( subsets s )
( if ( null? s )
( list nil )
( let ( ( rest ( subsets ( cdr s ) ) ) )
( append rest ( map ( lambda ( x )
( cons ( car s ) x ) )
rest ) ) ) ) )
Output:
> ( subsets ( list 1 2 3 ) )
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))