GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
155 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 (30.4k points)  
edited by | 155 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 Jul 2017
  1. Bikram

    4910 Points

  2. manu00x

    2940 Points

  3. Debashish Deka

    1870 Points

  4. joshi_nitish

    1776 Points

  5. Arjun

    1506 Points

  6. Hemant Parihar

    1306 Points

  7. Shubhanshu

    1128 Points

  8. pawan kumarln

    1124 Points

  9. Arnab Bhadra

    1114 Points

  10. Ahwan

    956 Points


24,099 questions
31,074 answers
70,703 comments
29,407 users