An educational pure functional programming library in TypeScript
1import { pipe } from "../prelude/compose"
2import { none, type Option, some } from "../prelude/option"
3
4// Phantom property type
5declare const __props: unique symbol
6type Props<P extends string> = { [__props]?: P }
7
8/**
9 * Tracked array with phantom properties.
10 * Properties like "Sorted" or "NonEmpty" are tracked at type level.
11 */
12export type Arr<T, P extends string = never> = readonly T[] & Props<P>
13
14// Property markers
15export type Sorted = "Sorted"
16export type NonEmpty = "NonEmpty"
17
18// Constructor
19export const arr = <T>(xs: readonly T[]): Arr<T> => xs as Arr<T>
20
21// NonEmpty check - returns Option to track the property
22export const nonEmpty = <T, P extends string>(
23 xs: Arr<T, P>,
24): Option<Arr<T, P | NonEmpty>> =>
25 xs.length > 0 ? some(xs as Arr<T, P | NonEmpty>) : none
26
27// Safe accessors for NonEmpty arrays
28export const head = <T, P extends string>(xs: Arr<T, P | NonEmpty>): T => xs[0]!
29export const last = <T, P extends string>(xs: Arr<T, P | NonEmpty>): T =>
30 xs[xs.length - 1]!
31
32// Sorting - adds Sorted property
33export const sortNum = <P extends string>(
34 xs: Arr<number, P>,
35): Arr<number, P | Sorted> =>
36 [...xs].sort((a, b) => a - b) as Arr<number, P | Sorted>
37
38export const sortBy =
39 <T, P extends string>(key: (t: T) => number) =>
40 (xs: Arr<T, P>): Arr<T, P | Sorted> =>
41 [...xs].sort((a, b) => key(a) - key(b)) as Arr<T, P | Sorted>
42
43// Transformations - preserve properties where valid
44export const map =
45 <T, U>(f: (t: T) => U) =>
46 <P extends string>(xs: Arr<T, P>): Arr<U, Exclude<P, Sorted>> =>
47 xs.map(f) as Arr<U, Exclude<P, Sorted>>
48
49export const filter =
50 <T>(pred: (t: T) => boolean) =>
51 <P extends string>(xs: Arr<T, P>): Arr<T, Exclude<P, NonEmpty>> =>
52 xs.filter(pred) as Arr<T, Exclude<P, NonEmpty>>
53
54export const reduce =
55 <T, U>(f: (acc: U, t: T) => U, initial: U) =>
56 <P extends string>(xs: Arr<T, P>): U =>
57 xs.reduce(f, initial)
58
59// Take/drop
60export const take =
61 (n: number) =>
62 <T, P extends string>(xs: Arr<T, P>): Arr<T, Exclude<P, NonEmpty>> =>
63 xs.slice(0, n) as Arr<T, Exclude<P, NonEmpty>>
64
65export const drop =
66 (n: number) =>
67 <T, P extends string>(xs: Arr<T, P>): Arr<T, Exclude<P, NonEmpty>> =>
68 xs.slice(n) as Arr<T, Exclude<P, NonEmpty>>
69
70// Generic binary search with comparator
71export const binarySearch =
72 <T>(compare: (a: T, b: T) => number) =>
73 (target: T) =>
74 <P extends string>(xs: Arr<T, P | Sorted>): Option<number> => {
75 const go = (lo: number, hi: number): Option<number> =>
76 lo > hi
77 ? none
78 : pipe(Math.floor((lo + hi) / 2), (mid) =>
79 ((cmp) =>
80 cmp === 0
81 ? some(mid)
82 : cmp < 0
83 ? go(lo, mid - 1)
84 : go(mid + 1, hi))(compare(target, xs[mid]!)),
85 )
86 return go(0, xs.length - 1)
87 }
88
89// Binary search specialized for numbers
90export const binarySearchNum = binarySearch<number>((a, b) => a - b)