Stack/LinkedList

A.scala

sealed trait Thing[+A]

object Thing {
  case class SomeThing[A](value: A, next: Thing[A]) extends Thing[A]
  case object NotAThing extends Thing[Nothing]
}

B.scala

// I can use `Thing` as a Linked List

//These are the two most important...
def headOption[A](xs: Thing[A]): Option[A] = xs match {
  case SomeThing(a, _) => Some(a)
  case NotAThing => None
}

def tail[A](xs: Thing[A]): Thing[A] = xs match {
  case SomeThing(_, rest) => rest
  case NotAThing => NotAThing
}

// But I can also do things like...
def take[A](xs: Thing[A])(n: Int): Thing[A] = 
  if(n <= 0) NotAThing else xs match {
    case SomeThing(first, rest) => SomeThing(first, take(rest)(n - 1))
    case NotAThing => NotAThing
  }

def map[A,B](xs: Thing[A])(f: A => B): Thing[B] = xs match {
  case SomeThing(first, rest) => SomeThing(f(first), map(rest)(f))
  case NotAthing => NotAThing
}

// You get the idea
                                         

C.scala

// But you can also use this like a stack

def peek[A](stack: Thing[A]): Option[A] = stack match {
  case SomeThing(first, _) => Some(first)
  case NotAThing => None
}

def push[A](stack: Thing[A])(a: A): Thing[A] = SomeThing(a, stack)

def pop(stack: Thing[A]): (Option[A], Thing[A]) = stack match {
  case SomeThing(first, rest) => (Some(first), rest)
  case NotAThing => (None, stack)
}

@bkyrlach the difference is purely in memory layout, right? Which yes, you are correct, is opaque from the perspective of the user of the API, but we should expect it to have a runtime difference. I think that's something we can empirically prove.

A stack's members are guaranteed to be next to each other in memory. A linked list does not make this guarantee. So in that way, it does matter to the user to know what the underlying structure is, and so they are not equivalent data structures?

(I think I see what you're saying though? You're saying you COULD implement a linked list such that all the items are next to each other in memory...? And you're thinking of that as an implementation detail?)

@OmarShehata I'm getting bullied enough for this (and my comments) on Twitter. Not sure anything I say here is gonna help. I'll give you the benefit of the doubt here and try and engage.

I don't think that the definition of a stack is built on an assumption of contiguous memory. I thought the study of computer science wasn't as worried about the specific architecture of the computer (think about pioneers like Ada Lovelace).

So, yes, in short, it seems like the essence of a data structure is...

• Can you expose an API that allows for the operations you need
• Do those operations have the expected computational complexity

Memory layout feels like an optimization choice that adds many additional factors. It may be true what everyone is saying on Twitter that it's always, without fail, better to implement a stack with a dynamic array. My experience has been that generally always is rarely true.

Here's an interesting question that I'm too scared to post on Twitter (since I've been nonstop roasted for the last several hours). How would you describe a stack or a linked list in lambda calculus?

I'll give you the benefit of the doubt here and try and engage.

I do appreciate that. I am sorry a lot of people are dunking on you, I think the discussion you're having with Jon is interesting and I'm certain that a lot of people are learning from it, because a lot of us don't have a very deep understanding of these things (I think many of the people dunking don't really know how to explain it. Many probably do but they should just explain it and engage in good faith). I try to remember that a magnitude more people read the exchange than are arguing in it, and I try to speak to them even if I don't think I'll convince my interlocuters.

I don't think that the definition of a stack is built on an assumption of contiguous memory.

I think this is a reasonable thing to say, and I think this is the implicit assumption a lot of people are coming in with. My understanding is most people would say the definition of it requires contiguous memory, and that this matters for practical every day work etc. But I think what you're saying makes sense. That, technically speaking, from a theoretical computer science perspective, it shouldn't matter. Like we can construe perhaps an alternative turing machine architecture where they would be equivalent.

I would expect that you and I should agree on the following: if have a hundred million data points that we're processing in real time every frame, we can measure a significant performance difference between it living in contiguous memory vs not. (I think maybe people started the discussion thinking you were disagreeing with that, and then after that everyone was being too defensive to recognize the subtle nuances we're talking about here)

Here's an interesting question that I'm too scared to post on Twitter (since I've been nonstop roasted for the last several hours). How would you describe a stack or a linked list in lambda calculus?

That is an interesting question that I'd love to know the answer to as well!

I do hope you'll maybe mute notifications and go relax for the rest of the day / prioritize your well being here! Have a wonderful day and thanks again for engaging (and for spurring an interesting discussion even it came at a personal cost)

@OmarShehata You have single-handedly restored my faith in humanity. I think your analysis/understanding of my argument and what happened in that Twitter thread are spot on.

Thank you so much. I’ve been feeling so crappy watching all of these notifications come in calling me terrible things. I hope you’re having a lovely day wherever you are.