3 ms·
As simple as possible but no simpler – Damian Conway
- triska 7y agoVery interesting, thank you for sharing this! To describe sequences, I often use grammar formalisms such as definite clause grammars (DCGs) that are provided by the logic programming language Prolog. For example, here is a Prolog definition of van Eck's sequence that is discussed in the article: n_van_eck(0) --> []. n_van_eck(N0) --> { N0 #> 0, N #= N0 - 1, empty_assoc(E) }, remainder(N, 0, t([],E,0)). remainder(0, Current, _) --> [Current]. remainder(N0, Current, t(Ls,A0,I0)) --> { N0 #> 0, N #= N0 - 1, I #= I0 + 1 }, [Current], { distance_to_current(Current, A0, I0, Distance), put_assoc(Current, A0, I0, A) }, remainder(N, Distance, t([Current|Ls],A,I)). distance_to_current(Current, A, I, Distance) :- ( get_assoc(Current, A, I0) -> Distance #= I - I0 ; Distance = 0 ). Sample query and answer: ?- phrase(n_van_eck(12), Ls). Ls = [0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5] ; false. The first 100 000 elements are computed within one second: ?- time(phrase(n_van_eck(100_000), _)). % 5,571,815 inferences, 0.739 CPU in 0.748 seconds (99% CPU, 7542128 Lips) true ; % 4 inferences, 0.000 CPU in 0.000 seconds (96% CPU, 23256 Lips) false. And 1 000 000 elements take about 10 seconds: ?- time(phrase(n_van_eck(1_000_000), _)). % 65,636,238 inferences, 9.135 CPU in 9.303 seconds (98% CPU, 7185063 Lips) true ; % 4 inferences, 0.000 CPU in 0.000 seconds (80% CPU, 173913 Lips) false. This seems comparable to the Perl 6 performance results that are reported in the article.