Skip to content

Instantly share code, notes, and snippets.

@suica

suica/infinite-stream-problems.ts

Created July 6, 2022 17:53
Show Gist options
  • Save suica/61ef1503a4082853a8fe904824dbc513 to your computer and use it in GitHub Desktop.
Save suica/61ef1503a4082853a8fe904824dbc513 to your computer and use it in GitHub Desktop.
Download ZIP
Problems on infinite stream. 无穷流编程问题。
Raw
infinite-stream-problems.ts
type List<T> = null | {
head(): T;
tail(): List<T>;
};
type Stream<T> = {
head(): T;
tail(): Stream<T>;
};
const constant = (value: number): Stream<number> => {
const self = {
head() {
return value;
},
tail() {
return self;
},
};
return self;
};
const map = <T, U>(stream: Stream<T>, f: (a: T) => U): Stream<U> => {
const self = {
head() {
return f(stream.head());
},
tail() {
return map(stream.tail(), f);
},
};
return self;
};
const takeUntil = <T, U>(
s: Stream<T>,
shouldTruncateHere: (x: T) => boolean
): List<T> => {
if (shouldTruncateHere(s.head())) {
return null;
}
const self = {
head() {
return s.head();
},
tail() {
return takeUntil(s.tail(), shouldTruncateHere);
},
};
return self;
};
const listToArray = <T>(list: List<T>): T[] => {
if (list) {
return [list.head(), ...listToArray(list.tail())];
}
return [];
};
// let index = 0;
// const list = takeUntil(constant(0), (x) => {
// return ++index >= 10;
// });
// console.log(listToArray(list));
const count = (start: number, step = 1): Stream<number> => {
return {
head() {
return start;
},
tail() {
return count(start + step, step);
},
};
};
// const list = takeUntil(count(0), (x) => {
// return x >= 9;
// });
// console.log(listToArray(list));
const mergeBy = <T, U, K>(
a: Stream<T>,
b: Stream<U>,
f: (a: T, b: U) => K
): Stream<K> => {
return {
head() {
return f(a.head(), b.head());
},
tail() {
return mergeBy(a.tail(), b.tail(), f);
},
};
};
const fib = (
pre: Stream<number> = constant(1),
prepre: Stream<number> = constant(-1)
): Stream<number> => {
const self = {
head() {
return pre.head() + prepre.head();
},
tail() {
return fib(self, pre);
},
};
return self;
};
const printList = <T>(list: List<T>): List<T> => {
console.log(listToArray(list));
return list;
};
const list = takeUntil(fib(), (x) => x >= 200);
printList(list);
const filter = <T>(s: Stream<T>, predicate: (x: T) => boolean): Stream<T> => {
const self = {
head() {
return s.head();
},
tail() {
return filter(s.tail(), predicate);
},
};
if (predicate(s.head())) {
return self;
}
return self.tail();
};
const prime = (assumedPrime = 2): Stream<number> => {
const self = {
head() {
return assumedPrime;
},
tail() {
return filter(prime(assumedPrime + 1), (x) => x % assumedPrime !== 0);
},
};
return self;
};
// const list = takeUntil(prime(), (x) => x >= 200);
// printList(list);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment