A simple data class based on an existing collection (Scala)

Question

I'm fairly new to Scala and I would like to learn it properly. My current task is to create a type to represent a heap, as seen in interpreters: a mapping from addresses in memory to values stored there.

A heap of that kind is very much like Map, but I would like to hide implementation details and only expose the interface consisting of a few methods, which in pseudo code would be:

* update :: address value -> Heap
* free :: address -> Heap
* alloc :: value -> (Heap, Address)
* addresses :: () -> Set[Address]
* lookup :: address -> [Value]

Here is what I came up with:

trait Heap[T] {

  def update(address: Address, value: T): Heap[T]

  def free(address: Address): Heap[T]

  def alloc(value: T): (Heap[T], Address)

  def addresses(): Set[Address]

  def lookup(address: Address): Option[T]
}

private case class HeapImpl[T](map: Map[Address, T]) extends Heap[T] {
  override def update(address: Address, value: T): Heap[T] = HeapImpl[T](map.updated(address, value))

  override def free(address: Address): Heap[T] = HeapImpl[T](map.removed(address))

  override def alloc(value: T): (Heap[T], Address) = {
    val nextFreeAddress = addresses().maxOption.getOrElse(0) + 1
    (HeapImpl(map.updated(nextFreeAddress, value)), nextFreeAddress)
  }

  override def addresses(): Set[Address] = map.keys.toSet

  override def lookup(address: Address): Option[T] = map.get(address)
}

object Heap {
  def apply[T](): Heap[T] = HeapImpl(Map())
}

I would like to know if this is proper idiomatic Scala or should I approach it differently.

jwvh · Accepted Answer · 2020-03-11 08:51:46Z

Your code, as posted, doesn't compile because there is no definition for the Address type. However, given the code for nextFreeAddress in the alloc() method, it's pretty obvious that Address can only be type Int, so that's easy to fix.

Also, HeapImpl is private to ... what? A surrounding object I assume, but that's also missing from the posted code so it's a bit unclear. You say you "would like to hide implementation details," which is a good thing, but I don't know that a private implementation class is significantly more hidden than having private members of a public class. Is the implementation class separate because you envision multiple different implementations available to the end user?

It's a bit unusual to have a factory method that takes no parameters except for a type parameter. It wouldn't be difficult to enhance the "constructor" to take optional initial values.

object Heap {
  def apply[T](ts:T*): Heap[T] = HeapImpl(ts.indices.map(x => x -> ts(x)).toMap)
}

Then you can have it both ways:

Heap[Char]()           //res0: Heap[Char] = HeapImpl(Map())
Heap(3L, 5L, 12L, 2L)  //res1: Heap[Long] = HeapImpl(Map(0 -> 3, 1 -> 5, 2 -> 12, 3 -> 2))

(Notice that the REPL has leaked a bit of your implementation detail.)

At first I was confused by the term Heap. Then I re-read the posting and realized that this isn't a heap data structure but is, instead, a chunk of memory for dynamic allocation and requiring memory management.

But your code doesn't actually do any of the things that makes a real heap challenging/interesting: dynamic allocation for heterogeneous data, handle fragmentation, etc. It sort of pretends to be a heap, but not very convincingly (your alloc() doesn't really act like malloc(), calloc(), or realloc()). It's just a thin wrapper around a highly restricted associative array.

So, while I find little to fault in the code, I can't see where it serves much purpose.

"Also, HeapImpl is private to ... what? A surrounding object I assume" -- The package. This is what I have at the top level in a file, the only thing missing was a package declaration. Anyway, thanks! Good point that I might have as well have a class with public methods instead of a trait (since I don't expect alternative implementations). — siledh
– siledh, Commented Mar 11, 2020 at 17:42

Stack Exchange Network

A simple data class based on an existing collection (Scala)

1 Answer 1

You must log in to answer this question.

Hot Network Questions

A simple data class based on an existing collection (Scala)

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions