> So as long as 'pop' is returning the element from the list/map/set/whatever, and nothing else, it is the wrong verb for immutable structures.
right, but would anyone really write a functional `pop` like that? that's just `last`. any sensible functional `pop` would return a tuple:
(x, new_xs) = pop(xs)
so i'm not sure i understand what the problem is tbh. we might be in violent agreement...
and re: unordered containers, i'd say it "makes as much sense" for immutable and mutable ones. maybe it returns the most recently inserted element or whatever's convenient/efficient to implement; but it's arbitrary regardless of any (im)mutability.
> so i'm not sure i understand what the problem is tbh. we might be in violent agreement...
A two-return pop like that is a little weird, but still basically reasonable.
But a one-return pop is a misleading term for immutable data structures. Use list[-1] or last(list) or something.
When I say I'd be upset at pop not mutating a list, I'm talking about a one-return pop specifically.
> and re: unordered containers, i'd say it "makes as much sense" for immutable and mutable ones. maybe it returns the most recently inserted element or whatever's convenient/efficient to implement; but it's arbitrary regardless of any (im)mutability.
If the structure is immutable and unordered, a one-return pop is almost totally useless.
You use it, it gives you some element. Then what? You can't meaningfully use it again, because it might give you the same element, or it might not. You can't whittle the structure down one element at a time, processing each element as you go.
The only things you can dependably do with it are check if the data structure is empty or not, and get an arbitrary example element.
so we agree about single-return-pop – it just wouldn't be very useful. what i tried to say is that it's a bit of a strawman – single-return-pop is pretty obviously useless, so no one would design a pure API like that. so there's no point arguing against it :)
(with a `Maybe` thrown in to account for popping an empty stack)
---
another alternative that works well in some cases is algebraic datatypes and pattern matching:
result = case myList of
[] -> "whoops, empty"
(x : rest) -> (
"the first element is " ++ (show x) ++
", and the rest of the list is: " ++ (show rest)
which is pretty similar to
try:
x = myList.pop(0)
result = "the first element is " + str(x) + " and the rest is " + str(myList)
except IndexError:
result = "whoops, empty"
so that way you can take your structure apart bit by bit like you would with `pop()`. if your container is unordered, you could convert it to a list first.
---
and if wrangling tuples and passing the "state" around like that gets annoying, Haskell has the `State` monad, essentially a wrapper around functions `SomeState -> (X, SomeState)` that eliminates the state-passing boilerplate
> so we agree about single-return-pop – it just wouldn't be very useful. what i tried to say is that it's a bit of a strawman – single-return-pop is pretty obviously useless, so no one would design a pure API like that. so there's no point arguing against it :)
Remember where the conversation started :) It's not a strawman because it's what confused macintux in the first place!
I was saying that the thing they expected would be a problem, and we're just discussing how to replace it, not disagreeing with that original idea.
i guess it's "making illegal states unrepresentable" – with `(Stack a, Maybe a)` you allow an implementation that does
stackPop [1,2,3,4] == ([1,2,3], Nothing)
which doesn't make sense - `Nothing` is only supposed to happen when the stack is empty, i.e. `([1,2,3], Nothing)` should be impossible. and if `([], Nothing)` is the only "error state", why not just use a `Nothing` for the whole thing instead? and then you can sleep soundly, knowing your pattern-matches are exhaustive :)
ergonomically, it's nicer to to test for failure; and you can do "railway-oriented programming", either doing something with the result or quickly bailing out.
all that said, there's probably cases where `(Stack a, Maybe a)` is more ergonomic... so you know, this isn't dogma
i was going to mention this, but the comment was already long :) of course, this doesn't stop you from implementing it as
stackPop _ = Nothing
or just doing the wrong thing. but it does prevent you from returning `([1,2,3], Nothing)`, and that's always one less thing to worry about - if not for the implementer, then for the users. and the more the signature constrains possible implementations¹, the better!
and this might be subjective, but for me `Maybe (Stack a, a)` results in less cognitive load. with `(Stack a, Maybe a)` if i do
case stackPop xs of
(_, Nothing) -> ...
(xs2, Just x) -> ...
in the back of my head i'm going to be thinking "hmm, am i 100% sure i can throw away that first value if i get a Nothing in there? if it's useless, why does the function return it?²"
whereas with
case stackPop xs of
Nothing -> ...
Just (xs2, x) -> ...
i know for certain there's no new values introduced in Nothing case – great, less things to keep in my head! it's a small thing to be sure, but i like when the types assist me like this :)
---
¹ parametricity is one of my favorite things in pure FP!
² but i hate throwing things away, so it might just be that...
In clojure, pop returns the input with the item removed (so popping a vector returns a vector with the last element removed). To return the actual element, you use a different function (peek, or last).
that's `init` in Haskell, and in this case i'd agree with the OP - i'm used to `pop` letting you actually access the last element, so i'd prefer a different name.
also, doing it that way will require traversing the structure twice, something that's often not free with functional data structures, whereas a tuple-pop does it in one go. similar to how you'd rather split a list at an index and get back two lists rather than do a `take n` and `drop n` separately
I don’t mind it, to me it reads as “pop the top of the stack off”, just like you would in a mutable version. The fact that the popped item is discarded doesn’t change the operation.
As for traversing twice, at least in Clojure, the reason you have peek and last as two separate functions is that peek never traverses, but what it does depends on the type of data structure passed in (and pop works to match that), eg, for a vector, it’s the same result to last and O(1) because vectors are random access, but for lists, peek is the same as first and still O(1), while last is O(n). For lists, pop does the same as rest.
Why have peek/pop when there are other functions that do the same thing? Well, they are designed to be consistent with each other, so regardless of the data structures used, peek will always return the item that pop removes.
right, but would anyone really write a functional `pop` like that? that's just `last`. any sensible functional `pop` would return a tuple:
so i'm not sure i understand what the problem is tbh. we might be in violent agreement...and re: unordered containers, i'd say it "makes as much sense" for immutable and mutable ones. maybe it returns the most recently inserted element or whatever's convenient/efficient to implement; but it's arbitrary regardless of any (im)mutability.