Skip to content

Instantly share code, notes, and snippets.

@Zaffer

Zaffer/ski.bend

Created July 24, 2024 23:59
Show Gist options
  • Save Zaffer/00b9cf6fa0b598e3103cf46e7f9b9ac0 to your computer and use it in GitHub Desktop.
Save Zaffer/00b9cf6fa0b598e3103cf46e7f9b9ac0 to your computer and use it in GitHub Desktop.
Download ZIP
binary recursive function in a tree structure
Raw
ski.bend
type C:
App {~x, ~y}
S
K
I
String/concat (String/Nil) str = str
String/concat (String/Cons c rest1) str2 = (String/Cons c (String/concat rest1 str2))
String/join List/Nil = ""
String/join (List/Cons x xs) = (String/concat x (String/join xs))
norm (C/App f x) = (app (norm f) (norm x))
norm term = term
app (C/App (C/App C/S x) y) z = (app (app x z) (app y z))
app (C/App C/K x) y = x
app C/I x = x
app f x = (C/App f x)
show C/S = "s"
show C/K = "k"
show C/I = "i"
show (C/App f x) = (String/join ["(" (show f) " " (show x) ")"])
size C/S = 1
size C/K = 1
size C/I = 1
size (C/App f x) = (+ 1 (+ (size f) (size x)))
def loop(n):
switch n:
case 0:
return 0
case _:
expr = norm(C/App(C/App(C/App(C/App(C/S, C/App(C/App(C/S, C/S), C/S)), C/S), C/App(C/S, C/S)), C/K))
return size(expr) + loop(n-1)
def tree(n):
switch n:
case 0:
return loop(500)
case _:
return tree(n-1) + tree(n-1)
def main:
return tree(6)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment