mirror of
https://github.com/HigherOrderCO/Bend.git
synced 2024-10-05 15:57:08 +03:00
123 lines
3.0 KiB
Plaintext
123 lines
3.0 KiB
Plaintext
type MyMap:
|
|
Free
|
|
Used
|
|
Both { ~a: MyMap, ~b: MyMap }
|
|
|
|
type Arr(t):
|
|
Null
|
|
Leaf { a: t }
|
|
Node { ~a: Arr(t), ~b: Arr(t) }
|
|
|
|
def swap(s: u24, a: MyMap, b: MyMap) -> MyMap:
|
|
switch s:
|
|
case 0:
|
|
return MyMap/Both{ a: a, b: b }
|
|
case _:
|
|
return MyMap/Both{ a: b, b: a }
|
|
|
|
|
|
def sort(t: Arr(u24)) -> Arr(u24):
|
|
return to_arr(0, to_map(t))
|
|
|
|
def to_map(t: Arr(u24)) -> MyMap:
|
|
match t:
|
|
case Arr/Null:
|
|
return MyMap/Free
|
|
case Arr/Leaf:
|
|
return radix(t.a)
|
|
case Arr/Node:
|
|
return merge(to_map(t.a), to_map(t.b))
|
|
|
|
def to_arr(x: u24, m: MyMap) -> Arr(u24):
|
|
match m:
|
|
case MyMap/Free:
|
|
return Arr/Null
|
|
case MyMap/Used:
|
|
return Arr/Leaf{ a: x }
|
|
case MyMap/Both:
|
|
return Arr/Node{ a: to_arr(x * 2, m.a), b: to_arr(x * 2 + 1, m.b) }
|
|
|
|
def merge(a: MyMap, b: MyMap) -> MyMap:
|
|
match a:
|
|
case MyMap/Free:
|
|
return b
|
|
case MyMap/Used:
|
|
return MyMap/Used
|
|
case MyMap/Both:
|
|
match b:
|
|
case MyMap/Free:
|
|
return a
|
|
case MyMap/Used:
|
|
return MyMap/Used
|
|
case MyMap/Both:
|
|
return MyMap/Both{ a: merge(a.a, b.a), b: merge(a.b, b.b) }
|
|
|
|
def radix(n: u24) -> MyMap:
|
|
r = MyMap/Used
|
|
r = swap(n & 1, r, MyMap/Free)
|
|
r = swap(n & 2, r, MyMap/Free)
|
|
r = swap(n & 4, r, MyMap/Free)
|
|
r = swap(n & 8, r, MyMap/Free)
|
|
r = swap(n & 16, r, MyMap/Free)
|
|
r = swap(n & 32, r, MyMap/Free)
|
|
r = swap(n & 64, r, MyMap/Free)
|
|
r = swap(n & 128, r, MyMap/Free)
|
|
r = swap(n & 256, r, MyMap/Free)
|
|
r = swap(n & 512, r, MyMap/Free)
|
|
return radix2(n, r)
|
|
|
|
# At the moment, we need to manually break very large functions into smaller ones
|
|
# if we want to run this program on the GPU.
|
|
# In a future version of Bend, we will be able to do this automatically.
|
|
def radix2(n: u24, r: MyMap) -> MyMap:
|
|
r = swap(n & 1024, r, MyMap/Free)
|
|
r = swap(n & 2048, r, MyMap/Free)
|
|
r = swap(n & 4096, r, MyMap/Free)
|
|
r = swap(n & 8192, r, MyMap/Free)
|
|
r = swap(n & 16384, r, MyMap/Free)
|
|
r = swap(n & 32768, r, MyMap/Free)
|
|
r = swap(n & 65536, r, MyMap/Free)
|
|
r = swap(n & 131072, r, MyMap/Free)
|
|
r = swap(n & 262144, r, MyMap/Free)
|
|
r = swap(n & 524288, r, MyMap/Free)
|
|
return radix3(n, r)
|
|
|
|
def radix3(n: u24, r: MyMap) -> MyMap:
|
|
r = swap(n & 1048576, r, MyMap/Free)
|
|
r = swap(n & 2097152, r, MyMap/Free)
|
|
r = swap(n & 4194304, r, MyMap/Free)
|
|
r = swap(n & 8388608, r, MyMap/Free)
|
|
return r
|
|
|
|
def reverse(t: Arr(u24)) -> Arr(u24):
|
|
match t:
|
|
case Arr/Null:
|
|
return Arr/Null
|
|
case Arr/Leaf:
|
|
return t
|
|
case Arr/Node:
|
|
return Arr/Node{ a: reverse(t.b), b: reverse(t.a) }
|
|
|
|
def sum(t: Arr(u24)) -> u24:
|
|
match t:
|
|
case Arr/Null:
|
|
return 0
|
|
case Arr/Leaf:
|
|
return t.a
|
|
case Arr/Node:
|
|
return sum(t.a) + sum(t.b)
|
|
|
|
def gen(n: u24) -> Arr(u24):
|
|
return gen_go(n, 0)
|
|
|
|
def gen_go(n: u24, x: u24) -> Arr(u24):
|
|
switch n:
|
|
case 0:
|
|
return Arr/Leaf{ a: x }
|
|
case _:
|
|
a = x * 2
|
|
b = x * 2 + 1
|
|
return Arr/Node{ a: gen_go(n-1, a), b: gen_go(n-1, b) }
|
|
|
|
Main: u24 = (sum (sort(reverse(gen 4))))
|