This isn’t a bad post, but beyond giving a very rudimentary overview of BFS there doesn’t seem to be much in the article demonstrating Go’s standard library. You could do this same exercise in virtually any language that has list and map types in its standard library and the code would look the same.
Serious question: do Go users actually re-use the standard list type everywhere instead of having proper types for stacks and queues?
Serious question: do Go users actually re-use the standard list type everywhere instead of having proper types for stacks and queues?
If the list type handles both and you can just pick which methods to call in your use case, why would that be an issue? Stacks and queues are very similar internally… You can sometimes see a very simple implementation of them just using slice access really.
If the list type handles both and you can just pick which methods to call in your use case, why would that be an issue?
No fundamental issue. I often rely on type signatures to help understand what I’m dealing with, and it is also sometimes helpful to get a compile error (ie. if I try to use as a stack a list that was intended to represent a queue). I guess folks using Go probably rely on comments explicitly indicating whether the list is a stack or queue (and helpfully named variables).
From what I’ve seen (using go since 2012) people don’t usually pass around a slice expecting you to push or pop.
If you are using a slice as a queue you make one of two choices: option 1 is write a wrapper type. Option 2 is reuse some wrapper type built on the empty interface. Soon we’ll get a third option with go2 generics.
I feel like if they had decided that they will implement generics eventually, they would’ve told us. Seems possible that they could explore the design space and decide there is no possible design they are satisfied with.
Yes, you are right, I’m not diving deep into BFS. I actually said in the post there was plenty of pretty awesome material online. I wanted to demonstrate the power of standard library. You must surely admit having a simple BFS implementation on ~15 lines of code is pretty cool :-)
do Go users actually re-use the standard list type everywhere instead of having proper types for stacks and queues
I dont personally do this all the time, but I often tend to start with it, just to get things going and then gradually improve on and sometimes eventually completely replacing some of the standard library data structure implementations.
That’s picking nits, and not really useful ones. The stack, as in the C/hardware stack, is pushed to on subroutine call and indexed into throughout the subroutine. It’s hard to argue that it’s not a stack.
Have you ever tried physically rotating a data structure? Of course it’s nonsense! :)
Anyway, it depends on how restrictively you define a stack. Is it just nil, push and pop? What about rot, tuck and roll? I’d say nil, cons, car and cdr form both a list and a stack minimally and adequately. Both data structures have a head and a tail, and arbitrary indexing is O(n), so it’s just a matter of perspective.
Also you can arbitrarily index into a mutable stack non-destructively if you keep another stack around to form a zip list.
A stack doesn’t really have a tail, if you’re pushing and popping the “tail” it’s a list or dequeue. rot is not an operation that cannot be performed on a stack, it requires some kind of external storage; in Forth, >r swap r> swap, and swap too requires some external storage. Same for tuck. roll is not a real stack operation, it’s treating a stack like a list and indexing arbitrarily. Names for these data structures exist for a reason. A stack is not a vertical list because the point of a stack is you push and pop the top item. If you wanted to randomly index into some data structure that might be appended or truncated, the first data structure to come to mind would not be a stack, because that isn’t the point in a stack.
These new external storage requirements aside (even pop requires some external storage), I’m not arguing what things are for, I’m saying what they are. Absolutely you wouldn’t arbitrarily index into a stack, but if you take an index-able data structure like a list (not that cdddr is any different to pop pop pop) and treat it like a stack, you’ve got yourself a stack. You wouldn’t reimplement a list type just to remove a method so you can rename it to “stack.”
This isn’t a bad post, but beyond giving a very rudimentary overview of BFS there doesn’t seem to be much in the article demonstrating Go’s standard library. You could do this same exercise in virtually any language that has list and map types in its standard library and the code would look the same.
Serious question: do Go users actually re-use the standard list type everywhere instead of having proper types for stacks and queues?
If the list type handles both and you can just pick which methods to call in your use case, why would that be an issue? Stacks and queues are very similar internally… You can sometimes see a very simple implementation of them just using slice access really.
No fundamental issue. I often rely on type signatures to help understand what I’m dealing with, and it is also sometimes helpful to get a compile error (ie. if I try to use as a stack a list that was intended to represent a queue). I guess folks using Go probably rely on comments explicitly indicating whether the list is a stack or queue (and helpfully named variables).
From what I’ve seen (using go since 2012) people don’t usually pass around a slice expecting you to push or pop.
If you are using a slice as a queue you make one of two choices: option 1 is write a wrapper type. Option 2 is reuse some wrapper type built on the empty interface. Soon we’ll get a third option with go2 generics.
Did they decide to add generics in Go 2? That would’ve been pretty big news.
Here’s one proposal from the core go team: https://go.googlesource.com/proposal/+/master/design/go2draft-contracts.md
I don’t know which release it will land in, but go getting generics is a question of when not if.
I feel like if they had decided that they will implement generics eventually, they would’ve told us. Seems possible that they could explore the design space and decide there is no possible design they are satisfied with.
Yes, you are right, I’m not diving deep into BFS. I actually said in the post there was plenty of pretty awesome material online. I wanted to demonstrate the power of standard library. You must surely admit having a simple BFS implementation on ~15 lines of code is pretty cool :-)
I dont personally do this all the time, but I often tend to start with it, just to get things going and then gradually improve on and sometimes eventually completely replacing some of the standard library data structure implementations.
Why not? A stack is just a vertical list.
No, a stack is not a vertical list. A stack is a LIFO. If you’re arbitrarily indexing into a stack, it’s a list.
That’s picking nits, and not really useful ones. The stack, as in the C/hardware stack, is pushed to on subroutine call and indexed into throughout the subroutine. It’s hard to argue that it’s not a stack.
It’s not a nitpick. “A stack is just a vertical list” is nonsense, else we’d just call it a list.
Have you ever tried physically rotating a data structure? Of course it’s nonsense! :)
Anyway, it depends on how restrictively you define a stack. Is it just
nil,pushandpop? What aboutrot,tuckandroll? I’d saynil,cons,carandcdrform both a list and a stack minimally and adequately. Both data structures have a head and a tail, and arbitrary indexing is O(n), so it’s just a matter of perspective.Also you can arbitrarily index into a mutable stack non-destructively if you keep another stack around to form a zip list.
A stack doesn’t really have a tail, if you’re pushing and popping the “tail” it’s a list or dequeue.
rotis not an operation that cannot be performed on a stack, it requires some kind of external storage; in Forth,>r swap r> swap, andswaptoo requires some external storage. Same fortuck.rollis not a real stack operation, it’s treating a stack like a list and indexing arbitrarily. Names for these data structures exist for a reason. A stack is not a vertical list because the point of a stack is you push and pop the top item. If you wanted to randomly index into some data structure that might be appended or truncated, the first data structure to come to mind would not be a stack, because that isn’t the point in a stack.These new external storage requirements aside (even
poprequires some external storage), I’m not arguing what things are for, I’m saying what they are. Absolutely you wouldn’t arbitrarily index into a stack, but if you take an index-able data structure like a list (not thatcdddris any different topop pop pop) and treat it like a stack, you’ve got yourself a stack. You wouldn’t reimplement a list type just to remove a method so you can rename it to “stack.”Sorry for a joke that’s probably getting old, but wouldn’t a lot of the code be easily genericized if go had generics?