Composing permutations in Set 9a

[Sose]

Hey, I'm not an expert on this and it is possible I'm wrong but I think there is an issue with the tests in Chapter 9a. My compose function seems to pass any tests related to it and my permute function fails only when checked together with compose (although there aren't many automated tests but I tested with the examples given in comments).

According to http://www.efgh.com/math/algebra/permutations.htm the composition of two permutations is the same as the composition of two functions.

(f . g)(x) = f(g(x)) (g is applied first and then f)

Composing permutations should follow the same rule? permute (p `compose` q) xs = permute p (permute q xs) (apply q first, then p)

However, the explanation in Set9a.hs and the tests in Set9aTest.hs seem to test that permute (p `compose` q) xs = permute q (permute p xs)

*** Failed! Falsified (after 2 tests):
permute (compose p q) xs == permute q (permute p xs) failed:
  p was [(0,0),(1,3),(2,2),(3,1),(4,4)]
  q was [(0,1),(1,4),(2,0),(3,3),(4,2)], and
  xs was "cdbae";
  permute (compose p q) xs evaluated to "daceb",
  while permute q (permute p xs) evaluated to "aecdb"

I tried to translate the composition example from the website to Haskell like this

-- "Hence {1,3,2} ◌ {2,1,3} = {2,3,1}."
p1 = [(0, 0), (1, 2), (2, 1)] :: Permutation -- using {0, 2, 1} instead of {1, 3, 2}
p2 = [(0, 1), (1, 0), (2, 2)] :: Permutation -- {1, 0, 2} instead of {2, 1, 3}

c1 = p1 `compose` p2 -- => [(0,1),(1,2),(2,0)] -- {1, 2, 0} or with one added to each index {2, 3, 1}

-- "Similarly, it can be shown that {2,1,3} ◌ {1,3,2} = {3,1,2}"
c2 = p2 `compose` p1 -- => [(0,2),(1,0),(2,1)]

-- testing
str = "abc"
ex1 = permute c str
ex1' = permute p1 (permute p2 str) -- p2 applied first
result = ex1 == ex1' -- => True

[opqdonut]

Hi, thanks for bringing that up!

The issue here is that the arguments to compose are indeed "the wrong way around" compared to mathematics. This can be seen from the types. Compare

compose :: (Eq a, Eq b) => [(a,b)] -> [(b,c)] -> [(a,c)]
(.) :: (b -> c) -> (a -> b) -> a -> c

I'll try to clarify the exercise text a bit. Also, it looks like the tests pretty much only test permute with compose, so I guess your permute is wrong. I'll add a simpler test for just permute that might help you.

[opqdonut]

Check the note I added to the exercise description and the new test for permute. Perhaps they'll help you!

(You can get the new exercise template and test using git pull)

[Sose]

Ah, now I see how my solution is wrong. Thanks for clarifying and adding the new test! I guess this can be closed