The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+4 votes
244 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 (42.7k points)
edited by | 244 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 (245 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,017 questions
36,844 answers
91,377 comments
34,721 users