0 | module Chem.Parity
 1 |
 2 | import Derive.Prelude
 3 |
 4 | %default total
 5 | %language ElabReflection
 6 |
 7 | public export
 8 | data Parity = Even | Odd
 9 |
10 | %runElab derive "Parity" [Show,Eq,Ord]
11 |
12 | public export
13 | Semigroup Parity where
14 |   Even <+> p    = p
15 |   Odd  <+> Even = Odd
16 |   Odd  <+> Odd  = Even
17 |
18 | public export
19 | Monoid Parity where
20 |   neutral = Even
21 |
22 | export %inline
23 | Cast Nat Parity where
24 |   cast n =
25 |     case prim__and_Integer (cast n) 1 of
26 |       0 => Even
27 |       _ => Odd
28 |
29 | ||| Computes the parity of a permutation, that is, the number
30 | ||| of swaps required to convert the given list into an ordered
31 | ||| list.
32 | |||
33 | ||| Note: The list is expected to hold no duplicates
34 | export
35 | parity : Ord a => List a -> Parity
36 | parity []        = Even
37 | parity (x :: xs) = cast (count (< x) xs) <+> parity xs
38 |
39 | ||| Tests if the given two permutations have the same parity.
40 | |||
41 | ||| Does not verify if the two lists are actually permutations of
42 | ||| the same sequence.
43 | export
44 | sameParity : Ord a => (xs,ys : List a) -> Bool
45 | sameParity xs ys = parity xs == parity ys
46 |