empty_rlist = None def make_rlist(first, rest = empty_rlist): """A recursive list, r, such that first(r) is FIRST and rest(r) is REST, which must be an rlist.""" return [first, rest] def first(r): """The first item in R.""" return r[0] def rest(r): """The tail of R.""" return r[1] def isempty(r): """True iff R is the empty sequence""" return r is None def set_first(r, v): r[0] = v def set_rest(r, v): r[1] = v def map_rlist(f, s): """The rlist of values F(x) for each x in rlist S (in the same order.)""" if (isempty(s)): return s result = last = make_rlist(f(first(s))) s = rest(s) while not isempty(s): set_rest(last, make_rlist(f(first(s)))) last, s = rest(last), rest(s) return result def cons(left, right): def data(which, value=None): if which == 0: return left elif which == 1: return right elif which == 2: left = value else: right = value return data def left(pair): return pair(0) def right(pair): return pair(1) def set_left(pair, v): return pair(2, v) def set_right(pair, v): return pair(3, v) import time def make_dice(sides = 6, seed = None): """A new 'sides'-sided die that yields numbers between 1 and 'sides' when called. 'seed' controls the sequence of values. If it is defaulted, the system chooses a non-deterministic value.""" if seed == None: seed = int(time.time() * 100000) a, c, m = 25214903917, 11, 2**48 # From Java def die(): nonlocal seed seed = (a*seed + c) % m return seed % sides + 1 return die def frequencies(L): """A dictionary giving, for each w in L, the number of times w appears in L. >>> frequencies(['the', 'name', 'of', 'the', 'name', 'of', 'the', ... 'song']) {'of': 2, 'the': 3, 'name': 2, 'song': 1} """ return { L[i-1]: L[i] for i in range(1, len(L)) } # Or, the long way: def frequencies2(L): """A dictionary giving, for each w in L, the number of times w appears in L. >>> frequencies(['the', 'name', 'of', 'the', 'name', 'of', 'the', ... 'song']) {'of': 2, 'the': 3, 'name': 2, 'song': 1} """ result = {} for i in range(1, len(L)): result[L[i-1]] = L[i] return result def is_duplicate(L): """True iff L contains a duplicated item.""" items = {} for x in L: if x in items: return True items[x] = True # Or any value return False def common_keys(D0, D1): """Return dictionary containing the keys common to D0 and D1.""" result = {} for x in D0: if x in D1: result[x] = True return result # Using sets def is_duplicate(L): """True iff L contains a duplicated item.""" return len(L) != len(set(L)) def common_keys(D0, D1): """Return set containing the keys common to D0 and D1.""" return set(D0) & set(D1)