5 ms·
> That said, reading a list length (in O(n) time) and then performing an operation on it is usually an anti-pattern Of course it's unnatural for Haskell lists,
by creata 6y ago
> That said, reading a list length (in O(n) time) and then performing an operation on it is usually an anti-pattern
Of course it's unnatural for Haskell lists, but replace "list" with "Array" (or even just the height of a tree, which is merely O(log n)) and I feel that this is a very common and acceptable use.
> If you want to touch a list twice, don't mark it as linear.
But why are we counting how many times we "touch" the list? Wouldn't it be nice to have some set of operations which get data out of the list without "touching" it?
Anyway, the other commenter points out that you can return the array as you compute its length, and yes, that is a common trick with linear types (Idris' experimental linear arrays do the same). But isn't it better to express in the type system that you will use something "nondestructively"? As an added bonus, it'd probably be more ergonomic than constantly reassigning the list.
- mrkeen 6y ago> But isn't it better to express in the type system that you will use something "nondestructively"? That is how regular functions & data work now. It's completely ergonomic, no linearity required.
- creata 6y agoSorry: you seem to be misunderstanding me, but I do not know how to express myself better. Edit: for reference, I'm looking for an analog of the let! construct from "Linear types can change the world!" and the borrowing usage from the Linear Haskell paper.
- dllthomas 6y ago> But why are we counting how many times we "touch" the list? Well, right, exactly. Why did you ask for that? Probably there's a reason. If I understand correctly, you are really asking why this needs to apply to all operations, and I think laziness is probably the answer. If I've asked for a linear list because I want to somewhere change it inline, and I ask for the length and "then" do something that changes that length, the value the length function returns would seem to depend on when (at run time) the change is forced vs the question (and they could possibly be overlapping, if you have sent the length to another thread!). That's not what we want. Requiring you to pass back a "new" list forces the ordering - either my modification is of the list before I took the length, or the list after. In terms of sequencing, that's exactly what we want. I do agree that it is a bit disappointing that the types don't tell us that length returns list unchanged.