GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
196 views

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?

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

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

asked in DS by Veteran (38.7k points)  
edited by | 196 views

1 Answer

0 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.
answered by (163 points)  


Top Users Sep 2017
  1. Habibkhan

    6334 Points

  2. Warrior

    2202 Points

  3. Arjun

    2150 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1706 Points

  8. makhdoom ghaya

    1650 Points

  9. A_i_$_h

    1518 Points

  10. rishu_darkshadow

    1512 Points


25,979 questions
33,554 answers
79,348 comments
31,011 users