Created
July 6, 2022 17:53
-
-
Save suica/61ef1503a4082853a8fe904824dbc513 to your computer and use it in GitHub Desktop.
Problems on infinite stream. 无穷流编程问题。
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 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