By the end of this, we will have defined insert, delete, find and replace operations.
Talking about polymorphism with someone in the context of JS, the following example came up:
function a(p1: integer): integer { ... } function a(p1: string): string { ... }
They argued that these should be two functions with different names. In a JS context I agree, that polymorphism isn’t great, and only works well in strictly typed contexts.
They still disagreed though. I brought up how +
is heavily overloaded,
but always has a generic meaning, thanks to abstract algebra.
This made me think about what kind of structure strings formed.
At first it seemed to be a magma - this is correct, but we can be even more precise. They also form a monoid, semigroup, free-group and group.
Group is the second most restrictive structure (abelian group being the most restrictive). To form a group, the following laws have to be followed:
-
Closure:
for all a, b in G; a * b is in G too.
-
Associative:
(a * b) * c = a * (b * c)
-
Identity:
a * i = i * a = a
-
Inverse:
a^-1 * b = b * a^-1 = i
At first I thought strings did not form a group, but they definitely can.
Let’s give an extensional example of all these laws:
-
Closure:
"hello" * "world" == "helloworld"
- which is still in the group of strings. -
Associative:
("hello" * "world") * "today" == "hello" * ("world" * "today")
-
Identity:
"hello" * "" == "" * "hello"
-
Inverse:
"hello"^-1 * "hello" == "hello" * "hello"^-1 == ""
^-1
means the "inverse" of the string, or a "negative string".
I propose just appending -
infront of strings to denote this.
It’s not proof, or anywhere close to rigorous, but it’s just neat to look at and think about.
Strings alone don’t seem to give enough information to do many useful things.
("hello " * name * ", how are you today?") * -"how") simply removes "how".
How would we replace the word "how"? Or maybe strings should be promoted to an even stricter algebraic structure?
These form a loop.
Here’s one way we can specify context or position, with a vector:
["hello ", name, " how are you?"] * ["", " with a hat", ""] == "hello lf94 with a hat how are you?"
An issue with this is, you must specify exactly what you want to replace…
["hello ", name, " how are you?"] * ["", -"lf94" * "bob", ""] == "hello bob how are you?"
So we need to figure out how to delete things entirely:
"a" * "" = "" "a" * -"" = ??? "" * "" = "" "" * -"" = -"" -"" * -"" = ""
So: "a" * -"" = -"a"
, which means * -""
will delete everything.
Now we can do a complete replace:
["hello ", name , " how are you?"] * ["" , -"" , "" ] * ["" , "bob", "" ] == "hello bob how are you?"
We can apply -
to entire vectors also:
["hello ", name , " how are you", "?"] * -["" , -"" , "" , -"" ] * ["" , " my boy", "" , "!" ] == "bob my boy?!"
To create these z-string vectors, we’ll need a split operator, %
.
Now we can start cooking with gas:
("hello big world" % " ") * ["", -"", ""] * ["", "small", ""] == "hello small world"
In JS the simplest solution involves a reference:
let a = "hello big world".split(' '); a[1] = "small";
!
re-joins everything.
!["hello ", "world"] == "hello world"
We can combine everything to get a real find and replace.
find
will be defined as ?
which returns a zipper structure, which is
essentially [string_before, the_found_string, string_after]
.
Now our find and replace can never fail and doesn’t require any references:
!(("hello my big world" ? "big") * ["", -"", ""] * ["", "small", ""]) == "hello my small world"
Let’s now explore using our new primitives.
Using these with other programming language functions we can get some interesting uses.
!(["", "(", ""] * ("if 1 === 1 { do_thing(); }" ? "1 === 1") * ["", ")", ""]) == "if (1 === 1) { do_thing(); }"
!([-"", "", ""] * ("if 1 === 1 { do_thing(); }" ? "1 === 1")) == "1 === 1 { do_thing(); }"
!(["", "", -""] * ("if 1 === 1 { do_thing(); }" ? "1 === 1")) == "if 1 === 1"
!(["", -"", ""] * ("if 1 === 1 { do_thing(); }" ? "1 === 1") * ["", "1 === 0", ""]) == "if 1 === 0 { do_thing(); }"