-
Notifications
You must be signed in to change notification settings - Fork 26
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
std/lists: support destructive add/prepend for SinglyLinkedList
, DoublyLinkedList
+ other lists
improvements
#303
Comments
While I can imagine your solution to work, I think it's too complex and I am not aware of other list implementations that use your solution. See also: https://doc.rust-lang.org/std/collections/struct.LinkedList.html#method.append
|
that's almost the same approach, in fact that was my original idea but then i figured keeping Either way, either using an "owned" flag or destroying b would be a net improvement over nim-lang/Nim#16362 (thanks for the link btw) |
This won't solve the problem of In my opinion, if someone uses list concatenation reasonably, these cases do not occur. If you create a cycle, you get an infinite loop, I think of that as a "fact of life" :) Adding a dirty bit, like the one proposed here, will result in many extra computations, and won't save the user if he does something like Also, e.g. Common Lisp has a special variable that determines whether cycles are detected or not when printing. We could at least give a predicate to decide if a given list is circular. |
I like the Rust solution, because it's so simple, although takes a bit of freedom away (sometimes it is good to have shared structures). |
after If destroying note: special case of
|
I am not convinced about the As for handling If someone would like to uses func first*[T](L: SinglyLinkedList[T]): T = L.head.value
func rest*[T](L: SinglyLinkedList[T]): SinglyLinkedList[T] =
result = initSinglyLinkedList[T]()
result.head = L.head.next
result.tail = L.head.next But then |
We should follow Rust and move the elements. |
indeed. We also need a var a = [0,1].toSinglyLinkedList
var b = [2,3].toSinglyLinkedList
# a.add b # ok but destructive for b
a.add b.copy # not destructive for b
assert a.toSeq == [0,1,2,3]
assert b.toSeq == [2,3]
a.add a.copy note: example: type Foo = ref object
x: int
var f = Foo(x: 1)
var a = [f, f].toSinglyLinkedList
var b = [f, f].toSinglyLinkedList
a.add b.copy
assert b.head.value == f |
Implemented the move semantics, and added a shallow var
a = [0, 1].toSinglyLinkedList
b = [2, 3].toSinglyLinkedList
c = b.copy
a.add(c) Is there a workaround for this? |
how about: proc addMove[T: SinglyLinkedList | DoublyLinkedList](a: var T, b: var T) = ...
proc add[T: SinglyLinkedList | DoublyLinkedList](a: var T, b: T) =
var b2 = b.copy
addMove(a, b2) ditto with it might actually be better, because in rest of stdlib, add is not destructive. bikeshedding: addMove or addFrom |
Use a |
That's nice! Haven't heard of these before. So if the second list is a sink parameter, then even though I like this, but I don't really like the idea that this operation is O(1) or O(n) based on what the compiler thinks, unknown to the user. |
You can make the |
That sounds like a good solution, but when I actually tried it out at this simple example: import lists
var a = [1, 2, 3].toSinglyLinkedList
let b = [4, 5].toSinglyLinkedList
a.add b.copy
assert $a == "[1, 2, 3, 4, 5]"
assert $b == "[4, 5]"
a.add b
assert $a == "[1, 2, 3, 4, 5, 4, 5]" # b is inaccessable ... I got an error for the |
but that would prevent valid use cases, and be a breaking change (not necessarily in the right direction). import std/lists
type Foo = object
list: DoublyLinkedList[int]
proc main()=
block:
var a = initDoublyLinkedList[int]()
let b = a # was legal
block:
let a = Foo(list: initDoublyLinkedList[int]())
let b = a.list # was legal
main() (and I do prefer the terminology
me neither, it's error prone |
Because |
That's true. But |
I have put it in as |
addMoved is a bit shorter; any name that works well with both add and prepend is fine.
|
Do we need b.addMove a
swap a, b (or a = b.copy.addMove a |
with import lists, sugar
# it works, I tried it after s/append/add/ in your PR
let b = collect(initSinglyLinkedList): for i in 0..<3: i the classical "works better in generic code" is a real argument ... and it doesn't mean that "everything compiles", just the stuff that makes sense ;-). my suggestion is:
template append*[T: DoublyLinkedList or SinglyLinkedList](a: T, b: T) {.deprecated: "use add".} = add(a,b)
template append*[T](a: DoublyLinkedList[T] or SinglyLinkedList[T], b: T) {.deprecated: "use add".} = add(a,b) (I also tried, seems to work; whereas
|
I was not really reasoning for |
arguments for
b.addMove a
swap a, b in any case this can be settled after your PR since it's orthogonal |
It is a real argument in this case because you gave a real example with |
@salvipeter after nim-lang/Nim#16362 (which I just LGTM'd) is merged, do you have interest in writing another PR for the following:
|
SinglyLinkedList
, DoublyLinkedList
SinglyLinkedList
, DoublyLinkedList
+ other lists
improvement
SinglyLinkedList
, DoublyLinkedList
+ other lists
improvementSinglyLinkedList
, DoublyLinkedList
+ other lists
improvements
I've created a new PR. |
when true:
import lists
import std/enumerate
var a = [10,11,12,13].toDoublyLinkedList
echo a
a.remove(nil)
echo a instead, we should use |
when true:
import lists
block:
var a = [10,11,12,13].toDoublyLinkedList
var b = [20,21,22,23].toDoublyLinkedList
a.remove(b.head)
echo a # [10, 11, 12, 13]
echo b # [20, 21, 22, 23]
block:
var a = [10,11,12,13].toDoublyLinkedList
var b = [20,21,22,23].toDoublyLinkedList
a.remove(b.head.next)
echo a # [10, 11, 12, 13]
echo b # [20, 22, 23] |
when true:
import lists
var a = [10,11,12].toSinglyLinkedList
a.add a.head.next
echo take(a, 6)
this would be consistent with behavior for (take is defined here: timotheecour/Nim#504) |
when true:
import lists
var a = [10,11,12].toDoublyLinkedList
a.add a.head.next
echo take(a, 6)
unlike with If user wants to add a n with (take is defined here: timotheecour/Nim#504) |
SinglyLinkedList
, DoublyLinkedList
+ other lists
improvementsSinglyLinkedList
, DoublyLinkedList
+ other lists
improvements
|
current implementation in nim-lang/Nim#16362 is problematic because:
But actually it turns out there's a similar problem with
SinglyLinkedList
:b
is left in inconsistent state after being added twice, and other problems below:proposal
This proposal involves adding a flag to indicate that a list is cycle-free assuming user sticks add, prepend + other APIS in lists.nim; overhead is negligible.
The proposal is to support destructive
add
andprepend
for bothSinglyLinkedList
andDoublyLinkedList
as follows:owned: bool
inSinglyLinkedList
add
as follows:implement
prepend
in analogous waynote that prepend is still needed even if we have add because prepend(a,b) will set b.owned but add(a,b) will set b.owned), so you can't simply implement prepend(a,b) in terms of
add
as that would "own" aimplement
$
anditems
as follows:then this will make
$
, andtoSeq
correct instead of infinite loop on cyclesNote: the
owned
flag is added toSinglyLinkedList
, notSinglyLinkedNodeObj
, so it doesn't asymptotically increase memory for normal use (few lists, lots of nodes)DoublyLinkedList
The text was updated successfully, but these errors were encountered: