a) Let op be an associative operation withe as the neutral element: op is associative: (x op y) op z = x op (y op z) e is neutral element: e op x = x and x op e = x Then the following holds for finite lists xs: foldr op e xs = foldl op e xs b) Let op1 and op2 be two operations for which x op1 (y `op2` z) = (x `op1` y) `op2` z x `op1 e = e op2 x holds. Then the following holds for finite lists xs: foldr op1 e xs = foldl op2 e xs c) Let op be an associative operation and xs a finite list. Then foldr op a xs = foldl op' a (reverse xs) holds with х ор' у 3 у ор х
a) Let op be an associative operation withe as the neutral element: op is associative: (x op y) op z = x op (y op z) e is neutral element: e op x = x and x op e = x Then the following holds for finite lists xs: foldr op e xs = foldl op e xs b) Let op1 and op2 be two operations for which x op1 (y `op2` z) = (x `op1` y) `op2` z x `op1 e = e op2 x holds. Then the following holds for finite lists xs: foldr op1 e xs = foldl op2 e xs c) Let op be an associative operation and xs a finite list. Then foldr op a xs = foldl op' a (reverse xs) holds with х ор' у 3 у ор х
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
Related questions
Question
![The fold functions compute a value over a list (or some other type that is foldable) by applying an
operator to the list elements and a neutral element. The foldl function assumes that the operator
is left associative, the foldr function assumes that the operatore is right associative. For example,
the function application
foldl (+) 0 [3,5,2,1]
1
results in the computation of (((0+3)+5)+2)+1) and the function application
foldr (+) 0 [3,5,2,1]
1
results in the computation of (3+(5+(2+(1+0)). The value computed by the fold functions may be
more complex than a simple scalar. It is very well possible to construct a new list as part of the
fold. For example:
map' :: (a -> b) -> [a] -> [b]
map' f xs = foldr ((:) . f) [] xs
1
The evaluation of map' succ [1,2,3] results in the list [2,3,4]. There are several duality theo-
rems that can be stated for fold functions. Prove the following three duality theorems:
a) Let op be an associative operation with e as the neutral element:
op is associative: (x op y) op z = x op (y op z)
e is neutral element: e op x = x and x op e = x
Then the following holds for finite lists xs:
foldr op e xs = foldl op e XS
b) Let op1 and op2 be two operations for which
x `op1 (y `op2 z) = (x `op1 y)`op2` z
x `op1 e
= e `op2` x
holds. Then the following holds for finite lists xs:
foldr op1 e xs = foldl op2 e xs
c) Let op be an associative operation and xs a finite list. Then
foldr op a xs = foldl op' a (reverse xs)
holds with
х ор' у 3 у ор х](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F4cfd2bf6-6fc3-42f6-9386-e155704e7c02%2Fcc8d63b7-59e4-4274-8cf6-8b6052205a51%2Fzc2aiq_processed.jpeg&w=3840&q=75)
Transcribed Image Text:The fold functions compute a value over a list (or some other type that is foldable) by applying an
operator to the list elements and a neutral element. The foldl function assumes that the operator
is left associative, the foldr function assumes that the operatore is right associative. For example,
the function application
foldl (+) 0 [3,5,2,1]
1
results in the computation of (((0+3)+5)+2)+1) and the function application
foldr (+) 0 [3,5,2,1]
1
results in the computation of (3+(5+(2+(1+0)). The value computed by the fold functions may be
more complex than a simple scalar. It is very well possible to construct a new list as part of the
fold. For example:
map' :: (a -> b) -> [a] -> [b]
map' f xs = foldr ((:) . f) [] xs
1
The evaluation of map' succ [1,2,3] results in the list [2,3,4]. There are several duality theo-
rems that can be stated for fold functions. Prove the following three duality theorems:
a) Let op be an associative operation with e as the neutral element:
op is associative: (x op y) op z = x op (y op z)
e is neutral element: e op x = x and x op e = x
Then the following holds for finite lists xs:
foldr op e xs = foldl op e XS
b) Let op1 and op2 be two operations for which
x `op1 (y `op2 z) = (x `op1 y)`op2` z
x `op1 e
= e `op2` x
holds. Then the following holds for finite lists xs:
foldr op1 e xs = foldl op2 e xs
c) Let op be an associative operation and xs a finite list. Then
foldr op a xs = foldl op' a (reverse xs)
holds with
х ор' у 3 у ор х
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 4 steps
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
