[swift-users] Comparing POP to OOP

Dave Abrahams dabrahams at apple.com
Thu Mar 10 18:05:11 CST 2016

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)


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?


More information about the swift-users mailing list