bradcater/scalacaster

Purely Functional Algorithms and Data Structures in Scala

Why Scalacaster?

Since Fender Stratocaster is a classic guitar, Scalacaster is classic algorithms and data structures in Scala. Scalacaster includes loads of widely used implementation techniques and approaches which have been developed by best programmers and enthusiasts of functional programming. Studying purely functional data structures is always fun and challenge for researchers, since data structures in a functional setting are much elegant and smarter than in an imperative setting.

How to use Scalacaster?

Scalacaster is neither a library nor framework. Moreover, Scalacaster`s code is not supposed to be executed at all. The code is neither for Scala compiler nor JVM. It is for human beings. For enthusiasts and researchers of the Scala programming language and it's application in the area of implementation of the purely functional data structures. So, the best way to use Scalacaster is to read through it's source code and comments.

What is inside?

Primitive routines

• Numbers theory src/primitive/Numbers.scala
• Strings src/primitive/Strings.scala

Simple Collections

• List src/collection/List.scala
• Queue src/collection/Queue.scala
• Stack src/collection/Stack.scala
• Set src/collection/Set.scala

Heaps

• Standard Binary Heap src/heap/StandardHeap.scala
• Leftist Heap src/heap/LeftistHeap.scala
• Pairing Heap src/heap/PairingHeap.scala
• Skew Heap src/heap/SkewHeap.scala

Trees

• Binary Search Tree src/tree/Tree.scala
• Red-Black Tree src/tree/RBTree.scala
• AA Tree src/tree/AATree.scala

Graphs

• Graph src/graph/Graph.scala
• InductiveGraph src/graph/InductiveGraph.scala

Sorting Algorithms

• Quick Sort src/sort/QuickSort.scala
• Merge Sort src/sort/MergeSort.scala
• Bubble Sort src/sort/BubbleSort.scala
• Insertion Sort src/sort/InsertionSort.scala
• Selection Sort src/sort/SelectionSort.scala

Searching Algorithms

• Selection Search (k-th order statistic) src/search/SelectionSearch.scala
• Binary Search src/search/BinarySearch.scala
• Linear Search src/search/LinearSearch.scala

How to contribute?

• Give it a star
• Drop the feedback to the author @vkostyukov
• Send a PR with fixes of typos/bugs/etc

What to read next?

• Slides about Scalacaster
• Purely Functional Data Structures by Chris Okasaki
• What's new in Purely Functional DS since Okasaki
• A Functional Approach to Standard Binary Heaps (see StandardHeap.scala)
• Combinatorial Algorithms in Scala