[Solved] ICS Problem sheet 8

You are given the following digital circuit. The circuit may as well be found online at http:// simulator.io/board/pu8qlKwg1J/3 (but there is no guarantee that it persists).

1. Write down the truth table defining the outputs y₀, y₁, and y.
2. Write down the boolean expressions defining y₀, y₁, and y.
3. Describe in your own words what the circuit is doing and how it might be used.

Problem 8.2: fold function duality theorems

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

1 foldl (+) 0 [3,5,2,1]

results in the computation of ((((0+3)+5)+2)+1) and the function application

1 foldr (+) 0 [3,5,2,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

The evaluation of map succ [1,2,3] results in the list [2,3,4]. There are several duality theorems that can be stated for fold functions. Prove the following three duality theorems:

1. 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

1. Let op1 and op2 be two operations for which
   • `op1` (y `op2` z) = (x `op1` y) `op2` zx `op1` e = e `op2` x

holds. Then the following holds for finite lists xs:

foldr op1 e xs = foldl op2 e xs

1. Let op be an associative operation and xs a finite list. Then

foldr op a xs = foldl op a (reverse xs)

holds with

• op y = y op x