[swift-users] Comparing POP to OOP

[Jon Hoffman]

> 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()


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