# SICP Solutions

### Section - 2.2 - Hierarchical Data and the Closure Property

#### Exercise 2.38

Procedures for fold-left and fold-right:

Fold-Right:

$a_1 \text{ op } (a_2 \text{ op } (a_3 \text{ op } ... (a_n \text{ op } \text{ init }) ... ))$.

Eg: If $op = \times$ and $n = 4$ :

$a_1 \times (a_2 \times (a_3 \times (a_4 \times \text{ init })))$.

Fold-Left:

$((...(\text{ init } \text{ op } a_1) \text{ op } a_2) \text{ op } a_3) \text{ op } ... ) \text{ op } a_n$.

Eg: If $op = \times$ and $n = 4$ :

$(((\text{ init } \times a_1) \times a_2) \times a_3) \times a_4$.

If fold-right and fold-left produce same values then:

$a_1 \text{ op } (a_2 \text{ op } (a_3 \text{ op } ... (a_n \text{ op } \text{ init }) ... )) = ((...(\text{ init } \text{ op } a_1) \text{ op } a_2) \text{ op } a_3) \text{ op } ... ) \text{ op } a_n$.

For eg: if $n = 4$ and $op = \times$:

$a_1 \times (a_2 \times (a_3 \times (a_4 \times \text{ init }))) = (((\text{ init } \times a_1) \times a_2) \times a_3) \times a_4$.

Clearly this property is called associative in mathematics.