GATE CSE 1987 | Question: 6a

Question

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])$

Comments

What is the connection of this problem with linked lists? It looks like a mathematics problem. Is there any linked lists concept that can help us to solve the problem more easily?

---

@akashkumarsen4 Just because there are two lists which are “linked” with each other through “glue” it’s present here I guess. But there’s no concept of “actual” linked list.

Answer 1

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

Comments

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

⇓

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

⇓

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

As it is mentioned that

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

so we are modifying the same list and returning it, it doesn’t return a new list by removing element.

After cdr([5,1,8,9]) the list is modified to [1,8,9] and on that we apply car([1,8,9])

@ankitgupta.1729 @Arjun @Bikram please clarify

---

@shashank023, sorry, I am not getting your question and there is some mistake in 2^nd and 3^rd line.

---

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

here in g function parameters get [5,1,8,9] and so, 

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

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

comes not whatever you mentioned.

EDIT :  It is coming exactly whatever is mentioned in answer.

---

@ASNR1010 It’s coming exactly as @ankitgupta.1729 Sir’s answer for the g() function. Check once again bro.

Answer 2

$f$ concatenate two list.

$g$ reverse a list.

Comments

This observation is needed to succeed 🎆

Answer 3

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.