Is this type really associative or just ignoring the 3rd type?

Learn
#1

This is from the book Get Programming with Haskell

import Data.Semigroup

data Color = Red |
	Yellow |
	Blue |
	Green |
	Purple |
	Orange |
	Brown deriving (Show,Eq)

This is the first implementation of Semigroup Color. The author said it is “non-associative”:

instance Semigroup Color where
	(<>) Red Blue = Purple
	(<>) Blue Red = Purple
	(<>) Yellow Blue = Green
	(<>) Blue Yellow = Green
	(<>) Yellow Red = Orange
	(<>) Red Yellow = Orange
	(<>) a b = if a == b
			   then a
			   else Brown

This implementation is said to be associative:

instance Semigroup Color where
	(<>) Red Blue = Purple
	(<>) Blue Red = Purple
	(<>) Yellow Blue = Green
	(<>) Blue Yellow = Green
	(<>) Yellow Red = Orange
	(<>) Red Yellow = Orange
	(<>) a b | a == b = a
			 | all (`elem` [Red,Blue,Purple]) [a,b] = Purple
			 | all (`elem` [Blue,Yellow,Green]) [a,b] = Green
			 | all (`elem` [Red,Yellow,Orange]) [a,b] = Orange
			 | otherwise = Brown

Example usage:

First implementation

> (Green <> Blue) <> Yellow
--  Brown

Second implementation

> (Green <> Blue) <> Yellow  returns Green
-- Green

It looks to me like the second implementation is just ignoring the 3rd argument and that isn’t really “associative”.

Is it ignoring the 3rd argument?
I don’t see anything that evaluates 3 colors. Even the last (<>) only has a b, not a b c and then check if both a and b are in in one of the lists in the guards.

#2

Indeed <> is a function of two arguments, similarly to how + is a function of two arguments. We evaluate the operation in the parenthesis first, which returns a single value, and then we can evaluate the outer operation which has two arguments now.

Associativity means that where you place the parenthesis (meaning which <> operation you evaluate first) doesn’t change the final result.

For the first implementation this is not true. Here are the two cases:

left first:

> (Green <> Blue) <> Yellow
=> (Brown) <> Yellow
=> Brown

right first:

> Green <> (Blue <> Yellow)
=> Green <> (Green)
=> Green

(Note that for an operation to be associative this exercise should work for each trio of possible values. It’s enough that one trio doesn’t work (in our case Green, Blue and Yellow) for an implementation to be disqualified.)

Try to do the same exercise with the second implementation and see that you get the same result whether you place the parenthesis on the right or on the left.

4 Likes
#3

I’m comfortable with associativity. I was thinking of instance Semigroup Color like a non-iterative function. Since you mention ‘first this then that’) now I’m looking at it as iterative.

For (Green <> Blue) <> Yellow
step 1
(Green <> Blue) returns Green
step 2
Green <> Yellow returns Green

For Green <> (Blue <> Yellow)
step 1
(Blue <> Yellow) returns Green
step 2
Green <> Green returns Green

It that is how it works (?), then I think I get it now.

1 Like
#4

Yep. Exactly like that.

1 Like