Racket

Algorhythms🔗ℹ

Anurag Muthyam

A Racket library of algorithms and data structures. Every function documented below is exported by algorhythms; there are no submodule imports required for anything on this page.

1 Installation

2 Quick Start

3 Calculator (Arithmetic Operators)

5.1 Higher-Order Functions

1 Installation🔗ℹ

Install from the Racket package catalog:

raco pkg install algorhythms

Or from source:

git clone https://github.com/aryaghan-mutum/algorhythms.git

cd algorhythms

raco pkg install --link .

2 Quick Start🔗ℹ

(require algorhythms)

(factorial 10)                 ; 3628800
(prime? 17)                    ; #t
(encode-to-morse "SOS")        ; "... --- ..."
(add 1 2 3 4 5)                ; 15 (variadic calculator)
(quick-sort '(3 1 4 1 5) <)    ; '(1 1 3 4 5)

3 Calculator (Arithmetic Operators)🔗ℹ

Variadic calculator-style operators that accept any numeric type Racket supports (exact integers, exact rationals, inexact/decimals, complex). Under the hood, the binary implementations use pure recursion (add1 / sub1) for exact integers and delegate to the built-in numeric tower for non-integer inputs.

procedure
(add n ...) → number?
n : number?

Variadic sum. (add) returns 0.

(add 1 2 3 4 5) ; 15
(add 1/2 1/3 1/6) ; 1
(add 1.5 2.5) ; 4.0

procedure
(subtract x y ...) → number?
x : number?
y : number?

Left-to-right difference. With a single argument, negates it.

(subtract 100 10 20 30) ; 40
(subtract 7) ; -7

procedure
(multiply n ...) → number?
n : number?

Variadic product. (multiply) returns 1.

(multiply 2 3 4) ; 24

procedure
(divide x y ...) → number?
x : number?
y : (and/c number? (not/c zero?))

Left-to-right quotient. With a single non-zero argument, returns the reciprocal. Raises an exception on any zero divisor.

(divide 100 5 2) ; 10
(divide 4) ; 1/4

procedure
(modulus a b) → exact-integer?
a : exact-integer?
b : (and/c exact-integer? (not/c zero?))

Integer modulo (matches Racket’s modulo).

procedure
(power-of base n) → number?
base : number?
n : exact-nonnegative-integer?

base raised to non-negative integer n, via repeated multiplication.

procedure
(add-integers-recursive a b) → exact-integer?
a : exact-integer?
b : exact-integer?

Add two integers using only add1/sub1 — a from-scratch recursive demonstration.

procedure
(multiply-integers-recursive a b) → exact-integer?
a : exact-integer?
b : exact-integer?

Multiply two integers using repeated addition — a from-scratch recursive demonstration.

procedure
(multiply-integers-loop a b) → exact-integer?
a : exact-integer?
b : exact-integer?

Same result as multiply-integers-recursive, implemented with an iterative accumulator loop instead of recursion.

4 Math🔗ℹ

4.1 Combinatorics🔗ℹ

procedure
(factorial n) → exact-nonnegative-integer?
n : exact-nonnegative-integer?

Factorial of n. (factorial 0) is 1 (base case).

procedure
(unique-permutations lst) → (listof list?)
lst : list?

All distinct permutations of lst, deduped for repeated elements.

procedure
(pascal-triangle rows)
→ (listof (listof exact-positive-integer?))
rows : exact-positive-integer?

First rows rows of Pascal’s triangle as a list of lists.

4.2 Number Theory🔗ℹ

procedure
(prime? n) → boolean?
n : exact-integer?

#t if n is prime.

procedure
(primes-up-to n) → (listof exact-positive-integer?)
n : exact-integer?

All primes ≤ n, via trial division.

procedure
(primes-up-to-via-sieve n) → (listof exact-positive-integer?)
n : exact-integer?

All primes ≤ n, via the Sieve of Eratosthenes.

procedure
(prime-factors n) → (listof exact-positive-integer?)
n : exact-positive-integer?

Prime factorization as a flat list, e.g. (prime-factors 12) is '(2 2 3).

procedure
(gcd-euclidean a b) → exact-integer?
a : exact-integer?
b : exact-integer?

Greatest common divisor via Euclid’s algorithm. The built-in gcd is also re-exported.

procedure
(lcm-custom a b) → exact-integer?
a : exact-integer?
b : exact-integer?

Least common multiple, derived from gcd-euclidean.

procedure
(fibonacci n) → exact-nonnegative-integer?
n : exact-nonnegative-integer?

The n-th Fibonacci number, computed in O(log n) via matrix exponentiation.

procedure
(collatz-steps n) → exact-positive-integer?
n : exact-positive-integer?

Number of Collatz-conjecture steps needed to reach 1 starting from n (n/2 if even, 3n+1 if odd).

procedure
(leap-year? year) → boolean?
year : exact-integer?

#t when year is a Gregorian leap year.

procedure
(palindrome-num? x) → boolean?
x : exact-integer?

#t when the decimal digits of x read the same forward and backward.

4.3 Arithmetic🔗ℹ

procedure
(square n) → number?
n : number?

Squares n.

procedure
(cube n) → number?
n : number?

Cubes n.

procedure
(absolute n) → number?
n : number?

Absolute value of n.

procedure
(increment n) → number?
n : number?

Returns (add1 n).

procedure
(double n) → number?
n : number?

Returns (* 2 n).

procedure
(halve n) → number?
n : number?

Returns (/ n 2).

procedure
(sum-to-n n) → exact-nonnegative-integer?
n : exact-nonnegative-integer?

Sum of the integers 1..n.

procedure
(power base n) → number?
base : number?
n : exact-nonnegative-integer?

Alias for the built-in expt via a professional name.

4.4 Statistics🔗ℹ

procedure
(mean lst) → real?
lst : (non-empty-listof real?)

Arithmetic mean.

procedure
(median lst) → real?
lst : (non-empty-listof real?)

Median value.

procedure
(mode lst) → any/c
lst : (non-empty-listof any/c)

Most frequent element.

procedure
(variance lst) → real?
lst : (non-empty-listof real?)

Population variance.

procedure
(standard-deviation lst) → real?
lst : (non-empty-listof real?)

Population standard deviation.

procedure
(percentile lst p) → real?
lst : (non-empty-listof real?)
p : (real-in 0 100)

Value at the given percentile.

4.5 Financial🔗ℹ

procedure
(simple-interest principal time rate) → real?
  principal : real?
  time : real?
  rate : real?

P × R × T.

procedure
(compound-interest principal time rate) → real?
  principal : real?
  time : real?
  rate : real?

Standard compound-interest formula.

procedure
(npv rate cashflows) → real?
rate : real?
cashflows : (listof real?)

Net Present Value of a stream of cashflows.

procedure
(irr cashflows) → real?
cashflows : (listof real?)

Internal Rate of Return of a stream of cashflows.

4.6 Matrix🔗ℹ

procedure
(matrix-multiply m1 m2) → (listof list?)
m1 : (listof list?)
m2 : (listof list?)

Standard matrix multiplication using lists of lists.

procedure
(matrix-transpose m) → (listof list?)
m : (listof list?)

Matrix transpose.

procedure
(matrix-determinant m) → real?
m : (listof list?)

Matrix determinant.

procedure
(matrix-inverse m) → (or/c (listof list?) #f)
m : (listof list?)

Matrix inverse or #f if singular.

procedure
(identity-matrix n) → (listof list?)
n : exact-positive-integer?

n × n identity matrix.

4.7 Algebra🔗ℹ

procedure
(solve-linear a b) → real?
a : real?
b : real?

Solves a·x + b = 0 for x.

procedure
(quadratic-formula a b c) → (list/c any/c any/c)
  a : real?
  b : real?
  c : real?

Both roots of the quadratic a·x² + b·x + c = 0.

procedure
(fast-expt base n) → number?
base : number?
n : exact-nonnegative-integer?

Fast exponentiation in O(log n).

4.8 Trigonometry🔗ℹ

procedure
(sine x) → real?
x : real?

Sine of x radians (custom Taylor-series).

procedure
(cosine x) → real?
x : real?

Cosine of x radians.

procedure
(tangent x) → real?
x : real?

Tangent of x radians.

procedure
(hypotenuse a b) → real?
a : real?
b : real?

√(a² + b²).

procedure
(degrees->radians deg) → real?
deg : real?

Degrees → radians.

procedure
(radians->degrees rad) → real?
rad : real?

Radians → degrees.

4.9 Geometry🔗ℹ

procedure
(circle-area r) → real?
r : real?

Area of a circle.

procedure
(rectangle-area len wid) → real?
len : real?
wid : real?

Area of a rectangle.

procedure
(area-of-triangle base height) → real?
base : real?
height : real?

Triangle area.

procedure
(heron a b c) → real?
  a : real?
  b : real?
  c : real?

Triangle area via Heron’s formula.

procedure
(sphere-volume r) → real?
r : real?

Volume of a sphere.

procedure
(cube-volume s) → real?
s : real?

Volume of a cube.

procedure
(pythagoras x y) → real?
x : real?
y : real?

√(x² + y²).

4.10 Logarithms🔗ℹ

procedure
(log-custom b n) → real?
b : real?
n : real?

Logarithm base b of n.

5 Data Structures🔗ℹ

5.1 Higher-Order Functions🔗ℹ

procedure
(mapper fn lst) → list?
fn : procedure?
lst : list?

Map fn over lst from scratch.

procedure
(filter-custom pred lst) → list?
pred : procedure?
lst : list?

Keep elements satisfying pred.

procedure
(reduce fn lst) → any/c
fn : procedure?
lst : list?

Reduce to a single value.

procedure
(foldl-custom fn init lst) → any/c
  fn : procedure?
  init : any/c
  lst : list?

Left fold.

procedure
(foldr-custom fn init lst) → any/c
  fn : procedure?
  init : any/c
  lst : list?

Right fold.

procedure
(flatten-list lst) → list?
lst : any/c

Flatten any nested structure into a single-level list.

procedure
(flatmap lst) → list?
lst : list?

Flatten nested lists (single-argument form).

procedure
(compose-fns fn ...) → procedure?
fn : procedure?

Right-to-left function composition.

procedure
(pipe fn ...) → procedure?
fn : procedure?

Left-to-right function composition.

procedure
(curry2 fn) → procedure?
fn : (any/c any/c -> any/c)

Curry a 2-argument function.

procedure
(complement fn) → procedure?
fn : procedure?

Return a function that negates fn’s result.

procedure
(make-counter) → procedure?

Return an independent counter that yields 0, 1, 2, ....

procedure
(lazy thunk) → (-> any/c)
thunk : (-> any/c)

Wrap thunk so it evaluates on first call and caches the result thereafter.

procedure
(memoize fn) → (any/c -> any/c)
fn : (any/c -> any/c)

Return a memoized version of fn that caches results per argument.

(define fib-memo
  (memoize (lambda (n)
             (if (<= n 1) n
                 (+ (fib-memo (- n 1)) (fib-memo (- n 2)))))))

5.2 Lists🔗ℹ

procedure
(my-length lst) → exact-nonnegative-integer?
lst : list?

Length via iterative accumulator (a from-scratch counterpart to the built-in length).

procedure
(my-last lst) → any/c
lst : (and/c list? (not/c empty?))

Last element.

procedure
(penultimate lst) → any/c
lst : list?

Second-to-last element.

procedure
(remove-last lst) → list?
lst : list?

Return lst without its last element.

procedure
(nth lst pos) → any/c
lst : list?
pos : exact-positive-integer?

1-indexed element access.

procedure
(occurrences item lst) → exact-nonnegative-integer?
item : any/c
lst : list?

Count occurrences of item in lst (uses equal?).

procedure
(remove-element item lst) → list?
item : any/c
lst : list?

Return lst with every occurrence of item removed.

procedure
(zip lst ...) → (listof list?)
lst : list?

Transpose several lists into a list of tuples, truncating to the shortest.

procedure
(append-custom lst1 lst2) → list?
lst1 : list?
lst2 : list?

Concatenate two lists using natural recursion (custom to avoid shadowing the built-in append).

procedure
(copy-list lst) → list?
lst : list?

Return a fresh flat copy of lst.

procedure
(copy-tree tr) → any/c
tr : any/c

Return a fresh cons-tree with the same structure and leaves.

procedure
(range-1-to-n n) → (listof exact-positive-integer?)
n : exact-integer?

Build the list '(1 2 ... n); empty when n ≤ 0.

procedure
(alternative-elems lst) → list?
lst : list?

Every other element, starting with the first.

procedure
(pack lst) → (listof list?)
lst : list?

Group consecutive equal elements into sublists.

procedure
(encode lst) → (listof (list exact-nonnegative-integer? any/c))
lst : list?

Run-length encode lst: '(a a b c c) → '((2 a) (1 b) (2 c)).

procedure
(member-custom? item lst) → boolean?
item : any/c
lst : list?

#t when item is present in lst.

procedure
(palindrome-lst? lst) → boolean?
lst : list?

#t when lst reads the same forward and backward.

5.3 Sets🔗ℹ

procedure
(unique-elements lst) → list?
lst : list?

Remove duplicates, preserving first-occurrence order.

procedure
(set-union a b) → list?
a : list?
b : list?

Set union (deduplicated).

procedure
(set-intersection a b) → list?
a : list?
b : list?

Set intersection, preserving a’s order.

procedure
(compress lst) → list?
lst : list?

Collapse consecutive equal elements (Unix uniq).

procedure
(duplicates-by-elem lst item) → list?
lst : list?
item : any/c

Every occurrence of item in lst.

procedure
(set-move-elem-to-last lst e) → list?
lst : (listof number?)
e : number?

Move every occurrence of e to the end of the list, keeping only one.

5.4 Sorting🔗ℹ

procedure
(bubble-sort lst less?) → list?
lst : list?
less? : (any/c any/c -> any/c)

Bubble sort with a comparator. Pass < for ascending numeric order.

procedure
(insertion-sort lst) → (listof real?)
lst : (listof real?)

Insertion sort, ascending order.

procedure
(quick-sort lst less?) → list?
lst : list?
less? : (any/c any/c -> any/c)

Quicksort with a comparator.

procedure
(selection-sort lst) → (listof real?)
lst : (listof real?)

Selection sort, ascending order.

5.5 Strings🔗ℹ

procedure
(reverse-words str) → string?
str : string?

Reverse the order of whitespace-separated tokens.

procedure
(reverse-chars-in-str str) → string?
str : string?

Reverse the characters of str.

procedure
(string-find pattern str) → (or/c exact-nonnegative-integer? #f)
pattern : string?
str : string?

KMP substring search; returns the start index or #f.

procedure
(string-hash-custom str) → exact-nonnegative-integer?
str : string?

DJB-style hash of str.

procedure
(string-index-of-char ch str)
→ (or/c exact-nonnegative-integer? #f)
ch : char?
str : string?

0-based index of the first occurrence of ch, or #f.

procedure
(string-split-custom sep str) → (listof string?)
sep : char?
str : string?

Split str on single-character separator sep.

procedure
(string-join-custom sep lst) → string?
sep : char?
lst : (listof string?)

Join a list of strings with single-character separator sep.

procedure
(string-upcase-custom str) → string?
str : string?

Upper-case every character.

procedure
(string-downcase-custom str) → string?
str : string?

Lower-case every character.

5.6 Queue🔗ℹ

procedure
(make-queue) → queue?

Create an empty FIFO queue.

procedure
(queue-empty? q) → boolean?
q : queue?

#t when q is empty.

procedure
(enqueue! q v) → void?
q : queue?
v : any/c

Append v to the back of q.

procedure
(dequeue! q) → any/c
q : queue?

Remove and return the front element; raises on empty.

procedure
(queue-peek q) → any/c
q : queue?

Return the front element without removing it.

5.7 Stack🔗ℹ

procedure
(make-stack) → procedure?

Create a message-passing LIFO stack. Send 'empty?, 'top, 'push!, or 'pop!.

(define s (make-stack))
(s 'push! 1)
(s 'push! 2)
(s 'top) ; 2
(s 'pop!)
(s 'top) ; 1

6 Encoding🔗ℹ

procedure
(encode-to-morse str) → string?
str : string?

Encode str to Morse code (letters, digits, common punctuation). Word breaks encode as "/".

(encode-to-morse "SOS") ; "... --- ..."
(encode-to-morse "HELLO") ; ".... . .-.. .-.. ---"

procedure
(decode-from-morse morse) → string?
morse : string?

Decode a Morse-encoded string produced by encode-to-morse back to upper-case text. Raises on unsupported tokens.

1	Installation
2	Quick Start
3	Calculator (Arithmetic Operators)
4	Math
5	Data Structures
6	Encoding
7	License