recategorized by
2,798 views
17 votes
17 votes

A list of $n$ elements is commonly written as a sequence of $n$ elements enclosed in a pair of square brackets. For example. $[10, 20, 30]$ is a list of three elements and $[]$ is a nil list. Five functions are defined below:

  • $car (l)$ returns the first element of its argument list $l$;
  • $cdr (l)$ returns the list obtained by removing the first element of the argument list $l$;
  • $glue (a, l)$ returns a list $m$ such that $car (m)= a$ and $cdr (m)=l$.
  • $f (x, y) \equiv$ if $x= []$ then $y$
                                else $glue (car (x), f (cdr (x), y))$;
  • $g(x) \equiv$ if $x = []$ then $[ ]$
                            else $f (g (cdr (x))$, $glue (car (x), [ ]))$

What do the following compute?

  1. $f ([32, 16, 8], [9, 11, 12])$
  2. $g ([5, 1, 8, 9])$
recategorized by

3 Answers

Best answer
16 votes
16 votes

Part (a) Concatenate the two lists.

Part (b) Reverse the given list.

Part (a):

$f([32,16,8],[9,11,12])$

$\qquad \qquad \Downarrow$

$\text{glue} (\text{car} [32,16,8],f(\text{cdr}([32,16,8]),[9,11,12]))$

$\qquad \qquad \Downarrow$

$\text{glue} (32,f([16,8],[9,11,12]))$

$\qquad \qquad \Downarrow$

$\text{glue} (32,\text{glue}(\text{car}([16,8]),f(\text{cdr}([16,8]),[9,11,12])))$

$\qquad \qquad \Downarrow$

$\text{glue} (32,\text{glue} (16, f ([8],[9,11,12])))$

$\qquad \qquad \Downarrow$

$\text{glue} ( 32, \text{glue} (16, \text{glue}(\text{car} ([8]),f(\text{cdr}([8]),[9,11,12]))))$

$\qquad \qquad \Downarrow$

$\text{glue} (32,\text{glue} (16, \text{glue} (8,f ([]),[9,11,12])))$

$\qquad \qquad \Downarrow$

$\text{glue} (32, \text{glue} (16,\text{glue} (8,[9,11,12])))$

$\qquad \qquad \Downarrow$

$\text{glue} ( 32 , \text{glue} (16, [8,9,11,12]))$

$\qquad \qquad \Downarrow$

$\text{glue} ( 32 , [16,8,9,11,12])$

$\qquad \qquad \Downarrow$

$\boxed{\bf{[32,16,8,9,11,12]}}$ Answer.


Part (b):

$g([5,1,8,9])$

$\qquad \qquad \Downarrow$

$f(g(\text{cdr}([5,1,8,9])), \text{glue} (\text{car} ([5,1,8,9]),[]))$

$\qquad \qquad \Downarrow$

$f(g([1,8,9]),\text{glue} (5,[])))$

$\qquad \qquad \Downarrow$

$f (g ([1,8,9]),[5])$

So, we can say, $g([5,1,8,9]) = f (g([1,8,9]),[5])$

Similarly,

$g([1,8,9]) =f(g([8,9]),[1])$

$g([8,9]) = f(g([9]),[8])$

$g ([9]) = f (g ([]),[9])  = f ( [ ], [9]) = [9]$

Now, backtrack

$g ([8,9]) = f ([9],[8]) =[9,8]$ (From part (a))

& $g ([1,8,9]) = f ([9,8],[1])$

$g ([1,8,9]) = [9,8,1]$ (From part (a))

Now, $g ([5,1,8,9]) = f ([9,8,1], [5]) = [9,8,1,5]$

So, $\bf\boxed{{g ([5,1,8,9]) = [9,8,1,5]}}$ Answer

selected by
2 votes
2 votes
$f$ concatenate two list.

$g$ reverse a list.
1 votes
1 votes
Part (a) :

f([32,16,8],[9,11,12])

// Code is without backslash and solution to code is without backslash

f(x,y)≡   if x=[] then y
                      else glue(car(x),f(cdr(x),y));

// x is not null so else part is executed ,

// glue(car([32,16,8]),f(cdr([32,16,8]),[9,11,12])

glue(a,l) returns list m such that car(m)=a and cdr(m)=l;

car(l) returns the first element of its argument list l;

cdr(l) returns the list obtained by removing the first element of the argument list l;

// Call with value where function becomes

// glue(car([32,16,8]),f(cdr([32,16,8]),[9,11,12])) returns list m such that car(m)=car([32,16,8]) and cdr(m)=cdr([32,16,8]);

// Function returns

// glue(32,glue(car([32,16,8]),f(cdr(cdr([32,16,8])),[9,11,12])))

// Recursive Function returns

// glue(32,glue(32,f(cdr([16,8]),[9,11,12])))

// Recursive Function returns

// glue(32,glue(32,f(8,[9,11,12])))

