A repository implementing basic algorithms in Haskell.

ToC

• Data Structure
  • Singly Linked List
  • Stack
  • Hash Table
  • Tree
    • Set (balanced binary tree): a set implemented as a balanced binary tree, based on Functional Pearls Efficient sets—a balancing act and Haskell Data.Set.Internal
    • Finger Trees: a sequence built on 2-3 finger trees that gives fast access to both ends, based on Finger trees: a simple general-purpose data structure
• Search
  • Linear Search
  • Binary Search
  • Binary Search Tree (BST)
  • Bit Search
  • Depth First Search
  • Breadth First Search
  • Subsequence
• Sort
  • Bubble Sort
  • Insertion Sort
  • Selection Sort
  • Merge Sort
  • Quick Sort
  • Shell Sort
  • Counting Sort
• Math
  • Euclidean Algorithm: GCD (Greatest Common Divisor), LCM (Least Common Multiple)
  • Prime Numbers: Sieve of Eratosthenes
  • Fermat's Little Theorem
  • Fibonacci
  • Pi Approximation
  • Base N
  • Newton's Method: square root by the Newton-Raphson method
• Compression
  • Run Length Encoding
• Technique
  • Cumulative Sum: prefix sum, range sum query in O(1)

Paper Implementations

• Why Functional Programming Matters: the paper's sample code rewritten in Haskell.

---

ENVIRONMENT

• Nix Flake
• Haskell
  • GHC

For details, see flake.nix.

---

CI

GitHub Actions runs on every push (see ci.yml):

• treefmt --ci: check formatting (ormolu, nixfmt, mdformat).
• check.sh: compile all *.hs files with ghc -Wall and run them. Build artifacts go to a temporary directory, so nothing is left in the repository. You can also run it locally: nix develop --command ./check.sh

---

Reference

Articles

• Why Haskell matters

Books

• Learn You a Haskell for Great Good! (翻訳: すごいHaskell楽しく学ぼう!)

Papers

• Finger trees: a simple general-purpose data structure
• Functional Pearls Efficient sets—a balancing act

---