---------------------------------------------------------------------------
{-
Enumerating the Zappa-Szep products of (N, 0, +) and (N, 0, +)
T. Uustalu, May 2012
Code to accompany:
D. Ahman, T. Uustalu. Distributive laws of directed containers.
Progress in Inform., v. 10, pp. 3-18, 2013.
-}
---------------------------------------------------------------------------
{-
As this is about two free monoids, we only have to decide what we
want to do at the generators. The rest is determined by the laws of a
Zappa-Szep product.
The idea is not mine, I borrowed it from
V. H. Fernandes, T. M. Quinteiro. Bilateral semidirect product
decompositions of transformation monoids. Semigroup Forum, v. 82,
n. 2, pp. 271-287, 2011.
-}
-----------------------------------------------------------------------
{-# LANGUAGE NPlusKPatterns #-}
-- The two monoids (I mean Nat, but use Int)
type P0 = Int
type P1 = Int
-- You can choose the two parameters c0, c1 below.
-- On certain combinations of the parameters,
-- the program won't terminate, on others it is fine.
c0 :: P0
c0 = 0 -- choose your own value
c1 :: P1
c1 = 0 -- choose your own value
-- The matching pairs q0, q1
q0 :: P1 -> P0 -> P0
q0 p1 0 = 0
q0 0 p0 = p0
q0 1 1 = c0
q0 (p1+1) 1 = q0 p1 (q0 1 1)
q0 p1 (p0+1) = q0 p1 1 + q0 (q1 p1 1) p0
q1 :: P1 -> P0 -> P1
q1 0 p0 = 0
q1 p1 0 = p1
q1 1 1 = c1
q1 (p1+1) 1 = q1 p1 (q0 1 1) + q1 1 1
q1 p1 (p0+1) = q1 (q1 p1 1) p0
q :: P1 -> P0 -> (P0, P1)
q p1 p0 = (q0 p1 p0, q1 p1 p0)
test = [ q p1 p0 | p1 <- [0..4], p0 <- [0..4] ]
-- multiplication of the Zappa-Szep product
(+++) :: (P0, P1) -> (P0, P1) -> (P0, P1)
(p0, p1) +++ (p0', p1') = (p0 + q0 p1 p0', q1 p1 p0' + p1')
{-
(c0, c1) = (1, 1) gives
q p1 p0 = (p0, p1) -- this is the case of the direct product
(c0, c1) = (1, 0) gives
q p1 0 = (0, p1)
q p1 (p0+1) = (p0+1, 0)
so in particular q0 p1 p0 = p0
-- whenever c0 = 1, we have a semidirect product, as
q0 is just the 2nd projection
(c0, c1) = (0, 0) gives
q p1 p0 = (p0-p1, p1-p0)
(c0, c1) = (2, 0) gives
q p1 0 = (0, p1)
q p1 (p0+1) = (p1+ p0+1, 0)
(c0, c1) = (3, 0) gives
q p1 0 = (0, p1)
q p1 (p0+1) = (2*p1+ p0+1, 0)
generally (c0, c1) = (n+1, 0) gives
q p1 0 = (0, p1)
q p1 (p0+1) = (n*p1+ p0+1, 0)
(c0, c1) = (2, 1) gives
q p1 p0 = (p0*2^p1, p1)
generally (c0, c1) = (n, 1) (where n /= 0) gives
q p1 p0 = (p0*n^p1, p1)
-}