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

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.