In terms of a stack, foldl is a confusing one since you can’t pop from the
start of the stack – it could be interesting to introduce a secondary stack,
which you could reverse the original stack into (allowing you to foldr that
stack), however outside of this use-case I’m not sure if the second stack is
that useful.
I’ve also been wondering about comparison operations. The immediately obvious
functionality this would be useful for is a max function. I’m also wondering
at what point this stops becoming a calculator however… A potentional
implementation of these could look like this
3 1 2 ; stack = 3, 1, 2
gt ; stack = 3, 2
lt ; stack = 2
The naming here is rather confusing, since gt and lt are supposed to mean
greatest and least rather than the conventional greater than and
less than that a language with booleans would use, I’m not really sure how to
clearly express what those operators are doing.
A less destructive implementation would be to order the top two elements in the stack, e.g
3 1 2 ; stack = 3, 1, 2
gt ; stack = 3, 1, 2
lt ; stack = 3, 2, 1
null ; stack = 3, 2
gt ; stack = 2, 3
Here, even just writing the example I found that it’s hard to make this approach
useful with some kind of a null command, which simply removes the top of the
stack – here we need an extra command to achieve what the first implementation
does in one, however it would allow you to bubble sort to some extent…
0 3 1 2
:= lt ; stack = (0), 3, 1, 2 => 0, (3), 1, 2 => 0, 1, (3), 2 => 0, 1, 2, (3)
<< null ; empty stack
3 5 2
:= lt ; stack = (3), 5, 2 => 3, (5), 2 => 3, 2, (5)
Writing this example highlighted how odd this map functionality is… it just
doesn’t feel very stack-ish… I suppose in this regard a second stack would
allow you to map in a more stack-like way – apply whatever function, push to
the second stack (repeat) and pop from the second into the first. I also wonder
if fold is misleading – the way I’m currently thinking of these is more like
apply this function until the stack contains one element.
Perhaps a variable could actually represent a stack, and prefixing a digit
with a variable/stack would mean push to that stack
0 1 1 2 ; primary stack = 0, 1, 1, 2
a 3 5 8 ; primary stack = 0, 1, 1, 2 | stack a = 3, 5, 8
a + ; primary stack = 0, 1, 1, 2, 8, + | stack a = 3, 5
This example nicely illustrates a major issue with this idea – does a + mean
perform + on the top two elements of stack a or
pop & push the top of a onto the primary stack and perform + on primary. Still
rather interesting and worthwhile revisiting.
Something else I’ve snuck into the above example is the idea of lazy evaluation, which sounds quite appealing to me!
I plan to stew on these questions a while and write a follow-up soon (whether I ever write the actual software I’m describing is a completely different question and far less certain!).