[swift-users] Comparing POP to OOP

Jon Hoffman hoffman.jon at gmail.com
Tue Mar 8 18:32:29 CST 2016

> 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

>> 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.  

> -- 
> -Dave

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-users/attachments/20160308/b5f2bb52/attachment.html>

More information about the swift-users mailing list