Closed uncomputable closed 1 month ago
Will wait for rebase after merge of #69, since this needs a rebase anyway to deal with merge conflicts.
Rebased
Can you address my outstanding comment from #69?
I don't see any outstanding comments in #69. Do you mean a different PR?
Oh, I was confused. I meant https://github.com/BlockstreamResearch/rust-simplicity/pull/237 which is in a different repo and of course has nothing to do with this PR.
c416f287abd7b2f6aaf175324bf79ca25ffcc051 looks good to me! I guess this is the first place where we meaningfully deviate from Rust syntax. It is a bit tempting to use fold(f, init, list)
syntax to match Rust ... though you would need to special-case this in the syntax so that it would look like a normal function call but actually be a language construct. Probably not worth the trickery and weird error messages.
I did not carefully analyze your Simplicity code but it looks like it's right.
Basically, we need to add function types to Simfony. Function types are a huge topic in Rust, so I will not open this can of worms here. We will come back to this issue and revise the syntax.
Depends on #69. Better version of #22.
Fold a bounded list using a binary function
fn f(element: E, accumulator: A) → A
.Lists are divided into blocks of decreasing size
[1234][56][7]
.f
is generalized to work on blocks, passing the updated accumulator to the next element. The fold processes blocks in order[1234]
,[56]
,[7]
. This seems like a left fold to me, which is usually inefficient, but in Simplicity there is no concept of recursion, so this inefficiency might no longer hold.