™
Mou Code
Divacon Trace Output
monosort-- source --
randarr = shuffled(4)
nest = PDC(d_lr,c_lr, !(min,max) @ #!corr, id, atom, id)
monosort = PDC(d_lr,c_lr, id, !nest @ !(min,max) @ #!mirr, atom, id)
trace(monosort, randarr)
-- end source --
-- lib: monosort_lib.py --
"""Helpers for monosort.dc.
Loaded via: ./pydc dcsrc/monosort.dc dcsrc/monosort_lib.py
`randints(N)` returns 2^N random integers in [0, 99] — small enough that
the trace stays readable, big enough that collisions are rare for small N.
`shuffled(N)` returns a uniform permutation of [0..2^N - 1] — useful for
verifying the sort end-to-end (output should be [0, 1, ..., 2^N - 1])."""
import random
def randints(N, lo=0, hi=99, seed=None):
"""List of 2**N random integers in [lo, hi]."""
if seed is not None:
random.seed(seed)
return [random.randint(lo, hi) for _ in range(2 ** N)]
def shuffled(N, seed=None):
"""A random permutation of [0..2**N - 1]."""
if seed is not None:
random.seed(seed)
arr = list(range(2 ** N))
random.shuffle(arr)
return arr
-- end lib --
-- trace: monosort([8,1,4,3,15,11,12,10,6,9,7,2,14,13,0,5]) --
monosort([8,1,4,3,15,11,12,10,6,9,7,2,14,13,0,5])
divide d_lr -> ([8,1,4,3,15,11,12,10], [6,9,7,2,14,13,0,5])
monosort([8,1,4,3,15,11,12,10])
divide d_lr -> ([8,1,4,3], [15,11,12,10])
monosort([8,1,4,3])
divide d_lr -> ([8,1], [4,3])
monosort([8,1])
divide d_lr -> ([8], [1])
monosort([8])
⇣ atom; basef -> [8]
monosort([1])
⇣ atom; basef -> [1]
post #!mirr -> ([(8, 1)], [(1, 8)])
post !(min, max) -> ([1], [8])
post !nest -> ([1], [8])
combine c_lr -> [1,8]
monosort([4,3])
divide d_lr -> ([4], [3])
monosort([4])
⇣ atom; basef -> [4]
monosort([3])
⇣ atom; basef -> [3]
post #!mirr -> ([(4, 3)], [(3, 4)])
post !(min, max) -> ([3], [4])
post !nest -> ([3], [4])
combine c_lr -> [3,4]
post #!mirr -> ([(1, 4),(8, 3)], [(3, 8),(4, 1)])
post !(min, max) -> ([1,3], [8,4])
post !nest -> ([1,3], [4,8])
combine c_lr -> [1,3,4,8]
monosort([15,11,12,10])
divide d_lr -> ([15,11], [12,10])
monosort([15,11])
divide d_lr -> ([15], [11])
monosort([15])
⇣ atom; basef -> [15]
monosort([11])
⇣ atom; basef -> [11]
post #!mirr -> ([(15, 11)], [(11, 15)])
post !(min, max) -> ([11], [15])
post !nest -> ([11], [15])
combine c_lr -> [11,15]
monosort([12,10])
divide d_lr -> ([12], [10])
monosort([12])
⇣ atom; basef -> [12]
monosort([10])
⇣ atom; basef -> [10]
post #!mirr -> ([(12, 10)], [(10, 12)])
post !(min, max) -> ([10], [12])
post !nest -> ([10], [12])
combine c_lr -> [10,12]
post #!mirr -> ([(11, 12),(15, 10)], [(10, 15),(12, 11)])
post !(min, max) -> ([11,10], [15,12])
post !nest -> ([10,11], [12,15])
combine c_lr -> [10,11,12,15]
post #!mirr -> ([(1, 15),(3, 12),(4, 11),(8, 10)], [(10, 8),(11, 4),(12, 3),(15, 1)])
post !(min, max) -> ([1,3,4,8], [10,11,12,15])
post !nest -> ([1,3,4,8], [10,11,12,15])
combine c_lr -> [1,3,4,8,10,11,12,15]
monosort([6,9,7,2,14,13,0,5])
divide d_lr -> ([6,9,7,2], [14,13,0,5])
monosort([6,9,7,2])
divide d_lr -> ([6,9], [7,2])
monosort([6,9])
divide d_lr -> ([6], [9])
monosort([6])
⇣ atom; basef -> [6]
monosort([9])
⇣ atom; basef -> [9]
post #!mirr -> ([(6, 9)], [(9, 6)])
post !(min, max) -> ([6], [9])
post !nest -> ([6], [9])
combine c_lr -> [6,9]
monosort([7,2])
divide d_lr -> ([7], [2])
monosort([7])
⇣ atom; basef -> [7]
monosort([2])
⇣ atom; basef -> [2]
post #!mirr -> ([(7, 2)], [(2, 7)])
post !(min, max) -> ([2], [7])
post !nest -> ([2], [7])
combine c_lr -> [2,7]
post #!mirr -> ([(6, 7),(9, 2)], [(2, 9),(7, 6)])
post !(min, max) -> ([6,2], [9,7])
post !nest -> ([2,6], [7,9])
combine c_lr -> [2,6,7,9]
monosort([14,13,0,5])
divide d_lr -> ([14,13], [0,5])
monosort([14,13])
divide d_lr -> ([14], [13])
monosort([14])
⇣ atom; basef -> [14]
monosort([13])
⇣ atom; basef -> [13]
post #!mirr -> ([(14, 13)], [(13, 14)])
post !(min, max) -> ([13], [14])
post !nest -> ([13], [14])
combine c_lr -> [13,14]
monosort([0,5])
divide d_lr -> ([0], [5])
monosort([0])
⇣ atom; basef -> [0]
monosort([5])
⇣ atom; basef -> [5]
post #!mirr -> ([(0, 5)], [(5, 0)])
post !(min, max) -> ([0], [5])
post !nest -> ([0], [5])
combine c_lr -> [0,5]
post #!mirr -> ([(13, 5),(14, 0)], [(0, 14),(5, 13)])
post !(min, max) -> ([5,0], [14,13])
post !nest -> ([0,5], [13,14])
combine c_lr -> [0,5,13,14]
post #!mirr -> ([(2, 14),(6, 13),(7, 5),(9, 0)], [(0, 9),(5, 7),(13, 6),(14, 2)])
post !(min, max) -> ([2,6,5,0], [9,7,13,14])
post !nest -> ([0,2,5,6], [7,9,13,14])
combine c_lr -> [0,2,5,6,7,9,13,14]
post #!mirr -> ([(1, 14),(3, 13),(4, 9),(8, 7),(10, 6),(11, 5),(12, 2),(15, 0)], [(0, 15),(2, 12),(5, 11),(6, 10),(7, 8),(9, 4),(13, 3),(14, 1)])
post !(min, max) -> ([1,3,4,7,6,5,2,0], [15,12,11,10,8,9,13,14])
post !nest -> ([0,1,2,3,4,5,6,7], [8,9,10,11,12,13,14,15])
combine c_lr -> [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
-- result: [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
--
|