Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

""" 

Cartesian Product Functorial Construction 

 

AUTHORS: 

 

- Nicolas M. Thiery (2008-2010): initial revision and refactorization 

""" 

#***************************************************************************** 

# Copyright (C) 2010 Nicolas M. Thiery <nthiery at users.sf.net> 

# 

# Distributed under the terms of the GNU General Public License (GPL) 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

from six.moves import range 

 

from sage.misc.lazy_import import lazy_import 

from sage.categories.covariant_functorial_construction import CovariantFunctorialConstruction, CovariantConstructionCategory 

from sage.categories.pushout import MultivariateConstructionFunctor 

 

native_python_containers = set([tuple, list, set, frozenset, range]) 

 

class CartesianProductFunctor(CovariantFunctorialConstruction, MultivariateConstructionFunctor): 

""" 

A singleton class for the Cartesian product functor. 

 

EXAMPLES:: 

 

sage: cartesian_product 

The cartesian_product functorial construction 

 

``cartesian_product`` takes a finite collection of sets, and 

constructs the Cartesian product of those sets:: 

 

sage: A = FiniteEnumeratedSet(['a','b','c']) 

sage: B = FiniteEnumeratedSet([1,2]) 

sage: C = cartesian_product([A, B]); C 

The Cartesian product of ({'a', 'b', 'c'}, {1, 2}) 

sage: C.an_element() 

('a', 1) 

sage: C.list() # todo: not implemented 

[['a', 1], ['a', 2], ['b', 1], ['b', 2], ['c', 1], ['c', 2]] 

 

If those sets are endowed with more structure, say they are 

monoids (hence in the category `Monoids()`), then the result is 

automatically endowed with its natural monoid structure:: 

 

sage: M = Monoids().example() 

sage: M 

An example of a monoid: the free monoid generated by ('a', 'b', 'c', 'd') 

sage: M.rename('M') 

sage: C = cartesian_product([M, ZZ, QQ]) 

sage: C 

The Cartesian product of (M, Integer Ring, Rational Field) 

sage: C.an_element() 

('abcd', 1, 1/2) 

sage: C.an_element()^2 

('abcdabcd', 1, 1/4) 

sage: C.category() 

Category of Cartesian products of monoids 

 

sage: Monoids().CartesianProducts() 

Category of Cartesian products of monoids 

 

The Cartesian product functor is covariant: if ``A`` is a 

subcategory of ``B``, then ``A.CartesianProducts()`` is a 

subcategory of ``B.CartesianProducts()`` (see also 

:class:`~sage.categories.covariant_functorial_construction.CovariantFunctorialConstruction`):: 

 

sage: C.categories() 

[Category of Cartesian products of monoids, 

Category of monoids, 

Category of Cartesian products of semigroups, 

Category of semigroups, 

Category of Cartesian products of unital magmas, 

Category of Cartesian products of magmas, 

Category of unital magmas, 

Category of magmas, 

Category of Cartesian products of sets, 

Category of sets, ...] 

 

[Category of Cartesian products of monoids, 

Category of monoids, 

Category of Cartesian products of semigroups, 

Category of semigroups, 

Category of Cartesian products of magmas, 

Category of unital magmas, 

Category of magmas, 

Category of Cartesian products of sets, 

Category of sets, 

Category of sets with partial maps, 

Category of objects] 

 

Hence, the role of ``Monoids().CartesianProducts()`` is solely to 

provide mathematical information and algorithms which are relevant 

to Cartesian product of monoids. For example, it specifies that 

the result is again a monoid, and that its multiplicative unit is 

the Cartesian product of the units of the underlying sets:: 

 

sage: C.one() 

('', 1, 1) 

 

Those are implemented in the nested class 

:class:`Monoids.CartesianProducts 

<sage.categories.monoids.Monoids.CartesianProducts>` of 

``Monoids(QQ)``. This nested class is itself a subclass of 

:class:`CartesianProductsCategory`. 

 

""" 

_functor_name = "cartesian_product" 

_functor_category = "CartesianProducts" 

symbol = " (+) " 

 

def __init__(self): 

