Programming languages... We previously had a definition of the foldr (or reduce)

Question

Programming languages...

We previously had a definition of the foldr (or reduce) function:

foldr: f times NIL = x foldr: f times (cons a list) = f a (foldr f times list) IN 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 fold1, (a) fold1 f times NIL = x (b) fold1 f times (cons a list) = foldl f(f times a) list (2) Borrowing from Python, we can treat a string as a sequence (i.e. a list) of characters, "bar" congruent ('b' 'a' 'r') congruent ['b' 'a' 'r'] (3) Borrowing from Lisp, we can use cons cells to represent or create lists, ('b' 'a' 'r') congruent (cons 'b' (cons 'r' nil))) (4) Borrowing from Fortran, we can define a string concatenation function, //, 'concate'//'nation' doublerightarrow '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, lambda f. Lambda x. Lambda y. f y x Thus, for example, (f 'back' 'drop') doublerightarrow (f 'drop' back') In this question, please trace the execution/reduction of the following function: fold1 (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 congruent OR via(1)(a)

Explanation / Answer

Foldr Function:

fold (+) [1,2,3,4,5] , which is result in (1+2+3+4+5) which is 15.'+' is an associative operation one parenthesis is irreverent to what the final result value be although the operational detail will differ as how exactly it will be calculated.

Examples:

Input foldr (+) 5[1,2,3,4] and the output is 15.

If the input is foldr(/) 3[] then output is 3.0

If the input is foldr(max) [43,7,22,87] the output is 87.

Toggle fn using Scheme:

Note: I am correcting the (toggle //) to (toggle (//)) due to the type error.

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

Step 1: Start with (1b) left side, foldl f x (cons a list) with f= (toggle (//)), x=nil and list = ("foo" "bar" "baz)

Step 2: Use (3) recursively expand the list.

Step 3: use (1b) right side foldl f (f x a ) list to recursively apply f, (toggle (//)) , to expand the list.

Step 4: Use (5) to apply the toggle function in the list expression.

Step 5: Use(4) ,//, to reduce the expression.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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