[swift-users] Comparing POP to OOP

[Dave Abrahams]

on Tue Mar 08 2016, Jon Hoffman <swift-users-AT-swift.org> wrote:

>> On Mar 8, 2016, at 1:40 PM, Dave Abrahams <dabrahams at apple.com> wrote:
>> 
>> 
>> on Mon Mar 07 2016, Jon Hoffman <hoffman.jon-AT-gmail.com> wrote:
>> 
>
>>> 
>>> So for the last two hours or so I put myself on a task to create a
>>> mutable linked list using value types and to do it in an elegant way
>>> (Hey I love challenges and beating my head against the wall).  
>> 
>> A linked list that conforms to MutableCollection with the right
>> efficiency characteristics for linked lists *and* value semantics is a
>> tough problem.
>> 
>> I think under the proposed new indexing model you can just build it on
>> top of an Array, though ;-)
>
> But where is the fun in using an Array?  The greater the challenge, the more rewarding it is to overcome it :)  
>
>> 
>>> While I have found one working solution so far it is pretty ugly
>>> therefore I have to ask myself, that even though it is preferred that
>>> we use value types overall, should it be preferred that we use
>>> reference types for mutable data structures like this?  
>> 
>> What do you mean by “like this?”  Array is a mutable data structure; is
>> it “like this?”
>> 
>> You're going to use reference types in the *implementation* of any type
>> that has arbitrary growth.  Array uses a reference internally.
>
> Actually we should be able to make a decent stack out of a value type
> without a reference type behind it.  Something like this:
>
> enum Stack<T> {
>     case Empty
>     indirect case Node(T, next: Stack<T>)
>
>     mutating func push(value: T) {
>         self = .Node(value, next:self)
>     }
>
>     mutating func pop() -> T? {
>         switch self {
>         case .Empty: return nil
>         case let .Node(value, next: next):
>             self = next
>             return value
>         }
>     }
> }
>
> Can use it like this:
>
> var stack = Stack<Int>.Empty
> stack.push(1)
> stack.push(2)
> stack.push(3)
> stack.pop()
> stack.pop()

Leaving aside the reference implied by "indirect," this type is not
mutable by parts.

You can build that same thing trivially with an immutable class; you just
lose the method syntax because our class methods aren't allowed to write
back to the original reference, so you end up with

  push(&stack, 1)

etc.

That's just a syntactic distinction The real /semantic/ distinction
between value types and reference types occurs when you are doing
mutation of just a part:

>>> Trust me, I have not giving up finding an elegant solution yet just
>>> wondering your thoughts on that.
>> 
>> My feeling is that linked lists are almost never the best answer in
>> real programs, but if you *really* need their characteristics you
>> might want to implement them with reference semantics.
>> 
>
> True but linked lists, stacks and queues are good data structures to
> play with especially when demonstrating what data structures are and
> how they work.

Sure.  But when you're demonstrating linked data structures, do they
need to be value types?  Do you even want the complication implied by
the CoW that's needed?

-- 
-Dave