sassa_nf | Returning an Iterator

You're viewing

sassa_nf's journal
Create a Dreamwidth Account Learn More

Reload page in style: site light

ok, here's what was wrong with the previous attempt: https://stackoverflow.com/a/59576677/1935631

Declaring something as a mutable reference seems to imply that the receiver of it is the sole owner, but it doesn't work for struct fields and return values.

The expression problem - use Box. Box can be declared to contain some implementation of a trait, then at construction time you tell what that implementation is. Also, you can even add the lifetime to the signature.

Then also a closure with a reference to an immutable field - well, it used to capture a mutable reference self, not self.mx. But if you create a local variable first, then you can move that.

Flat | Top-Level Comments Only

From:

juan_gandhi

So, maybe it's a hit that we have to view it as a sign to start treating iterators differently.

From:

sassa_nf

Maybe you see something I don't see. :-)

For me it has been a test of my understanding of lifetimes (where do the lifetimes of return values come from; a solid pass - I did not need to change lifetime propagation logic), reference ownership (fail - I completely misunderstood value ownership vs memory management distinction) and subtyping (maybe pass, and a doze of disappointment to go with it - I knew what I wanted, but took a while to work out how to express that; and one expression problem is not solved (the Peekable<Range...>)). That euler problem was as good as any. I didn't notice anything special about the returned value being an Iterator.

Edited Date: 2020-01-03 06:10 pm (UTC)

From:

juan_gandhi

Well, I'm totally confused how to combine these dimensions in a reasonable discourse.

From:

sassa_nf

Apologies. Let me try again.

I took project euler as a playground to try and use Rust-specific features, not just an opportunity to write more C/Java/Scala-like solutions. So here was an opportunity to see how a stateful object (Iterator) can return another stateful object (another Iterator). It was obvious from the start that the second iterator needs to have a lifetime that does not exceed the lifetime of the "matrix" it gets the values from, such an excellent opportunity to test the understanding of this particular aspect.

I am pleased my understanding of lifetimes was correct. I discovered that my understanding of ownership was flawed (but I learned something new). And I am somewhat disappointed about some other expression problem that probably cannot be solved.

So I did not look too deeply into what is so special about Iterators in this exercise. But Iterators in general - yes, they are very special. If you did some amount of JS or Python, you'll be familiar with Generators. That is the other face of the Iterators.

def ab():
   y = yield(x)
   t = yield(z)

it = ab()
x = it.next()
z = it.next(y)

I deliberately placed the argument of yield in brackets, so it looks like a function call. Now there is a correspondence between each yield and each next. In fact, returning a value from an iterator's next() not only provides a value, but also associates iterator's next with a continuation, and each yield() not only provides a value, but also associates the next yield with the caller's continuation. So yield and next are very similar, the difference is only who starts the invocation chain (and who can capture the continuation on the stack). Also, if we were to capture the types of the functions (ok, no such thing in Python), you can see that this establishes a correspondence between some values A->B and B->A.

In many languages there are no Generators. So they are bound to express things as Iterators. Some things that are straightforward with Generators, are really clunky, when implemented as Iterators.

Here's the famous "generate all strings that match [ab]*":

def ab():
   yield("")
   for s in ab():
      yield("a" + s)
      yield("b" + s)

it = ab()
print(it.next())
print(it.next())
print(it.next())

Now, an Iterator for that.... Well, in this particular case we can get away using binary counting, but if it is not binary, but, say, an arbitrary alphabet, you end up implementing state transitions that actually are nicely captured by the recursion and the scope of each call.

So, yeah, Iterators are special. But without Generators some important insights are missing.

From:

sassa_nf

Actually, in Python it.next doesn't take arguments. I should have used y = it.send(x). Iterator's next() then is just a special case of sending a Unit, so send: A -> B, and next: () -> B, as it were.

From:

juan_gandhi

I'm a little bit confused with this python code, but it's not the point.

My point is, I'm afraid Rust has "progressed" from a pure linear-logic language to something slightly c-ish, to satisfy the consumer. I have a feeling that I do not want to use `Box`, `dyn` and the like; not even sure about lifetimes.

I'd like to find a solution that satisfies the very basic ideas of the language. And I think, for instance, that the idea of exposing an iterator, or a generator, is not how the language was designed. Creating something inside some function and then returning it, it does not seem like a good idea in Rust. If we can live without a comonad... can we? I don't know.

From:

sassa_nf

I see what you mean. You have a good point about the intention of the language.

But I'd like to point out that the dyn and Box in my example is the result of trying to find an expression for function covariance. Nothing to do with mutability.

How do you declare a function A->B, but return a value of a subtype of B?.. Unfortunately, the only subtyping is through traits, right?.. Forget that in this case it is an Iterator, the main problem is function covariance.