Coverage for /usr/lib/python3/dist-packages/sympy/strategies/tree.py: 53%

1from functools import partial 

2from sympy.strategies import chain, minimize 

3from sympy.strategies.core import identity 

4import sympy.strategies.branch as branch 

5from sympy.strategies.branch import yieldify 

6 

7 

8def treeapply(tree, join, leaf=identity): 

9 """ Apply functions onto recursive containers (tree). 

10 

11 Explanation 

12 =========== 

13 

14 join - a dictionary mapping container types to functions 

15 e.g. ``{list: minimize, tuple: chain}`` 

16 

17 Keys are containers/iterables. Values are functions [a] -> a. 

18 

19 Examples 

20 ======== 

21 

22 >>> from sympy.strategies.tree import treeapply 

23 >>> tree = [(3, 2), (4, 1)] 

24 >>> treeapply(tree, {list: max, tuple: min}) 

25 2 

26 

27 >>> add = lambda *args: sum(args) 

28 >>> def mul(*args): 

29 ... total = 1 

30 ... for arg in args: 

31 ... total *= arg 

32 ... return total 

33 >>> treeapply(tree, {list: mul, tuple: add}) 

34 25 

35 """ 

36 for typ in join: 

37 if isinstance(tree, typ): 

38 return join[typ](*map(partial(treeapply, join=join, leaf=leaf), 

39 tree)) 

40 return leaf(tree) 

41 

42 

43def greedy(tree, objective=identity, **kwargs): 

44 """ Execute a strategic tree. Select alternatives greedily 

45 

46 Trees 

47 ----- 

48 

49 Nodes in a tree can be either 

50 

51 function - a leaf 

52 list - a selection among operations 

53 tuple - a sequence of chained operations 

54 

55 Textual examples 

56 ---------------- 

57 

58 Text: Run f, then run g, e.g. ``lambda x: g(f(x))`` 

59 Code: ``(f, g)`` 

60 

61 Text: Run either f or g, whichever minimizes the objective 

62 Code: ``[f, g]`` 

63 

64 Textx: Run either f or g, whichever is better, then run h 

65 Code: ``([f, g], h)`` 

66 

67 Text: Either expand then simplify or try factor then foosimp. Finally print 

68 Code: ``([(expand, simplify), (factor, foosimp)], print)`` 

69 

70 Objective 

71 --------- 

72 

73 "Better" is determined by the objective keyword. This function makes 

74 choices to minimize the objective. It defaults to the identity. 

75 

76 Examples 

77 ======== 

78 

79 >>> from sympy.strategies.tree import greedy 

80 >>> inc = lambda x: x + 1 

81 >>> dec = lambda x: x - 1 

82 >>> double = lambda x: 2*x 

83 

84 >>> tree = [inc, (dec, double)] # either inc or dec-then-double 

85 >>> fn = greedy(tree) 

86 >>> fn(4) # lowest value comes from the inc 

87 5 

88 >>> fn(1) # lowest value comes from dec then double 

89 0 

90 

91 This function selects between options in a tuple. The result is chosen 

92 that minimizes the objective function. 

93 

94 >>> fn = greedy(tree, objective=lambda x: -x) # maximize 

95 >>> fn(4) # highest value comes from the dec then double 

96 6 

97 >>> fn(1) # highest value comes from the inc 

98 2 

99 

100 Greediness 

101 ---------- 

102 

103 This is a greedy algorithm. In the example: 

104 

105 ([a, b], c) # do either a or b, then do c 

106 

107 the choice between running ``a`` or ``b`` is made without foresight to c 

108 """ 

109 optimize = partial(minimize, objective=objective) 

110 return treeapply(tree, {list: optimize, tuple: chain}, **kwargs) 

111 

112 

113def allresults(tree, leaf=yieldify): 

114 """ Execute a strategic tree. Return all possibilities. 

115 

116 Returns a lazy iterator of all possible results 

117 

118 Exhaustiveness 

119 -------------- 

120 

121 This is an exhaustive algorithm. In the example 

122 

123 ([a, b], [c, d]) 

124 

125 All of the results from 

126 

127 (a, c), (b, c), (a, d), (b, d) 

128 

129 are returned. This can lead to combinatorial blowup. 

130 

131 See sympy.strategies.greedy for details on input 

132 """ 

133 return treeapply(tree, {list: branch.multiplex, tuple: branch.chain}, 

134 leaf=leaf) 

135 

136 

137def brute(tree, objective=identity, **kwargs): 

138 return lambda expr: min(tuple(allresults(tree, **kwargs)(expr)), 

139 key=objective)