Created
June 24, 2021 06:26
-
-
Save texastoland/7a51e4dec1cb45f4686f715933fa85b9 to your computer and use it in GitHub Desktop.
Linked list comparison between TypeScript and ReScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
export abstract class List<T> { | |
readonly isEmpty: boolean | |
constructor(readonly length: number) { | |
this.isEmpty = !length | |
} | |
*[Symbol.iterator](): Generator<T, void, void> { | |
for (let xs = this as List<T>; xs instanceof NonEmptyList; xs = xs.rest) | |
yield xs.first | |
} | |
} | |
export class NonEmptyList<T> extends List<T> { | |
constructor(readonly first: T, readonly rest: List<T>) { | |
super(rest.length + 1) | |
} | |
} | |
export class EmptyList extends List<never> { | |
static #instance: EmptyList | |
constructor() { | |
super(0) | |
return (EmptyList.#instance ??= this) | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import { EmptyList, List, NonEmptyList } from "./list-classes" | |
export const empty = new EmptyList() | |
export const shift = <T>(first: T, rest: List<T>) => | |
new NonEmptyList(first, rest) | |
export const make = <T>(...xs: T[]) => | |
xs.reduceRight((ys, x) => shift(x, ys), empty as List<T>) | |
export const convert = <T>(xs: Iterable<T>) => make(...xs) | |
export const push = <T>(xs: List<T>, x: T): NonEmptyList<T> => | |
xs instanceof NonEmptyList | |
? shift(xs.first, push(xs.rest, x)) | |
: shift(x, empty) | |
export const pop = <T>({ first, rest }: NonEmptyList<T>): [List<T>, T] => { | |
if (rest instanceof NonEmptyList) { | |
const [init, last] = pop<T>(rest) | |
return [shift(first, init), last] | |
} else return [empty, first] | |
} | |
export const unsafeGet = <T>(xs: NonEmptyList<T>, index: number) => { | |
if (index < -xs.length || index >= xs.length) | |
throw new Error("index out of bounds") | |
const safeGet = ({ first, rest }: NonEmptyList<T>, index: number): T => | |
index < 1 ? first : safeGet(rest as NonEmptyList<T>, index - 1) | |
return safeGet(xs, index < 0 ? index + xs.length : index) | |
} | |
export const unsafeDelete = <T>(xs: NonEmptyList<T>, index: number) => { | |
if (index < -xs.length || index >= xs.length) | |
throw new Error("index out of bounds") | |
const safeDelete = ( | |
{ first, rest }: NonEmptyList<T>, | |
index: number, | |
): [List<T>, T] => { | |
if (index < 1) return [rest, first] | |
else { | |
const [skipped, deleted] = safeDelete(rest as NonEmptyList<T>, index - 1) | |
return [shift(first, skipped), deleted] | |
} | |
} | |
return safeDelete(xs, index < 0 ? index + xs.length : index) | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import { EmptyList } from "./list-classes" | |
import * as List from "./list-functions" | |
const shiftTest = List.shift("hello", List.shift("world", List.empty)) //? | |
const makeTest = List.make("hello", "world") //? Array.from($) | |
const emptyTest = List.make() //? Array.from($) | |
console.assert(emptyTest === new EmptyList()) | |
const pushPopTest = List.pop(List.push(List.push(List.empty, "hello"), "world")) //? | |
List.unsafeGet(shiftTest, 0) //? | |
List.unsafeGet(shiftTest, 1) //? | |
// List.unsafeGet(shiftTest, 2) // exception | |
const deleteTest = List.unsafeDelete(shiftTest, 0) //? $[0] | |
List.unsafeDelete(shiftTest, 1) //? $[1] | |
// List.unsafeDelete(shiftTest, 2) // exception |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
type rec list<'t> = EmptyList | NonEmptyList('t, list<'t>, int) | |
let length = xs => | |
switch xs { | |
| EmptyList => 0 | |
| NonEmptyList(_, _, length) => length | |
} | |
let empty = EmptyList | |
let shift = (rest, first) => NonEmptyList(first, rest, rest->length + 1) | |
let make = xs => xs->Belt.Array.reduceReverse(empty, shift) | |
/* | |
let makeTest = ["hello", "world"]->make | |
* convert is impossible :( | |
*/ | |
let rec push = (xs, x) => | |
switch xs { | |
| EmptyList => empty->shift(x) | |
| NonEmptyList(first, rest, _) => rest->push(x)->shift(first) | |
} | |
@warning("-8") | |
let rec unsafePop = (NonEmptyList(first, rest, _)) => | |
switch rest { | |
| EmptyList => (empty, first) | |
| NonEmptyList(_, _, _) => { | |
let (init, last) = rest->unsafePop | |
(init->shift(first), last) | |
} | |
} | |
let unsafeGet = (xs, index) => { | |
let length = xs->length | |
if index < length || index >= length { | |
invalid_arg("index out of bounds") | |
} | |
@warning("-8") | |
let rec safeGet = (NonEmptyList(first, rest, _), index) => | |
index == 0 ? first : rest->safeGet(index - 1) | |
xs->safeGet(index < 0 ? index + length : index) | |
} | |
let unsafeDelete = (xs, index) => { | |
let length = xs->length | |
if index < length || index >= length { | |
invalid_arg("index out of bounds") | |
} | |
@warning("-8") | |
let rec safeDelete = (NonEmptyList(first, rest, _), index) => { | |
if index == 0 { | |
(rest, first) | |
} else { | |
let (skipped, deleted) = rest->safeDelete(index - 1) | |
(skipped->shift(first), deleted) | |
} | |
} | |
xs->safeDelete(index < 0 ? index + length : index) | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Show hidden characters
{ | |
"compilerOptions": { | |
"target": "ESNext", | |
"strict": true, | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment