4 ms·
The author has provided a type operator for sets (and other datatypes) that let's one compute fixpoints of monotone operations like transitive closure on direct
by tromp 4y ago
The author has provided a type operator for sets (and other datatypes) that let's one compute fixpoints of monotone operations like transitive closure on directed graphs
with a minimum of effort. While the implementation uses unsafe primitives, the resulting interface is safe and pure. Quite impressive and hopepully something I can make use of in the future...
Btw, regarding the introductory example
> fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
I prefer the more straightforward
fibs = f 0 1 where f a b = a : f b (a+b)
- deleted 4y ago[deleted]
- downvotetruth 4y agofib n = head (apply (Matrix [[0,1], [1,1]] ^ n) [0,1]) https://wiki.haskell.org/The_Fibonacci_sequence https://wiki.haskell.org/The_Fibonacci_sequence
- tromp 4y agoThat looks exponentially faster for large n, but with the Fibonacci numbers themselves growing exponentially, the former takes Theta(n^2), while the latter also takes Theta(n^2) for the final squaring of the matrix using naive multiplication and still takes Theta(n^1.58) for multiplication with Karatsuba's algorithm (or still less with the more esoteric methods in [1]). [1] https://en.wikipedia.org/wiki/Multiplication_algorithm https://en.wikipedia.org/wiki/Multiplication_algorithm
- downvotetruth 4y agohttps://en.wikipedia.org/wiki/Exponentiation_by_squaring https://en.wikipedia.org/wiki/Exponentiation_by_squaring https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form Faster Haskell implementations exist as shown on the Haskell page link, but the idea was to show the most straightforward form that is also recursive with an order of magnitude better runtime.
- bibanez 4y agoThis isn't faster unless you diagonalize the matrix. Then you get the closed form for fibonacci