// Recursive Function returns

// glue(32,glue(32,glue(8,f(cdr(8),[9,11,12]))))

// Recursive Function returns

// glue(32,glue(32,glue(8,f([],[9,11,12]))))

// Note that first time f() has first eleement as null , Function returns

// glue(32,glue(32,glue(8,[9,11,12])))

// Note that first time glue() will return a list m=a+L

// glue(32,glue(32,[8,9,11,12]))

// glue(32,[32,8,9,11,12])

// [32,32,8,9,11,12]

 

Part (b) :

g([5,1,8,9])

 

g(x)≡ if x=[] then []
                        else f(g(cdr(x)), glue(car(x),[]));

// Call by value

// f(g(cdr([5,1,8,9])), glue(car([5,1,8,9]),[]))

// f(g([1,8,9]), glue([5],[]))

// Function Returns

// f(f(g(cdr([1,8,9])), glue(car([1,8,9]),[])), glue([5],[]))

// Function Returns

// f(f(g([8,9]), glue([1],[])), glue([5],[]))

// Function Returns

// f(f(f(g(cdr([8,9])), glue(car([8,9]),[])), glue([1],[])), glue([5],[]))

// Function Returns

// f(f(f(g([9]), glue([8],[])), glue([1],[])), glue([5],[]))

// Function Returns

// f(f(f(f(g(cdr([9])), glue(car([9]),[])), glue([8],[])), glue([1],[])), glue([5],[]))

// Function Returns

// f(f(f(f(g([]), glue([9],[])), glue([8],[])), glue([1],[])), glue([5],[]))

// Function Returns

// f(f(f(f([], glue([9],[])), glue([8],[])), glue([1],[])), glue([5],[]))

// Function Returns

// f(f(f(f([],[9]),[8]),[1]),[5])

// Function will return

// f(f(f([9],[8]),[1]),[5])

// Function will return

// f(f(glue(car([9]),f(cdr([9]),[8])),[1]),[5])

// Function Returns

// f(f(glue([9],f([],[8])),[1]),[5])

// Function Returns

// f(f(glue([9],[8]),[1]),[5])

// Function will return

// f(f([9,8],[1]),[5])

// Function Returns

// f(f([9,8],[1]),[5])

// Call by value

// f(glue(car([9,8]),f(cdr([9,8]),[1])),[5])

// Function Returns

...// f(glue([9],f([8],[1])),[5])

// Function Returns

// f(glue([9],glue(car([8]),f(cdr([8]),[1]))),[5])

// Function Returns

// f(glue([9],glue([8],f([],[1]))),[5])

// Function Returns

// f(glue([9],glue([8],[1])),[5])

// Function Returns

// f(glue([9],[8,1]),[5])

// Function Returns

// f([9,8,1],[5])

// Function Returns

// glue(car([9,8,1]),f(cdr([9,8,1]),[5]))

// Function Returns

// glue([9],f([8,1],[5]))

// Function Returns

// glue([9],glue(car([8,1]),f(cdr([8,1]),[5])))

// Function Returns

// glue([9],glue([8],f([1],[5])))

// Function Returns

// glue([9],glue([8],f([1],[5])))

// Function Returns

// glue([9],glue([8],glue(car([1]),f(cdr([1]),[5]))))

// Function Returns

// glue([9],glue([8],glue([1],f([],[5]))))

// Function Returns

// glue([9],glue([8],glue([1],[5])))

// Function Returns

// glue([9],glue([8],[1,5]))

// Function Returns

// glue([9],[8,1,5])

// Function Returns

// [9,8,1,5]

 

Final Answer:

Part (a) : [32,32,8,9,11,12]

Part (b) : [9,8,1,5]

Makhdoom Gaya Suggest some alternative way , better to know many ways. Hope you will at least look through steps if answer is wrong.

Related questions

23 votes
23 votes
3 answers
1
makhdoom ghaya asked Nov 8, 2016
14,108 views
In a circular linked list organization, insertion of a record involves modification ofOne pointer.Two pointers.Multiple pointers.No pointer.
18 votes
18 votes
3 answers
2
makhdoom ghaya asked Nov 14, 2016
5,083 views
Construct a binary tree whose preorder traversal is$K\;L\;N\;M\;P\;R\;Q\;S\;T$and inorder traversal is$N\;L\;K\;P\;R\;M\;S\;Q\;T$
19 votes
19 votes
3 answers
3
makhdoom ghaya asked Nov 9, 2016
4,831 views
State whether the following statements are TRUE or FALSE:If the number of leaves in a tree is not a power of $2,$ then the tree is not a binary tree.
31 votes
31 votes
5 answers
4
makhdoom ghaya asked Nov 9, 2016
6,426 views
State whether the following statements are TRUE or FALSE:It is possible to construct a binary tree uniquely whose pre-order and post-order traversals are given?