3 ms·

Hilbert’s Rusty Hotel

43 points by LegitGandalf 7y ago

Arnavion 7y ago
While the solution is composed neatly from functional primitives, the large amount of boxes of boxes are not ideal. For example, Interleave stores a Vec<Box<Iterator>>, which it absolutely should for the general case. But Flatten only ever uses it with two iterators, so the Vec is an extra allocation that could've been avoided in Flatten's case. For the specific case of flattening an infinite iterator of infinite iterators, once could simplify to: struct FlattenInfinite where I: IntoIterator, ::Item: IntoIterator { iters: ::IntoIter, realized_iters: Vec<<I::Item as IntoIterator>::IntoIter>, cursor: usize, } where the number of trailing ones in self.cursor specifies which iterator to yield the next element from. Full example at https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=b2c807cc5537fa2915fe11855bf44373 https://play.rust-lang.org/?version=stable&mode=release&edit... The `.expect()`s require that the solution is specific to an infinite iterator of infinite iterators. (Edit: Better implementation that uses usize::trailing_zeros() instead of hand-counting trailing ones.)
tom_mellior 7y ago
For whatever it's worth, here's how you would actually implement the reflexive-transitive closure of a relation in Prolog: subtype(gerbil, rodent). subtype(rodent, mammal). subtype(mammal, animal). transitive_subtype(S, T) :- subtype(S, T). transitive_subtype(S, T) :- subtype(S, U), transitive_subtype(U, T). reflexive_transitive_subtype(T, T). % FIXME: should check if T is a type reflexive_transitive_subtype(S, T) :- transitive_subtype(S, T). This terminates as expected: ?- transitive_subtype(gerbil, X). X = rodent ; X = mammal ; X = animal ; false. % meaning "I have proved that there are no further solutions" ?- reflexive_transitive_subtype(gerbil, X). X = gerbil ; X = rodent ; X = mammal ; X = animal ; false. or even: ?- reflexive_transitive_subtype(S, T). S = T ; S = gerbil, T = rodent ; S = rodent, T = mammal ; S = mammal, T = animal ; S = gerbil, T = mammal ; S = gerbil, T = animal ; S = rodent, T = animal ; false. Left recursion can indeed be a problem in Prolog, but this is not a problematic case.

43 points by LegitGandalf 7y ago

While the solution is composed neatly from functional primitives, the large amount of boxes of boxes are not ideal. For example, Interleave stores a Vec<Box<Iterator>>, which it absolutely should for the general case. But Flatten only ever uses it with two iterators, so the Vec is an extra allocation that could've been avoided in Flatten's case. For the specific case of flattening an infinite iterator of infinite iterators, once could simplify to: struct FlattenInfinite where I: IntoIterator, ::Item: IntoIterator { iters: ::IntoIter, realized_iters: Vec<<I::Item as IntoIterator>::IntoIter>, cursor: usize, } where the number of trailing ones in self.cursor specifies which iterator to yield the next element from. Full example at https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=b2c807cc5537fa2915fe11855bf44373 https://play.rust-lang.org/?version=stable&mode=release&edit... The `.expect()`s require that the solution is specific to an infinite iterator of infinite iterators. (Edit: Better implementation that uses usize::trailing_zeros() instead of hand-counting trailing ones.)

tom_mellior 7y ago

For whatever it's worth, here's how you would actually implement the reflexive-transitive closure of a relation in Prolog: subtype(gerbil, rodent). subtype(rodent, mammal). subtype(mammal, animal). transitive_subtype(S, T) :- subtype(S, T). transitive_subtype(S, T) :- subtype(S, U), transitive_subtype(U, T). reflexive_transitive_subtype(T, T). % FIXME: should check if T is a type reflexive_transitive_subtype(S, T) :- transitive_subtype(S, T). This terminates as expected: ?- transitive_subtype(gerbil, X). X = rodent ; X = mammal ; X = animal ; false. % meaning "I have proved that there are no further solutions" ?- reflexive_transitive_subtype(gerbil, X). X = gerbil ; X = rodent ; X = mammal ; X = animal ; false. or even: ?- reflexive_transitive_subtype(S, T). S = T ; S = gerbil, T = rodent ; S = rodent, T = mammal ; S = mammal, T = animal ; S = gerbil, T = mammal ; S = gerbil, T = animal ; S = rodent, T = animal ; false. Left recursion can indeed be a problem in Prolog, but this is not a problematic case.