Programming languages, show each step: A presented definition of the foldr (or r

Question

Programming languages, show each step:

A presented definition of the foldr (or reduce) function as:

Foldr: f x NIL = x foldr: f x (cons a list) = f a (foldr f x list) and gave an example of using foldr. Let's have some fun and combine the features of a number of different languages. (1) Borrowing from the course notes and Haskell, let's define a function foldl, (a) foldl f x NIL = x (b) foldl f x (cons a list) = foldl f(f x a) list (2) Borrowing from Python, we can treat a string as a sequence (i.e. a list) of characters, "bar" ('b' 'a' 'r') ['b', 'a', 'r'] (3) Borrowing from Lisp, we can use cons cells to represent or create lists, ('b' 'a' 'r') (cons 'b' (cons 'a' (cons 'r' nil))) (4) Borrowing from Fortran, we can define a string concatenation function, //, 'concate'//' nation' 'concatenation' (5) Borrowing from Scheme, define a toggle function, f x y = f y x, (define toggle (lambda (f x y) (f y x))) That is, the toggle function switches its arguments, in Lambda Calculus, it's, f. lambda x. lambda y. f y x Thus, for example, (f 'back' 'drop') (f 'drop' back') In this question, please trace the execution/reduction of the following function: foldl (toggle//) nil ("foo" "bar" "baz") In order to obtain full credit and possibly obtain partial credit when appropriate, you must show each step (for example, my solution has 11 steps). At each step, briefly describe how you transitioned from the previous step. For example, you simply explain it by listing: via OR via (1)(a).

Explanation / Answer

Here we start dicussion about fold function in brief :-

Foldk function also termed as reduce,aggergate & compress function which refers to the higher order function's family. It analyze a recursive data structure with the use of given combine & recombine operation that provide the return value.

A node represent the combining function and node of the data structures and some default values under certain conditions.The fold then represent the data structure using insome systematic way. For instat,we mihght to use a hypothetical function 'fold' to write:

fold (+) [1,2,3,4,5] , which is result in (1+2+3+4+5) i.e., 15.
And '+' is an associative operation one paranthsis is irrevelent to what the final result value bealthough the operational detailwill differ as how exactly it will be calculated.

However , in the general case the function of two parameters are not associative, so the order in which one comes out the combination of the elements matters. On list,there are two ways to carry this out: either by recursivelycombinig the first element with the result of combining the rest i.e. the right fold or by recursivly combining the result of combinig all but the last element with the last one i.e. the left fold. Aso in practice it is also inconvenient and natural to have the initial value which is the case of right fold is used as one reaches at the end of list but in the case of left foldis what is initially combines with the first element of the list. the perhaps clearer to see in theequation defining 'foldr' and 'foldl' in Haskell.

Note that in Haskell,[] represent the empty list and (x:xs) represent the list starting with x and where the rest of the list is xs.

In case of empty list,the result is initial value y else apply f to the first element and rest of the result:
fold f z []= z
fold f z (y:ys) = f y (foldk f z ys)

In case of empty list, The result is initial value; else we recurse immediatly, making the new initial value of the reult of combinig the old initial value with the first element.
fold f z[] = z
fold f z(y:ys)= foldk f (f z y) ys

Check out the examples:

Input foldk (+) 5[1,2,3,4] and the output is 15.
If the input is foldk(/) 4[] then output is 4.0
If the input is foldk(max) [57,17,82,37] the output is 82.

Now using Toggle func Scheme:
Here we correct
(toggle //) to (toggle (//))
because of type errror.

foldk (toggle //) nil ("foo""bar""baz)

First we need to start with (1b) left side, foldk f y (cons a list)

with f= (toggle (//)), y=nil and list = ("foo" "bar" "baz)

Then we use(3) recursively expand the list.

After that use(1b) right side foldk f (f y a ) list

in order to recursively apply f, (toggle (//)) , to expand the list.

Next we use(5) to apply the toggle function in the list expression.

At last we use(4) ,//, in order to reduce the expression.

Here is the Output:

foldk (toggle //) nil ("foo""bar""baz)
foldk fy (cons a list)- via (1b)
foldk fy (a list)- via (3)
foldk f (f y a) list - via (1b)
foldk (toggle //) (toggle // y a) list - via(5)
foldk y // // a list - via(4)
foldk nil a ("foo""bar""baz)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.