# Assignment 2

## Problems

## Problem 1

Integers, like booleans, do not have a natural associative operation. However, both addition and multiplication are associative operations on integers. Write `Semigroup`

instances for the `Sum`

and `Product`

types wrapping `Int`

in the starter code, mirroring the implementations of `Any`

and `All`

.

*See solution to Problem 3.*

## Problem 2

The default given above has \(O(n)\) performance, which is less efficient than the best general implementation. Using the associative property of `<>`

, provide a more efficient implementation, `stimes'`

, with time complexity \(O(\log n)\).

```
stimes' :: (Semigroup a, Integral b) => b -> a -> a
stimes' n x
| n <= 0 = error "positive multiplier expected"
| n == 1 = x
| even n = stimes' m x <> stimes' m x
| otherwise = stimes' (m + 1) x <> stimes' m x
where m = n `div` 2
```

## Problem 3

While \(O(\log n)\) is the best possible performance in general, specific instances can perform even better. Extend your instances for `Sum`

and `Product`

with \(O(1)\) implementations of `stimes`

.

```
instance Semigroup Sum where
(Sum a) <> (Sum b) = Sum $ a + b
stimes n (Sum x)
| n <= 0 = error "positive multiplier expected"
| otherwise = Sum $ x * (fromIntegral n)
instance Semigroup Product where
(Product a) <> (Product b) = Product $ a * b
stimes n (Product x)
| n <= 0 = error "positive multiplier expected"
| otherwise = Product $ x ^ (fromIntegral n)
```