r""" 

Constructor. See :class:`CartesianProductFunctor` for details. 

 

TESTS:: 

 

sage: from sage.categories.cartesian_product import CartesianProductFunctor 

sage: CartesianProductFunctor() 

The cartesian_product functorial construction 

""" 

CovariantFunctorialConstruction.__init__(self) 

from sage.categories.sets_cat import Sets 

MultivariateConstructionFunctor.__init__(self, Sets(), Sets()) 

 

def __call__(self, args, **kwds): 

r""" 

Functorial construction application. 

 

This specializes the generic ``__call__`` from 

:class:`CovariantFunctorialConstruction` to: 

 

- handle the following plain Python containers as input: 

:class:`frozenset`, :class:`list`, :class:`set`, 

:class:`tuple`, and :class:`xrange` (Python3 ``range``). 

 

- handle the empty list of factors. 

 

See the examples below. 

 

EXAMPLES:: 

 

sage: cartesian_product([[0,1], ('a','b','c')]) 

The Cartesian product of ({0, 1}, {'a', 'b', 'c'}) 

sage: _.category() 

Category of Cartesian products of finite enumerated sets 

 

sage: cartesian_product([set([0,1,2]), [0,1]]) 

The Cartesian product of ({0, 1, 2}, {0, 1}) 

sage: _.category() 

Category of Cartesian products of sets 

 

Check that the empty product is handled correctly: 

 

sage: C = cartesian_product([]) 

sage: C 

The Cartesian product of () 

sage: C.cardinality() 

1 

sage: C.an_element() 

() 

sage: C.category() 

Category of Cartesian products of sets 

 

Check that Python3 ``range`` is handled correctly:: 

 

sage: from six.moves import range as py3range 

sage: C = cartesian_product([py3range(2), py3range(2)]) 

sage: list(C) 

[(0, 0), (0, 1), (1, 0), (1, 1)] 

sage: C.category() 

Category of Cartesian products of finite enumerated sets 

""" 

if any(type(arg) in native_python_containers for arg in args): 

from sage.categories.sets_cat import Sets 

S = Sets() 

args = [S(a, enumerated_set=True) for a in args] 

elif not args: 

from sage.categories.sets_cat import Sets 

from sage.sets.cartesian_product import CartesianProduct 

return CartesianProduct((), Sets().CartesianProducts()) 

 

return super(CartesianProductFunctor, self).__call__(args, **kwds) 

 

class CartesianProductsCategory(CovariantConstructionCategory): 

""" 

An abstract base class for all ``CartesianProducts`` categories. 

 

TESTS:: 

 

sage: C = Sets().CartesianProducts() 

sage: C 

Category of Cartesian products of sets 

sage: C.base_category() 

Category of sets 

sage: latex(C) 

\mathbf{CartesianProducts}(\mathbf{Sets}) 

""" 

 

_functor_category = "CartesianProducts" 

 

def _repr_object_names(self): 

""" 

EXAMPLES:: 

 

sage: ModulesWithBasis(QQ).CartesianProducts() # indirect doctest 

Category of Cartesian products of vector spaces with basis over Rational Field 

 

""" 

# This method is only required for the capital `C` 

return "Cartesian products of %s"%(self.base_category()._repr_object_names()) 

 

def CartesianProducts(self): 

""" 

Return the category of (finite) Cartesian products of objects 

of ``self``. 

 

By associativity of Cartesian products, this is ``self`` (a Cartesian 

product of Cartesian products of `A`'s is a Cartesian product of 

`A`'s). 

 

EXAMPLES:: 

 

sage: ModulesWithBasis(QQ).CartesianProducts().CartesianProducts() 

Category of Cartesian products of vector spaces with basis over Rational Field 

""" 

return self 

 

def base_ring(self): 

""" 

The base ring of a Cartesian product is the base ring of the underlying category. 

 

EXAMPLES:: 

 

sage: Algebras(ZZ).CartesianProducts().base_ring() 

Integer Ring 

""" 

return self.base_category().base_ring() 

 

# Moved to avoid circular imports 

lazy_import('sage.categories.sets_cat', 'cartesian_product') 

""" 

The Cartesian product functorial construction 

 

See :class:`CartesianProductFunctor` for more information 

 

EXAMPLES:: 

 

sage: cartesian_product 

The cartesian_product functorial construction 

"""