# -*- coding: utf8 -*-
"""
List functions
"""
from mathics.builtin.base import (
Builtin, Test, InvalidLevelspecError,
PartError, PartDepthError, PartRangeError, SympyFunction)
from mathics.builtin.scoping import dynamic_scoping
from mathics.core.expression import Expression, String, Symbol, Integer, Number
from mathics.core.evaluation import BreakInterrupt, ContinueInterrupt
from mathics.core.rules import Pattern
from mathics.core.convert import from_sympy
from mathics.builtin.algebra import cancel
import sympy
class List(Builtin):
"""
'List' is the head of lists.
>> Head[{1, 2, 3}]
= List
Lists can be nested:
>> {{a, b, {c, d}}}
= {{a, b, {c, d}}}
"""
attributes = ('Locked',)
def apply_makeboxes(self, items, f, evaluation):
'''MakeBoxes[{items___},
f:StandardForm|TraditionalForm|OutputForm|InputForm]'''
items = items.get_sequence()
return Expression(
'RowBox', Expression('List', *list_boxes(items, f, "{", "}")))
class ListQ(Test):
"""
<dl>
<dt>'ListQ[$expr$]'
<dd>tests whether $expr$ is a 'List'.
</dl>
>> ListQ[{1, 2, 3}]
= True
>> ListQ[{{1, 2}, {3, 4}}]
= True
>> ListQ[x]
= False
"""
def test(self, expr):
return expr.get_head_name() == 'List'
class NotListQ(Test):
def test(self, expr):
return expr.get_head_name() != 'List'
def list_boxes(items, f, open=None, close=None):
result = [Expression('MakeBoxes', item, f) for item in items]
if f.get_name() in ('OutputForm', 'InputForm'):
sep = ", "
else:
sep = ","
result = riffle(result, String(sep))
if len(items) > 1:
result = Expression('RowBox', Expression('List', *result))
elif items:
result = result[0]
if result:
result = [result]
else:
result = []
if open is not None and close is not None:
return [String(open)] + result + [String(close)]
else:
return result
class Length(Builtin):
"""
>> Length[{1, 2, 3}]
= 3
'Length' operates on the 'FullForm' of expressions:
>> Length[Exp[x]]
= 2
>> FullForm[Exp[x]]
= Power[E, x]
The length of atoms is 0:
>> Length[a]
= 0
Note that rational and complex numbers are atoms, although their 'FullForm' might suggest the opposite:
>> Length[1/3]
= 0
>> FullForm[1/3]
= Rational[1, 3]
"""
def apply(self, expr, evaluation):
'Length[expr_]'
if expr.is_atom():
return Integer(0)
else:
return Integer(len(expr.leaves))
class Span(Builtin):
"""
'Span' is the head of span ranges like '1;;3'.
>> ;; // FullForm
= Span[1, All]
>> 1;;4;;2 // FullForm
= Span[1, 4, 2]
>> 2;;-2 // FullForm
= Span[2, -2]
>> ;;3 // FullForm
= Span[1, 3]
## Test parsing : 8 cases to consider
#> a ;; b ;; c // FullForm
= Span[a, b, c]
#> ;; b ;; c // FullForm
= Span[1, b, c]
#> a ;; ;; c // FullForm
= Span[a, All, c]
#> ;; ;; c // FullForm
= Span[1, All, c]
#> a ;; b // FullForm
= Span[a, b]
#> ;; b // FullForm
= Span[1, b]
#> a ;; // FullForm
= Span[a, All]
#> ;; // FullForm
= Span[1, All]
"""
# operator = ';;'
# precedence = 305
pass
def join_lists(lists):
new_list = []
for list in lists:
new_list.extend(list)
return new_list
def get_part(list, indices):
" Simple part extraction. indices must be a list of python integers. "
def rec(cur, rest):
if rest:
pos = rest[0]
if cur.is_atom():
raise PartDepthError
try:
if pos > 0:
part = cur.leaves[pos - 1]
elif pos == 0:
part = cur.head
else:
part = cur.leaves[pos]
except IndexError:
raise PartRangeError
return rec(part, rest[1:])
else:
return cur
return rec(list, indices)
def set_part(list, indices, new):
" Simple part replacement. indices must be a list of python integers. "
def rec(cur, rest):
if len(rest) > 1:
pos = rest[0]
if cur.is_atom():
raise PartDepthError
try:
if pos > 0:
part = cur.leaves[pos - 1]
elif pos == 0:
part = cur.head
else:
part = cur.leaves[pos]
except IndexError:
raise PartRangeError
rec(part, rest[1:])
elif len(rest) == 1:
pos = rest[0]
if cur.is_atom():
raise PartDepthError
try:
if pos > 0:
cur.leaves[pos - 1] = new
elif pos == 0:
cur.head = new
else:
cur.leaves[pos] = new
except IndexError:
raise PartRangeError
rec(list, indices)
def walk_parts(list_of_list, indices, evaluation, assign_list=None):
list = list_of_list[0]
# To get rid of duplicate entries (TODO: could be made faster!)
list = list.copy()
list.set_positions()
list_of_list = [list]
result = list.copy()
result.set_positions()
inner_list = [result] # changed in loop
list_of_result = [result] # to be able to change it in replace_result
def replace_item(all, item, new):
if item.position is None:
all[0] = new
else:
item.position.replace(new)
for index in indices:
if index.has_form('Span', None):
if len(index.leaves) > 3:
evaluation.message('Part', 'span', index)
return False
start = 1
stop = None
step = 1
if len(index.leaves) > 0:
start = index.leaves[0].get_int_value()
if len(index.leaves) > 1:
stop = index.leaves[1].get_int_value()
if stop is None:
if index.leaves[1].get_name() == 'All':
stop = None
else:
evaluation.message('Part', 'span', index)
return False
if len(index.leaves) > 2:
step = index.leaves[2].get_int_value()
if start is None or step is None:
evaluation.message('Part', 'span', index)
return False
start, stop = python_seq(start, stop)
for inner in inner_list:
if inner.is_atom():
evaluation.message('Part', 'partd')
return False
if stop is None:
inner.leaves = inner.leaves[start::step]
else:
inner.leaves = inner.leaves[start:stop:step]
inner.original = None
inner.set_positions()
inner_list = join_lists(inner.leaves for inner in inner_list)
elif index.has_form('List', None):
index_list = index
indices = []
for index in index_list.leaves:
if not isinstance(index, Integer):
evaluation.message('Part', 'pspec', index_list)
return False
index = index.value
if index > 0:
py_index = index - 1
else:
py_index = index
indices.append((py_index, index))
for inner in inner_list:
if inner.is_atom():
evaluation.message('Part', 'partd')
return False
new_leaves = []
for py_index, index in indices:
try:
if index != 0:
part = inner.leaves[py_index]
else:
part = inner.head
new_leaves.append(part)
except IndexError:
evaluation.message('Part', 'partw', index, inner)
return False
inner.leaves = new_leaves
inner.original = None
inner.set_positions()
inner_list = join_lists(inner.leaves for inner in inner_list)
elif isinstance(index, Integer):
index = index.value
if index > 0:
py_index = index - 1
else:
py_index = index
for inner in inner_list:
if inner.is_atom():
evaluation.message('Part', 'partd')
return False
try:
if index != 0:
part = inner.leaves[py_index]
else:
part = inner.head
except IndexError:
evaluation.message('Part', 'partw', index, inner)
return False
replace_item(list_of_result, inner, part)
part.set_positions()
inner_list = [inner.leaves[py_index] for inner in inner_list]
result = list_of_result[0]
if assign_list is not None:
def process_level(item, assignment):
if item.is_atom():
replace_item(list_of_list, item.original, assignment)
elif (assignment.get_head_name() != 'List' or
len(item.leaves) != len(assignment.leaves)):
if item.original:
replace_item(list_of_list, item.original, assignment)
else:
for leaf in item.leaves:
process_level(leaf, assignment)
else:
for sub_item, sub_assignment in zip(item.leaves,
assignment.leaves):
process_level(sub_item, sub_assignment)
process_level(result, assign_list)
return list_of_list[0]
else:
return result
def is_in_level(current, depth, start=1, stop=None):
if stop is None:
stop = current
if start < 0:
start += current + depth + 1
if stop < 0:
stop += current + depth + 1
return start <= current <= stop
def walk_levels(expr, start=1, stop=None, current=0, heads=False,
callback=lambda l: l, include_pos=False, cur_pos=[]):
if expr.is_atom():
depth = 0
new_expr = expr
else:
depth = 0
if heads:
head, head_depth = walk_levels(
expr.head, start, stop, current + 1, heads, callback,
include_pos, cur_pos + [0])
else:
head = expr.head
leaves = []
for index, leaf in enumerate(expr.leaves):
leaf, leaf_depth = walk_levels(
leaf, start, stop, current + 1, heads, callback, include_pos,
cur_pos + [index + 1])
if leaf_depth + 1 > depth:
depth = leaf_depth + 1
leaves.append(leaf)
new_expr = Expression(head, *leaves)
if is_in_level(current, depth, start, stop):
if include_pos:
new_expr = callback(new_expr, cur_pos)
else:
new_expr = callback(new_expr)
return new_expr, depth
def python_levelspec(levelspec):
def value_to_level(expr):
value = expr.get_int_value()
if value is None:
if expr == Expression('DirectedInfinity', 1):
return None
else:
raise InvalidLevelspecError
else:
return value
if levelspec.has_form('List', None):
values = [value_to_level(leaf) for leaf in levelspec.leaves]
if len(values) == 1:
return values[0], values[0]
elif len(values) == 2:
return values[0], values[1]
else:
raise InvalidLevelspecError
else:
return 1, value_to_level(levelspec)
class Level(Builtin):
"""
<dl>
<dt>'Level[$expr$, $levelspec$]'
<dd>gives a list of all subexpressions of $expr$ at the level(s) specified by $levelspec$.
</dl>
Level uses standard level specifications:
<dl>
<dt>$n$
<dd>levels 1 through $n$
<dt>'Infinity'
<dd>all levels from level 1
<dt>'{$n$}'
<dd>level $n$ only
<dt>'{$m$, $n$}'
<dd>levels $m$ through $n$
</dl>
Level 0 corresponds to the whole expression.
A negative level '-$n$' consists of parts with depth $n$.
Level -1 is the set of atoms in an expression:
>> Level[a + b ^ 3 * f[2 x ^ 2], {-1}]
= {a, b, 3, 2, x, 2}
>> Level[{{{{a}}}}, 3]
= {{a}, {{a}}, {{{a}}}}
>> Level[{{{{a}}}}, -4]
= {{{{a}}}}
>> Level[{{{{a}}}}, -5]
= {}
>> Level[h0[h1[h2[h3[a]]]], {0, -1}]
= {a, h3[a], h2[h3[a]], h1[h2[h3[a]]], h0[h1[h2[h3[a]]]]}
Use the option 'Heads -> True' to include heads:
>> Level[{{{{a}}}}, 3, Heads -> True]
= {List, List, List, {a}, {{a}}, {{{a}}}}
>> Level[x^2 + y^3, 3, Heads -> True]
= {Plus, Power, x, 2, x ^ 2, Power, y, 3, y ^ 3}
>> Level[a ^ 2 + 2 * b, {-1}, Heads -> True]
= {Plus, Power, a, 2, Times, 2, b}
>> Level[f[g[h]][x], {-1}, Heads -> True]
= {f, g, h, x}
>> Level[f[g[h]][x], {-2, -1}, Heads -> True]
= {f, g, h, g[h], x, f[g[h]][x]}
"""
options = {
'Heads': 'False',
}
def apply(self, expr, ls, evaluation, options={}):
'Level[expr_, ls_, OptionsPattern[Level]]'
try:
start, stop = python_levelspec(ls)
except InvalidLevelspecError:
evaluation.message('Level', 'level', ls)
return
result = []
def callback(level):
result.append(level)
return level
heads = self.get_option(options, 'Heads', evaluation).is_true()
walk_levels(expr, start, stop, heads=heads, callback=callback)
return Expression('List', *result)
class LevelQ(Test):
"""
<dl>
<dt>'LevelQ[$expr$]'
<dd>tests whether $expr$ is a valid level specification.
</dl>
>> LevelQ[2]
= True
>> LevelQ[{2, 4}]
= True
>> LevelQ[Infinity]
= True
>> LevelQ[a + b]
= False
"""
def test(self, ls):
try:
start, stop = python_levelspec(ls)
return True
except InvalidLevelspecError:
return False
def python_seq(start, stop):
if start > 0:
start -= 1
if stop is not None and stop < 0:
stop += 1
if stop == 0:
stop = None
return start, stop
def convert_seq(seq):
start, stop, step = 1, None, 1
name = seq.get_name()
value = seq.get_int_value()
if name == 'All':
pass
elif name == 'None':
stop = 0
elif value is not None:
if value > 0:
stop = value
else:
start = value
elif seq.has_form('List', 1, 2, 3):
if len(seq.leaves) == 1:
start = stop = seq.leaves[0].get_int_value()
if stop is None:
return False
else:
start = seq.leaves[0].get_int_value()
stop = seq.leaves[1].get_int_value()
if start is None or stop is None:
return False
if len(seq.leaves) == 3:
step = seq.leaves[2].get_int_value()
if step is None:
return False
else:
return False
return (start, stop, step)
class Part(Builtin):
"""
>> A = {a, b, c, d};
>> A[[3]]
= c
Negative indizes count from the end:
>> {a, b, c}[[-2]]
= b
'Part' can be applied on any expression, not necessarily lists.
>> (a + b + c)[[2]]
= b
'$expr$[[0]]' gives the head of $expr$:
>> (a + b + c)[[0]]
= Plus
Parts of nested lists:
>> M = {{a, b}, {c, d}};
>> M[[1, 2]]
= b
You can use 'Span' to specify a range of parts:
>> {1, 2, 3, 4}[[2;;4]]
= {2, 3, 4}
>> {1, 2, 3, 4}[[2;;-1]]
= {2, 3, 4}
A list of parts extracts elements at certain indices:
>> {a, b, c, d}[[{1, 3, 3}]]
= {a, c, c}
Get a certain column of a matrix:
>> B = {{a, b, c}, {d, e, f}, {g, h, i}};
>> B[[;;, 2]]
= {b, e, h}
Extract a submatrix of 1st and 3rd row and the two last columns:
>> B = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
>> B[[{1, 3}, -2;;-1]]
= {{2, 3}, {8, 9}}
Further examples:
>> (a+b+c+d)[[-1;;-2]]
= 0
>> x[[2]]
: Part specification is longer than depth of object.
= x[[2]]
Assignments to parts are possible:
>> B[[;;, 2]] = {10, 11, 12}
= {10, 11, 12}
>> B
= {{1, 10, 3}, {4, 11, 6}, {7, 12, 9}}
>> B[[;;, 3]] = 13
= 13
>> B
= {{1, 10, 13}, {4, 11, 13}, {7, 12, 13}}
>> B[[1;;-2]] = t;
>> B
= {t, t, {7, 12, 13}}
>> F = Table[i*j*k, {i, 1, 3}, {j, 1, 3}, {k, 1, 3}];
>> F[[;; All, 2 ;; 3, 2]] = t;
>> F
= {{{1, 2, 3}, {2, t, 6}, {3, t, 9}}, {{2, 4, 6}, {4, t, 12}, {6, t, 18}}, {{3, 6, 9}, {6, t, 18}, {9, t, 27}}}
>> F[[;; All, 1 ;; 2, 3 ;; 3]] = k;
>> F
= {{{1, 2, k}, {2, t, k}, {3, t, 9}}, {{2, 4, k}, {4, t, k}, {6, t, 18}}, {{3, 6, k}, {6, t, k}, {9, t, 27}}}
Of course, part specifications have precedence over most arithmetic operations:
>> A[[1]] + B[[2]] + C[[3]] // Hold // FullForm
= Hold[Plus[Part[A, 1], Part[B, 2], Part[C, 3]]]
"""
attributes = ('NHoldRest', 'ReadProtected')
def apply_makeboxes(self, list, i, f, evaluation):
'''MakeBoxes[Part[list_, i___],
f:StandardForm|TraditionalForm|OutputForm|InputForm]'''
i = i.get_sequence()
list = Expression('MakeBoxes', list, f)
if f.get_name() in ('OutputForm', 'InputForm'):
open, close = "[[", "]]"
else:
open, close = u"\u301a", u"\u301b"
indices = list_boxes(i, f, open, close)
result = Expression('RowBox', Expression('List', list, *indices))
return result
def apply(self, list, i, evaluation):
'Part[list_, i___]'
indices = i.get_sequence()
result = walk_parts([list], indices, evaluation)
if result:
return result
class Partition(Builtin):
"""
<dl>
<dt>'Partition[$list$, $n$]'
<dd>partitions $list$ into sublists of length $n$.
<dt>'Parition[$list$, $n$, $d$]'
<dd>partitions $list$ into sublists of length $n$ which overlap $d$ indicies.
</dl>
>> Partition[{a, b, c, d, e, f}, 2]
= {{a, b}, {c, d}, {e, f}}
>> Partition[{a, b, c, d, e, f}, 3, 1]
= {{a, b, c}, {b, c, d}, {c, d, e}, {d, e, f}}
#> Partition[{a, b, c, d, e}, 2]
= {{a, b}, {c, d}}
"""
# TODO: Nested list length specifications
"""
>> Partition[{{11, 12, 13}, {21, 22, 23}, {31, 32, 33}}, {2, 2}, 1]
= {{{{11, 12}, {21, 22}}, {{12, 13}, {22, 23}}}, {{{21, 22}, {31, 32}}, {{22, 23}, {32, 33}}}}
"""
rules = {
'Parition[list_, n_, d_, k]': 'Partition[list, n, d, {k, k}]',
}
def chunks(self, l, n, d):
assert n > 0 and d > 0
return filter(lambda x: len(x) == n,
map(lambda i: l[i:i + n], xrange(0, len(l), d)))
def apply_no_overlap(self, l, n, evaluation):
'Partition[l_List, n_Integer]'
# TODO: Error checking
return Expression('List', *self.chunks(
l.get_leaves(), n.get_int_value(), n.get_int_value()))
def apply(self, l, n, d, evaluation):
'Partition[l_List, n_Integer, d_Integer]'
# TODO: Error checking
return Expression('List', *self.chunks(
l.get_leaves(), n.get_int_value(), d.get_int_value()))
class Extract(Builtin):
"""
<dl>
<dt>'Extract[$expr$, $list$]'
<dd>extracts parts of $expr$ specified by $list$.
<dt>'Extract[$expr$, {$list1$, $list2$, ...}]'
<dd>extracts a list of parts.
</dl>
'Extract[$expr$, $i$, $j$, ...]' is equivalent to 'Part[$expr$, {$i$, $j$, ...}]'.
>> Extract[a + b + c, {2}]
= b
>> Extract[{{a, b}, {c, d}}, {{1}, {2, 2}}]
= {{a, b}, d}
"""
attributes = ('NHoldRest',)
rules = {
'Extract[expr_, list_List]': 'Part[expr, Sequence @@ list]',
'Extract[expr_, {lists___List}]': u'Extract[expr, #]& /@ {lists}',
}
class First(Builtin):
"""
<dl>
<dt>'First[$expr$]'
<dd>returns the first elment in $expr$.
</dl>
'First[$expr$]' is equivalent to '$expr$[[1]]'.
>> First[{a, b, c}]
= a
>> First[a + b + c]
= a
>> First[x]
: Nonatomic expression expected.
= First[x]
"""
def apply(self, expr, evaluation):
'First[expr_]'
if expr.is_atom():
evaluation.message('First', 'normal')
return
return expr.leaves[0]
class Last(Builtin):
"""
<dl>
<dt>'Last[$expr$]'
<dd>returns the last elment in $expr$.
</dl>
'Last[$expr$]' is equivalent to '$expr$[[-1]]'.
>> Last[{a, b, c}]
= c
>> Last[x]
: Nonatomic expression expected.
= Last[x]
"""
def apply(self, expr, evaluation):
'Last[expr_]'
if expr.is_atom():
evaluation.message('Last', 'normal')
return
return expr.leaves[-1]
class Most(Builtin):
"""
<dl>
<dt>'Most[$expr$]'
<dd>returns $expr$ with the last element removed.
</dl>
'Most[$expr$]' is equivalent to '$expr$[[;;-2]]'.
>> Most[{a, b, c}]
= {a, b}
>> Most[a + b + c]
= a + b
>> Most[x]
: Nonatomic expression expected.
= Most[x]
"""
def apply(self, expr, evaluation):
'Most[expr_]'
if expr.is_atom():
evaluation.message('Most', 'normal')
return
return Expression(expr.head, *expr.leaves[:-1])
class Rest(Builtin):
"""
<dl>
<dt>'Rest[$expr$]'
<dd>returns $expr$ with the first element removed.
</dl>
'Rest[$expr$]' is equivalent to '$expr$[[2;;]]'.
>> Rest[{a, b, c}]
= {b, c}
>> Rest[a + b + c]
= b + c
>> Rest[x]
: Nonatomic expression expected.
= Rest[x]
"""
def apply(self, expr, evaluation):
'Rest[expr_]'
if expr.is_atom():
evaluation.message('Rest', 'normal')
return
return Expression(expr.head, *expr.leaves[1:])
class ReplacePart(Builtin):
"""
>> ReplacePart[{a, b, c}, 1 -> t]
= {t, b, c}
>> ReplacePart[{{a, b}, {c, d}}, {2, 1} -> t]
= {{a, b}, {t, d}}
>> ReplacePart[{{a, b}, {c, d}}, {{2, 1} -> t, {1, 1} -> t}]
= {{t, b}, {t, d}}
>> ReplacePart[{a, b, c}, {{1}, {2}} -> t]
= {t, t, c}
Delayed rules are evaluated once for each replacement:
>> n = 1;
>> ReplacePart[{a, b, c, d}, {{1}, {3}} :> n++]
= {1, b, 2, d}
Non-existing parts are simply ignored:
>> ReplacePart[{a, b, c}, 4 -> t]
= {a, b, c}
You can replace heads by replacing part 0:
>> ReplacePart[{a, b, c}, 0 -> Times]
= a b c
(This is equivalent to 'Apply'.)
Negative part numbers count from the end:
>> ReplacePart[{a, b, c}, -1 -> t]
= {a, b, t}
"""
messages = {
'reps': "`1` is not a list of replacement rules.",
}
rules = {
'ReplacePart[expr_, (Rule|RuleDelayed)[i_, new_]]': (
'ReplacePart[expr, {i -> new}]'),
'ReplacePart[expr_, Pattern[rule, '
'Rule|RuleDelayed][{indices___?(Head[#]===List&)}, new_]]': (
'ReplacePart[expr, rule[#, new]& /@ {indices}]'),
}
def apply(self, expr, replacements, evaluation):
'ReplacePart[expr_, {replacements___}]'
new_expr = expr.copy()
replacements = replacements.get_sequence()
for replacement in replacements:
if (not replacement.has_form('Rule', 2) and # noqa
not replacement.has_form('RuleDelayed', 2)):
evaluation.message('ReplacePart', 'reps',
Expression('List', *replacements))
return
position = replacement.leaves[0]
replace = replacement.leaves[1]
if position.has_form('List', None):
position = position.leaves
else:
position = [position]
for index, pos in enumerate(position):
value = pos.get_int_value()
if value is None:
position = None
break
else:
position[index] = value
if position is None:
continue
try:
if replacement.get_head_name() == 'RuleDelayed':
replace_value = replace.evaluate(evaluation)
else:
replace_value = replace
set_part(new_expr, position, replace_value)
except PartError:
pass
return new_expr
class Take(Builtin):
"""
>> Take[{a, b, c, d}, 3]
= {a, b, c}
>> Take[{a, b, c, d}, -2]
= {c, d}
>> Take[{a, b, c, d, e}, {2, -2}]
= {b, c, d}
Take a submatrix:
>> A = {{a, b, c}, {d, e, f}};
>> Take[A, 2, 2]
= {{a, b}, {d, e}}
Take a single column:
>> Take[A, All, {2}]
= {{b}, {e}}
"""
messages = {
'take': "Cannot take positions `1` through `2` in `3`.",
}
def apply(self, list, seqs, evaluation):
'Take[list_, seqs___]'
seqs = seqs.get_sequence()
list = list.copy()
inner_list = [list]
for seq in seqs:
seq_tuple = convert_seq(seq)
if not seq_tuple:
evaluation.message('Take', 'seqs', seq)
return
start, stop, step = seq_tuple
py_start, py_stop = python_seq(start, stop)
for inner in inner_list:
if (inner.is_atom() or # noqa
abs(start) > len(inner.leaves) or
stop is not None and abs(stop) > len(inner.leaves)):
evaluation.message('Take', 'take', start, Symbol(
'Infinity') if stop is None else stop, inner)
return
if stop is None:
inner.leaves = inner.leaves[py_start::step]
else:
inner.leaves = inner.leaves[py_start:py_stop:step]
inner_list = join_lists(inner.leaves for inner in inner_list)
return list
class Drop(Builtin):
"""
>> Drop[{a, b, c, d}, 3]
= {d}
>> Drop[{a, b, c, d}, -2]
= {a, b}
>> Drop[{a, b, c, d, e}, {2, -2}]
= {a, e}
Drop a submatrix:
>> A = Table[i*10 + j, {i, 4}, {j, 4}]
= {{11, 12, 13, 14}, {21, 22, 23, 24}, {31, 32, 33, 34}, {41, 42, 43, 44}}
>> Drop[A, {2, 3}, {2, 3}]
= {{11, 14}, {41, 44}}
"""
messages = {
'drop': "Cannot drop positions `1` through `2` in `3`.",
}
def apply(self, list, seqs, evaluation):
'Drop[list_, seqs___]'
seqs = seqs.get_sequence()
list = list.copy()
inner_list = [list]
for seq in seqs:
seq_tuple = convert_seq(seq)
if not seq_tuple:
evaluation.message('Drop', 'seqs', seq)
return
start, stop, step = seq_tuple
py_start, py_stop = python_seq(start, stop)
for inner in inner_list:
if (inner.is_atom() or # noqa
abs(start) > len(inner.leaves) or
stop is not None and abs(stop) > len(inner.leaves)):
evaluation.message('Drop', 'drop', start, stop, inner)
return
if stop is None:
del inner.leaves[py_start::step]
else:
del inner.leaves[py_start:py_stop:step]
inner_list = join_lists(inner.leaves for inner in inner_list)
return list
class Select(Builtin):
"""
>> Select[{-3, 0, 1, 3, a}, #>0&]
= {1, 3}
>> Select[f[a, 2, 3], NumberQ]
= f[2, 3]
>> Select[a, True]
: Nonatomic expression expected.
= Select[a, True]
"""
def apply(self, list, expr, evaluation):
'Select[list_, expr_]'
if list.is_atom():
evaluation.message('Select', 'normal')
return
new_leaves = []
for leaf in list.leaves:
test = Expression(expr, leaf)
if test.evaluate(evaluation).is_true():
new_leaves.append(leaf)
return Expression(list.head, *new_leaves)
class Split(Builtin):
"""
<dl>
<dt>'Split[$list$]'
<dd>splits $list$ into collections of consecutive identical elements.
<dt>'Split[$list$, $test$]'
<dd>splits $list$ based on whether the function $test$ yields 'True' on consecutive elements.
</dl>
>> Split[{x, x, x, y, x, y, y, z}]
= {{x, x, x}, {y}, {x}, {y, y}, {z}}
#> Split[{x, x, x, y, x, y, y, z}, x]
= {{x}, {x}, {x}, {y}, {x}, {y}, {y}, {z}}
Split into increasing or decreasing runs of elements
>> Split[{1, 5, 6, 3, 6, 1, 6, 3, 4, 5, 4}, Less]
= {{1, 5, 6}, {3, 6}, {1, 6}, {3, 4, 5}, {4}}
>> Split[{1, 5, 6, 3, 6, 1, 6, 3, 4, 5, 4}, Greater]
= {{1}, {5}, {6, 3}, {6, 1}, {6, 3}, {4}, {5, 4}}
Split based on first element
>> Split[{x -> a, x -> y, 2 -> a, z -> c, z -> a}, First[#1] === First[#2] &]
= {{x -> a, x -> y}, {2 -> a}, {z -> c, z -> a}}
#> Split[{}]
= {}
"""
rules = {
'Split[list_]': 'Split[list, SameQ]',
}
messages = {
'normal': 'Nonatomic expression expected at position `1` in `2`.',
}
def apply(self, mlist, test, evaluation):
'Split[mlist_, test_]'
expr = Expression('Split', mlist, test)
if mlist.is_atom():
evaluation.message('Select', 'normal', 1, expr)
return
if len(mlist.leaves) == 0:
result = []
else:
result = [[mlist.leaves[0]]]
for leaf in mlist.leaves[1:]:
applytest = Expression(test, result[-1][-1], leaf)
if applytest.evaluate(evaluation).is_true():
result[-1].append(leaf)
else:
result.append([leaf])
return Expression(mlist.head, *[Expression('List', *l)
for l in result])
class SplitBy(Builtin):
"""
<dl>
<dt>'Split[$list$, $f$]'
<dd>splits $list$ into collections of consecutive elements that give the same result when $f$ is applied.
</dl>
>> SplitBy[Range[1, 3, 1/3], Round]
= {{1, 4 / 3}, {5 / 3, 2, 7 / 3}, {8 / 3, 3}}
>> SplitBy[{1, 2, 1, 1.2}, {Round, Identity}]
= {{{1}}, {{2}}, {{1}, {1.2}}}
>> SplitBy[{1, 2, 1, 1.2}, {Round, Identity}]
= {{{1}}, {{2}}, {{1}, {1.2}}}
#> SplitBy[Tuples[{1, 2}, 3], First]
= {{{1, 1, 1}, {1, 1, 2}, {1, 2, 1}, {1, 2, 2}}, {{2, 1, 1}, {2, 1, 2}, {2, 2, 1}, {2, 2, 2}}}
"""
rules = {
'SplitBy[list_]': 'SplitBy[list, Identity]',
}
messages = {
'normal': 'Nonatomic expression expected at position `1` in `2`.',
}
def apply(self, mlist, func, evaluation):
'SplitBy[mlist_, func_?NotListQ]'
expr = Expression('Split', mlist, func)
if mlist.is_atom():
evaluation.message('Select', 'normal', 1, expr)
return
plist = [l for l in mlist.leaves]
result = [[plist[0]]]
prev = Expression(func, plist[0]).evaluate(evaluation)
for leaf in plist[1:]:
curr = Expression(func, leaf).evaluate(evaluation)
if curr == prev:
result[-1].append(leaf)
else:
result.append([leaf])
prev = curr
return Expression(mlist.head, *[Expression('List', *l)
for l in result])
def apply_multiple(self, mlist, funcs, evaluation):
'SplitBy[mlist_, funcs_?ListQ]'
expr = Expression('Split', mlist, funcs)
if mlist.is_atom():
evaluation.message('Select', 'normal', 1, expr)
return
result = mlist
for f in funcs.leaves[::-1]:
result = self.apply(result, f, evaluation)
return result
class Cases(Builtin):
rules = {
'Cases[list_, pattern_]': 'Select[list, MatchQ[#, pattern]&]',
}
class MemberQ(Builtin):
rules = {
'MemberQ[list_, pattern_]': (
'Length[Select[list, MatchQ[#, pattern]&]] > 0'),
}
class Range(Builtin):
"""
>> Range[5]
= {1, 2, 3, 4, 5}
>> Range[-3, 2]
= {-3, -2, -1, 0, 1, 2}
>> Range[0, 2, 1/3]
= {0, 1 / 3, 2 / 3, 1, 4 / 3, 5 / 3, 2}
"""
rules = {
'Range[imax_?RealNumberQ]': 'Range[1, imax, 1]',
'Range[imin_?RealNumberQ, imax_?RealNumberQ]': 'Range[imin, imax, 1]',
}
def apply(self, imin, imax, di, evaluation):
'Range[imin_?RealNumberQ, imax_?RealNumberQ, di_?RealNumberQ]'
imin = imin.value
imax = imax.value
di = di.value
index = imin
result = []
while index <= imax:
evaluation.check_stopped()
result.append(Number.from_mp(index))
index += di
return Expression('List', *result)
class _IterationFunction(Builtin):
attributes = ('HoldAll',)
rules = {
'%(name)s[expr_, {i_Symbol, imax_}]': (
'%(name)s[expr, {i, 1, imax, 1}]'),
'%(name)s[expr_, {i_Symbol, imin_, imax_}]': (
'%(name)s[expr, {i, imin, imax, 1}]'),
}
allow_loopcontrol = False
throw_iterb = True
def get_result(self, items):
pass
def apply_max(self, expr, imax, evaluation):
'%(name)s[expr_, {imax_}]'
index = 0
imax = imax.evaluate(evaluation).get_real_value()
if imax is None:
if self.throw_iterb:
evaluation.message(self.get_name(), 'iterb')
return
result = []
while index < imax:
evaluation.check_stopped()
try:
result.append(expr.evaluate(evaluation))
except ContinueInterrupt:
if self.allow_loopcontrol:
pass
else:
raise
except BreakInterrupt:
if self.allow_loopcontrol:
break
else:
raise
index += 1
return self.get_result(result)
def apply_iter(self, expr, i, imin, imax, di, evaluation):
'%(name)s[expr_, {i_Symbol, imin_, imax_, di_}]'
if isinstance(self, SympyFunction) and di.get_int_value() == 1:
whole_expr = Expression(
self.get_name(), expr, Expression('List', i, imin, imax))
sympy_expr = whole_expr.to_sympy()
# apply Together to produce results similar to Mathematica
result = sympy.together(sympy_expr)
result = from_sympy(result)
result = cancel(result)
if not result.same(whole_expr):
return result
index = imin.evaluate(evaluation)
imax = imax.evaluate(evaluation)
di = di.evaluate(evaluation)
result = []
while True:
cont = Expression('LessEqual', index, imax).evaluate(evaluation)
if cont == Symbol('False'):
break
if not cont.is_true():
if self.throw_iterb:
evaluation.message(self.get_name(), 'iterb')
return
evaluation.check_stopped()
try:
item = dynamic_scoping(
expr.evaluate, {i.name: index}, evaluation)
result.append(item)
except ContinueInterrupt:
if self.allow_loopcontrol:
pass
else:
raise
except BreakInterrupt:
if self.allow_loopcontrol:
break
else:
raise
index = Expression('Plus', index, di).evaluate(evaluation)
return self.get_result(result)
def apply_list(self, expr, i, items, evaluation):
'%(name)s[expr_, {i_Symbol, {items___}}]'
items = items.evaluate(evaluation).get_sequence()
result = []
for item in items:
evaluation.check_stopped()
try:
item = dynamic_scoping(
expr.evaluate, {i.name: item}, evaluation)
result.append(item)
except ContinueInterrupt:
if self.allow_loopcontrol:
pass
else:
raise
except BreakInterrupt:
if self.allow_loopcontrol:
break
else:
raise
return self.get_result(result)
def apply_multi(self, expr, first, sequ, evaluation):
'%(name)s[expr_, first_, sequ__]'
sequ = sequ.get_sequence()
name = self.get_name()
return Expression(name, Expression(name, expr, *sequ), first)
class ConstantArray(Builtin):
"""
>> ConstantArray[a, 3]
= {a, a, a}
>> ConstantArray[a, {2, 3}]
= {{a, a, a}, {a, a, a}}
"""
rules = {
'ConstantArray[c_, dims_]': 'Apply[Table[c, ##]&, List /@ dims]',
'ConstantArray[c_, n_Integer]': 'ConstantArray[c, {n}]',
}
class Array(Builtin):
"""
>> Array[f, 4]
= {f[1], f[2], f[3], f[4]}
>> Array[f, {2, 3}]
= {{f[1, 1], f[1, 2], f[1, 3]}, {f[2, 1], f[2, 2], f[2, 3]}}
>> Array[f, {2, 3}, 3]
= {{f[3, 3], f[3, 4], f[3, 5]}, {f[4, 3], f[4, 4], f[4, 5]}}
>> Array[f, {2, 3}, {4, 6}]
= {{f[4, 6], f[4, 7], f[4, 8]}, {f[5, 6], f[5, 7], f[5, 8]}}
>> Array[f, {2, 3}, 1, Plus]
= f[1, 1] + f[1, 2] + f[1, 3] + f[2, 1] + f[2, 2] + f[2, 3]
#> Array[f, {2, 3}, {1, 2, 3}]
: {2, 3} and {1, 2, 3} should have the same length.
= Array[f, {2, 3}, {1, 2, 3}]
#> Array[f, a]
: Single or list of non-negative integers expected at position 2.
= Array[f, a]
#> Array[f, 2, b]
: Single or list of non-negative integers expected at position 3.
= Array[f, 2, b]
"""
messages = {
'plen': "`1` and `2` should have the same length.",
}
def apply(self, f, dimsexpr, origins, head, evaluation):
'Array[f_, dimsexpr_, origins_:1, head_:List]'
if dimsexpr.has_form('List', None):
dims = dimsexpr.leaves[:]
else:
dims = [dimsexpr]
for index, dim in enumerate(dims):
value = dim.get_int_value()
if value is None:
evaluation.message('Array', 'ilsnn', 2)
return
dims[index] = value
if origins.has_form('List', None):
if len(origins.leaves) != len(dims):
evaluation.message('Array', 'plen', dimsexpr, origins)
return
origins = origins.leaves[:]
else:
origins = [origins] * len(dims)
for index, origin in enumerate(origins):
value = origin.get_int_value()
if value is None:
evaluation.message('Array', 'ilsnn', 3)
return
origins[index] = value
dims = zip(dims, origins)
def rec(rest_dims, current):
evaluation.check_stopped()
if rest_dims:
level = []
count, origin = rest_dims[0]
for index in range(origin, origin + count):
level.append(rec(rest_dims[1:], current + [index]))
return Expression(head, *level)
else:
return Expression(f, *(Integer(index) for index in current))
return rec(dims, [])
class Table(_IterationFunction):
"""
>> Table[x, {4}]
= {x, x, x, x}
>> n = 0;
>> Table[n = n + 1, {5}]
= {1, 2, 3, 4, 5}
>> Table[i, {i, 4}]
= {1, 2, 3, 4}
>> Table[i, {i, 2, 5}]
= {2, 3, 4, 5}
>> Table[i, {i, 2, 6, 2}]
= {2, 4, 6}
>> Table[i, {i, Pi, 2 Pi, Pi / 2}]
= {Pi, 3 Pi / 2, 2 Pi}
>> Table[x^2, {x, {a, b, c}}]
= {a ^ 2, b ^ 2, c ^ 2}
'Table' supports multi-dimensional tables:
>> Table[{i, j}, {i, {a, b}}, {j, 1, 2}]
= {{{a, 1}, {a, 2}}, {{b, 1}, {b, 2}}}
#> Table[x, {x,0,1/3}]
= {0}
#> Table[x, {x, -0.2, 3.9}]
= {-0.2, 0.8, 1.8, 2.8, 3.8}
"""
def get_result(self, items):
return Expression('List', *items)
class Join(Builtin):
"""
'Join' concatenates lists.
>> Join[{a, b}, {c, d, e}]
= {a, b, c, d, e}
>> Join[{{a, b}, {c, d}}, {{1, 2}, {3, 4}}]
= {{a, b}, {c, d}, {1, 2}, {3, 4}}
The concatenated expressions may have any head.
>> Join[a + b, c + d, e + f]
= a + b + c + d + e + f
However, it must be the same for all expressions.
>> Join[a + b, c * d]
: Heads Plus and Times are expected to be the same.
= Join[a + b, c d]
#> Join[x, y]
= Join[x, y]
#> Join[x + y, z]
= Join[x + y, z]
#> Join[x + y, y z, a]
: Heads Plus and Times are expected to be the same.
= Join[x + y, y z, a]
#> Join[x, y + z, y z]
= Join[x, y + z, y z]
"""
attributes = ('Flat', 'OneIdentity')
def apply(self, lists, evaluation):
'Join[lists___]'
result = []
head = None
for list in lists.get_sequence():
if list.is_atom():
return
if head is not None and list.get_head() != head:
evaluation.message('Join', 'heads', head, list.get_head())
return
head = list.get_head()
result.extend(list.leaves)
if result:
return Expression(head, *result)
else:
return Expression('List')
def get_tuples(items):
if not items:
yield []
else:
for item in items[0]:
for rest in get_tuples(items[1:]):
yield [item] + rest
class Tuples(Builtin):
"""
<dl>
<dt>'Tuples[$list$, $n$]'
<dd>returns a list of all $n$-tuples of elements in $list$.
<dt>'Tuples[{$list1$, $list2$, ...}]'
<dd>returns a list of tuples with elements from the given lists.
</dl>
>> Tuples[{a, b, c}, 2]
= {{a, a}, {a, b}, {a, c}, {b, a}, {b, b}, {b, c}, {c, a}, {c, b}, {c, c}}
>> Tuples[{}, 2]
= {}
>> Tuples[{a, b, c}, 0]
= {{}}
>> Tuples[{{a, b}, {1, 2, 3}}]
= {{a, 1}, {a, 2}, {a, 3}, {b, 1}, {b, 2}, {b, 3}}
The head of $list$ need not be 'List':
>> Tuples[f[a, b, c], 2]
= {f[a, a], f[a, b], f[a, c], f[b, a], f[b, b], f[b, c], f[c, a], f[c, b], f[c, c]}
However, when specifying multiple expressions, 'List' is always used:
>> Tuples[{f[a, b], g[c, d]}]
= {{a, c}, {a, d}, {b, c}, {b, d}}
"""
def apply_n(self, expr, n, evaluation):
'Tuples[expr_, n_]'
if expr.is_atom():
evaluation.message('Tuples', 'normal')
return
n = n.get_int_value()
if n is None or n < 0:
evaluation.message('Tuples', 'intnn')
return
items = expr.leaves
def iterate(n_rest):
evaluation.check_stopped()
if n_rest <= 0:
yield []
else:
for item in items:
for rest in iterate(n_rest - 1):
yield [item] + rest
return Expression('List', *(Expression(expr.head, *leaves)
for leaves in iterate(n)))
def apply_lists(self, exprs, evaluation):
'Tuples[{exprs___}]'
exprs = exprs.get_sequence()
items = []
for expr in exprs:
evaluation.check_stopped()
if expr.is_atom():
evaluation.message('Tuples', 'normal')
return
items.append(expr.leaves)
return Expression('List', *(Expression('List', *leaves)
for leaves in get_tuples(items)))
class Reap(Builtin):
"""
<dl>
<dt>'Reap[$expr$]'
<dd>gives the result of evaluating $expr$, together with all values sown during
this evaluation. Values sown with different tags are given in different lists.
<dt>'Reap[$expr$, $pattern$]'
<dd>only yields values sown with a tag matching $pattern$.
'Reap[$expr$]' is equivalent to 'Reap[$expr$, _]'.
<dt>'Reap[$expr$, {$pattern1$, $pattern2$, ...}]'
<dd>uses multiple patterns.
<dt>'Reap[$expr$, $pattern$, $f$]'
<dd>applies $f$ on each tag and the corresponding values sown
in the form '$f$[tag, {e1, e2, ...}]'.
</dl>
>> Reap[Sow[3]; Sow[1]]
= {1, {{3, 1}}}
>> Reap[Sow[2, {x, x, x}]; Sow[3, x]; Sow[4, y]; Sow[4, 1], {_Symbol, _Integer, x}, f]
= {4, {{f[x, {2, 2, 2, 3}], f[y, {4}]}, {f[1, {4}]}, {f[x, {2, 2, 2, 3}]}}}
Find the unique elements of a list, keeping their order:
>> Reap[Sow[Null, {a, a, b, d, c, a}], _, # &][[2]]
= {a, b, d, c}
Sown values are reaped by the innermost matching 'Reap':
>> Reap[Reap[Sow[a, x]; Sow[b, 1], _Symbol, Print["Inner: ", #1]&];, _, f]
| Inner: x
= {Null, {f[1, {b}]}}
When no value is sown, an empty list is returned:
>> Reap[x]
= {x, {}}
"""
attributes = ('HoldFirst',)
rules = {
'Reap[expr_, pattern_, f_]': (
'{#[[1]], #[[2, 1]]}& [Reap[expr, {pattern}, f]]'),
'Reap[expr_, pattern_]': 'Reap[expr, pattern, #2&]',
'Reap[expr_]': 'Reap[expr, _]',
}
def apply(self, expr, patterns, f, evaluation):
'Reap[expr_, {patterns___}, f_]'
patterns = patterns.get_sequence()
sown = [(Pattern.create(pattern), []) for pattern in patterns]
def listener(e, tag):
result = False
for pattern, items in sown:
if pattern.does_match(tag, evaluation):
for item in items:
if item[0].same(tag):
item[1].append(e)
break
else:
items.append((tag, [e]))
result = True
return result
evaluation.add_listener('sow', listener)
try:
result = expr.evaluate(evaluation)
items = []
for pattern, tags in sown:
list = Expression('List')
for tag, elements in tags:
list.leaves.append(Expression(
f, tag, Expression('List', *elements)))
items.append(list)
return Expression('List', result, Expression('List', *items))
finally:
evaluation.remove_listener('sow', listener)
class Sow(Builtin):
"""
<dl>
<dt>'Sow[$e$]'
<dd>sends the value $e$ to the innermost 'Reap'.
<dt>'Sow[$e$, $tag$]'
<dd>sows $e$ using $tag$. 'Sow[$e$]' is equivalent to 'Sow[$e$, Null]'.
<dt>'Sow[$e$, {$tag1$, $tag2$, ...}]'
<dd>uses multiple tags.
</dl>
"""
rules = {
'Sow[e_]': 'Sow[e, {Null}]',
'Sow[e_, tag_]': 'Sow[e, {tag}]',
}
def apply(self, e, tags, evaluation):
'Sow[e_, {tags___}]'
tags = tags.get_sequence()
for tag in tags:
evaluation.publish('sow', e, tag)
return e
class UnitVector(Builtin):
"""
>> UnitVector[2]
= {0, 1}
>> UnitVector[4, 3]
= {0, 0, 1, 0}
"""
messages = {
'nokun': "There is no unit vector in direction `1` in `2` dimensions.",
}
rules = {
'UnitVector[k_Integer]': 'UnitVector[2, k]',
}
def apply(self, n, k, evaluation):
'UnitVector[n_Integer, k_Integer]'
n = n.get_int_value()
k = k.get_int_value()
if n is None or k is None:
return
if not 1 <= k <= n:
evaluation.message('UnitVector', 'nokun', k, n)
return
def item(i):
if i == k:
return Integer(1)
else:
return Integer(0)
return Expression('List', *(item(i) for i in range(1, n + 1)))
def riffle(items, sep):
result = items[:1]
for item in items[1:]:
result.append(sep)
result.append(item)
return result
def riffle_lists(items, seps):
if len(seps) + 1 < len(items): # Use seperators cyclically
seps = seps * (len(items) / len(seps) + 1)
if len(seps) > len(items):
seps = seps[:len(items) - 1]
return [val for pair in (map(None, items, seps))
for val in pair if val is not None]
class Riffle(Builtin):
"""
>> Riffle[{a, b, c}, x]
= {a, x, b, x, c}
>> Riffle[{a, b, c}, {x, y, z}]
= {a, x, b, y, c, z}
>> Riffle[{a, b, c, d, e, f}, {x, y, z}]
= {a, x, b, y, c, z, d, x, e, y, f}
#> Riffle[{1, 2, 3, 4}, {x, y, z, t}]
= {1, x, 2, y, 3, z, 4, t}
#> Riffle[{1, 2}, {1, 2, 3}]
= {1, 1, 2}
#> Riffle[{1, 2}, {1, 2}]
= {1, 1, 2, 2}
"""
def apply(self, list, sep, evaluation):
'Riffle[list_List, sep_]'
if sep.has_form('List', None):
return Expression('List',
*riffle_lists(list.get_leaves(), sep.leaves))
else:
return Expression('List', *riffle_lists(list.get_leaves(), [sep]))
class DeleteDuplicates(Builtin):
"""
<dl>
<dt>'DeleteDuplicates[$list$]'
<dd>deletes duplicates from $list$.
<dt>'DeleteDuplicates[$list$, $test$]'
<dd>deletes elements from $list$ based on whether the function $test$ yields 'True' on pairs of elements.
</dl>
>> DeleteDuplicates[{1, 7, 8, 4, 3, 4, 1, 9, 9, 2, 1}]
= {1, 7, 8, 4, 3, 9, 2}
>> DeleteDuplicates[{3,2,1,2,3,4}, Less]
= {3, 2, 1}
#> DeleteDuplicates[{3,2,1,2,3,4}, Greater]
= {3, 3, 4}
#> DeleteDuplicates[{}]
= {}
"""
rules = {
'DeleteDuplicates[list_]': 'DeleteDuplicates[list, SameQ]',
}
messages = {
'normal': 'Nonatomic expression expected at position `1` in `2`.',
}
def apply(self, mlist, test, evaluation):
'DeleteDuplicates[mlist_, test_]'
expr = Expression('DeleteDuplicates', mlist, test)
if mlist.is_atom():
evaluation.message('Select', 'normal', 1, expr)
return
result = []
for leaf in mlist.leaves:
matched = False
for res in result:
applytest = Expression(test, res, leaf)
if applytest.evaluate(evaluation).is_true():
matched = True
break
if not matched:
result.append(leaf)
return Expression(mlist.head, *result)
class Complement(Builtin):
"""
<dl>
<dt>'Complement[$all$, $e1$, $e2$, ...]'
<dd>returns an expression containing the elements in the set $all$ that
are not in any of $e1$, $e2$, etc.
<dt>'Complement[$all$, $e1$, $e2$, ..., SameTest->$test$]'
<dd>applies $test$ to the elements in $all$ and each of the $ei$
to determine equality.
</dl>
The sets $all$, $e1$, etc can have any head, which must all match.
The returned expression has the same head as the input
expressions.
>> Complement[{a, b, c}, {a, c}]
= {b}
>> Complement[{a, b, c}, {a, c}, {b}]
= {}
>> Complement[f[z, y, x, w], f[x], f[x, z]]
= f[w, y]
#> Complement[a, b]
: Non-atomic expression expected at position 1 in Complement[a, b].
= Complement[a, b]
#> Complement[f[a], g[b]]
: Heads f and g at positions 1 and 2 are expected to be the same.
= Complement[f[a], g[b]]
#> Complement[{a, b, c}, {a, c}, SameTest->(True&)]
= {}
#> Complement[{a, b, c}, {a, c}, SameTest->(False&)]
= {a, b, c}
"""
messages = {
'normal': "Non-atomic expression expected at position `1` in `2`.",
'heads': ("Heads `1` and `2` at positions `3` and `4` are expected "
"to be the same."),
'smtst': ("Application of the SameTest yielded `1`, which evaluates "
"to `2`. The SameTest must evaluate to True or False at "
"every pair of elements."),
}
options = {
'SameTest': 'SameQ',
}
def complement(self, all, others, evaluation, test):
def test_pair(e1, e2):
test_expr = Expression(test, e1, e2)
result = test_expr.evaluate(evaluation)
if not(result.is_symbol() and (result.has_symbol('True') or
result.has_symbol('False'))):
evaluation.message('Complement', 'smtst', test_expr, result)
return result.is_true()
all = set(all)
for leaves in others:
for e2 in leaves:
for e1 in all.copy():
if test_pair(e1, e2):
all.discard(e1)
return all
def apply(self, all, others, evaluation, options={}):
'Complement[all_, others__, OptionsPattern[Complement]]'
# FIXME: is there a better way to get hold of the original
# expression?
def get_call():
return Expression('Complement', all, *others.get_sequence())
for pos, e in enumerate([all, others]):
if e.is_atom():
return evaluation.message(
'Complement', 'normal', pos + 1, get_call())
for pos, e in enumerate([all] + others.get_sequence()):
if e.is_atom():
return evaluation.message(
'Complement', 'normal', pos + 1, get_call())
if e.head != all.head:
return evaluation.message(
'Complement', 'heads', all.head, e.head,
1, pos + 1)
result_head = all.head
same_test = self.get_option(options, 'SameTest', evaluation)
others_leaves = [e.leaves for e in others.get_sequence()]
result = Expression(result_head,
*self.complement(all.leaves, others_leaves,
evaluation, same_test))
result.sort()
return result
