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
Product types wrapping
Int in the starter code, mirroring the implementations of
See solution to Problem 3.
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)\).
While \(O(\log n)\) is the best possible performance in general, specific instances can perform even better. Extend your instances for
Product with \(O(1)\) implementations of
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)