Last active
April 12, 2017 04:50
-
-
Save reissbaker/f786f83b19960f7f388658794f6bd02a to your computer and use it in GitHub Desktop.
typescript port of aphyr's "reversing the technical interview." compiled with --noImplicitAny and --strictNullChecks, obv.
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 empty = undefined | null; | |
| type Maybe<T> = T | empty; | |
| type TrueCell<T> = (b: true) => T; | |
| type FalseCell<T> = (b: false) => Maybe<TrueCell<T> | FalseCell<T>>; | |
| type Cell<T> = TrueCell<T> | FalseCell<T>; | |
| type Next<T> = Maybe<Cell<T>>; | |
| type Iteration<T> = T | Next<T>; | |
| /* | |
| * Get the value of a Cell | |
| */ | |
| function value<T>(cell: Cell<T>): T { | |
| const realized: TrueCell<T> = cell as TrueCell<T>; | |
| return realized(true); | |
| } | |
| /* | |
| * Get the next list item from a Cell | |
| */ | |
| function next<T>(cell: Cell<T>): Next<T> { | |
| const iterator: FalseCell<T> = cell as FalseCell<T>; | |
| return iterator(false); | |
| } | |
| /* | |
| * Given a value and an optional list, return a new list with the value prepended to the old list. | |
| */ | |
| function cons<T>(x: T, next?: Next<T>): Cell<T> { | |
| // A cell function is an overloaded function that does different things depending on whether it | |
| // takes true or false. Define the overload here, and return it. | |
| function cell(b: true): T; | |
| function cell(b: false): Next<T>; | |
| function cell(b: boolean): Iteration<T> { | |
| return b ? x : next; | |
| } | |
| return cell; | |
| } | |
| /* | |
| * Given a set of values, return a list of those values | |
| */ | |
| function list<T>(...args: T[]): Next<T> { | |
| if(args.length === 0) return null; | |
| return cons<T>(args[0], list.apply(this, args.slice(1, args.length))); | |
| } | |
| /* | |
| * Given a list and a number n, return the nth value from the list | |
| */ | |
| function nth<T>(cell: Next<T>, n: number): Maybe<T> { | |
| if(cell == null) { | |
| if(n === 0) return null; | |
| throw 'Out of bounds'; | |
| } | |
| if(n === 0) return value(cell); | |
| return nth(next(cell), n - 1); | |
| } | |
| /* | |
| * Reverses a list | |
| */ | |
| function reverse<T>(cell: Next<T>): Next<T> { | |
| let curr = cell; | |
| let reversed: Next<T> = null; | |
| while(curr) { | |
| reversed = cons<T>(value(curr), reversed); | |
| curr = next<T>(curr); | |
| } | |
| return reversed; | |
| } | |
| /* | |
| * Let's try it out: | |
| */ | |
| const l = list(1, 2, 3) | |
| console.log(nth(l, 0)); | |
| console.log(nth(l, 1)); | |
| console.log(nth(l, 2)); | |
| const r = reverse(l); | |
| console.log(nth(r, 0)); | |
| console.log(nth(r, 1)); | |
| console.log(nth(r, 2)); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment