Tag Archives: scala adt

Scala Binary Search Tree

1 Reply

When I wrote about Scala linked list implementation a couple of years ago, I also did some quick ground work for implementing binary search trees (BST). Occupied by other R&D projects at the time, it was put aside and has since been patiently awaiting its turn to see the light of day. As much of the code is already there, I’m going to put it up in this blog post along with some narrative remarks.

First, we come up with an ADT (algebraic data type). Let’s call it BSTree, starting out with a base trait with generic type A for the data element to be stored inside the tree structure, to be extended by a case class BSBranch as tree branches and a case object BSLeaf as “null” tree nodes. The ADT’s overall structure resembles that of the one used in the linked list implementation described in the old post.

ADT BSTree

A few notes:

  • Data elements (of generic type A) are stored only in branches and data of the same value will go to the same branch and be represented with a proper count value.
  • BSTree is covariant, or else BSLeaf can’t even be defined as a sub-type of BSTree[Nothing].
  • A toString method is created for simplified string output of a tree instance.

Populating a BSTree

One of the first things we need is a method to insert tree nodes into an existing BSTree. We start expanding the base trait with method insert(). That’s all great for adding a node one at a time, but we also need a way to create a BSTree and populate it from a readily available collection of data elements. It makes sense to delegate such a factory method to the companion object BSTree as its method apply().

Note that type parameter B for insert() needs to be a supertype of A because Function1 is contravariant over its parameter type. In addition, the context bound “B : Ordering” constrains type B to be capable of being ordered (i.e. compared) which is necessary for traversing a binary search tree.

Testing BSTree.apply():

Tree traversal and finding tree nodes

Next, we need methods for tree traversal and search. For brevity, we only include in-order traversal.

Using the tree created above:

Removing tree nodes

To be able to remove tree nodes that consist of a specific or range of element values, we include also the following few methods in the base trait.

Note that delete() may involve a little shuffling of the tree nodes. Once the tree node to be removed is located, that node may need to be filled with the node having the next-bigger element & count values from its right node (or equivalently, the node having the next-smaller element from its left node).

Method trim() removes tree nodes with element values below or above the provided range. Meanwhile, method cutOut() does the opposite by cutting out tree nodes with values within the given range. It involves slightly more work than trim(), requiring the use of delete() for individual tree nodes.

Example:

Rebuilding a binary search tree

A highly unbalanced binary search tree beats the purpose of using such a data structure. One of the most straight forward ways to rebuild a binary search tree is to “unpack” the individual tree nodes of the existing tree by traversing in-order into a list (e.g. a Vector or List) of elements, followed by reconstructing a new tree with nodes being assigned elements from recursively half-ing the in-order node list.

Example:

Thoughts on the ADT

An alternative to how the ADT is designed is to have the class fields and methods declared in the BSTree base trait with specific implementations reside within subclasses BSBranch and BSLeaf, thus eliminating the need of the boiler-plate pattern matching for the subclasses. There is also the benefit of making class fields like left & right referenceable from the base trait, though they would need to be wrapped in Options with value None for BSLeaf.

As can be seen with the existing ADT, an advantage is having all the binary tree functions defined within the base trait once and for all. If there is the need for having left and right referenceable from the BSTree base trait, one can define something like below within the trait.

Example:

Then there is also non-idiomatic approach of using mutable class fields in a single tree class commonly seen in Java implementation, like below:

Addendum: Complete source code of the BSTree ADT

Implementing Linked List In Scala

3 Replies

In Scala, if you wonder why its standard library doesn’t come with a data structure called LinkedList, you may have overlooked. The collection List is in fact a linked list — although it often appears in the form of a Seq or Vector collection rather than the generally “mysterious” linked list that exposes its “head” with a hidden “tail” to be revealed only iteratively.

Our ADT: LinkedNode

Perhaps because of its simplicity and dynamicity as a data structure, implementation of linked list remains a popular coding exercise. To implement our own linked list, let’s start with a barebone ADT (algebraic data structure) as follows:

If you’re familiar with Scala List, you’ll probably notice that our ADT resembles List and its subclasses Cons (i.e. ::) and Nil (see source code):

Expanding LinkedNode

Let’s expand trait LinkedNode to create class methods insertNode/deleteNode at a given index for inserting/deleting a node, toList for extracting contained elements into a List collection, and toString for display:

Note that LinkedNode is made covariant. In addition, method insertNode has type A as its lower type bound because Function1 is contravariant over its parameter type.

Recursion and pattern matching

A couple of notes on the approach we implement our class methods with:

  1. We use recursive functions to avoid using of mutable variables. They should be made tail-recursive for optimal performance, but that isn’t the focus of this implementation. If performance is a priority, using conventional while-loops with mutable class fields elem/next would be a more practical option.
  2. Pattern matching is routinely used for handling cases of Node versus EmptyNode. An alternative approach would be to define fields elem and next in the base trait and implement class methods accordingly within Node and EmptyNode.

Finding first/last matching nodes

Next, we add a couple of class methods for finding first/last matching nodes.

Reversing a linked list by groups of nodes

Reversing a given LinkedNode can be accomplished via recursion by cumulatively wrapping the element of each Node in a new Node with its next pointer set to the Node created in the previous iteration.

Method reverseK reverses a LinkedNode by groups of k elements using a different approach that extracts the elements into groups of k elements, reverses the elements in each of the groups and re-wraps each of the flattened elements in a Node.

Using LinkedNode as a Stack

For LinkedNode to serve as a Stack, we include simple methods push and pop as follows:

Addendum: implementing map, flatMap, fold

From a different perspective, if we view LinkedNode as a collection like a Scala List or Vector, we might be craving for methods like map, flatMap, fold. Using the same approach of recursion along with pattern matching, it’s rather straight forward to crank them out.

Putting everything together

Along with a few additional simple class methods and a factory method wrapped in LinkedNode‘s companion object, below is the final LinkedNode ADT that includes everything described above.

A cursory test-run …

Traversing A Scala Collection

Leave a reply

When we have a custom class in the form of an ADT, say, Container[A] and are required to process a collection of the derived objects like List[Container[A]], there might be times we want to flip the collection “inside out” to become a single “container” of collection Container[List[A]], and maybe further transform the inner collection with a function.

For those who are familiar with Scala Futures, the nature of such transformation is analogous to what method Future.sequence does. In case the traversal involves also applying to individual elements with a function, say, f: A => Container[B] to transform the collection into Container[List[B]], it’ll be more like how Future.traverse works.

To illustrate how we can come up with methods sequence and traverse for the collection of our own ADTs, let’s assemble a simple ADT Fillable[A]. Our goal is to create the following two methods:

For simplicity, rather than a generic collection like IterableOnce, we fix the collection type to List.

A simple ADT

It looks a little like a home-made version of Scala Option, but is certainly not very useful yet. Let’s equip it with a companion object and a couple of methods for transforming the element within a Fillable:

With slightly different signatures, methods map and flatMap are now available for transforming the element “contained” within a Fillable.

A couple of quick notes:

  • Fillable[A] is made covariant so that method map/flatMap is able to operate on subtypes of Fillable.
  • Using of self-type annotation isn’t necessary here, but is rather a personal coding style preference.

Testing the ADT:

Sequencing a collection of Fillables

Let’s assemble method sequence which will reside within the companion object. Looking at the signature of the method to be defined:

it seems logical to consider aggregating a List from scratch within Fillable using Scala fold. However, trying to iteratively aggregate a list out of elements from within their individual “containers” isn’t as trivial as it may seem. Had there been methods like get/getOrElse that unwraps a Fillable to obtain the contained element, it would’ve been straight forward – although an implementation leveraging a getter method would require a default value for the contained element to handle the Emptied case.

One approach to implement sequence using only map/flatMap would be to first map within the fold operation each Fillable element of the input List into a list-push function for the element’s contained value, followed by a flatMap to aggregate the resulting List by iteratively applying the list-push functions within the Fillable container:

Note that pushToList within map is now regarded as a function that takes an element of type A and returns a List[A] => List[A] function. The expression fa.map(pushToList).flatMap(acc.map) is just a short-hand for:

In essence, the first map transforms element within each Fillable in the input list into a corresponding list-push function for the specific element, and the flatMap uses the individual list-push functions for the inner map to iteratively aggregate the list inside the resulting Fillable.

Traversing the Fillable collection

Next, we’re going to define method traverse with the following signature within the companion object:

In case it doesn’t seem obvious, based on the method signatures, sequence is really just a special case of traverse with f(a: A) = Fillable(a)

Similar to the way sequence is implemented, we’ll also use fold for iterative aggregating the resulting list. Since an element of type Fillable[A] when flatMap-ed with the provided function f would yield a Fillable[B], we’re essentially dealing with the same problem we did for sequence except that we type A is now replaced with type B.

Putting everything together:

Testing with the newly created methods: