4 ms·

Pure recursively defined sets without looping in Haskell

34 points by romes 4y ago

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 ago
  fib 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 ago
    That 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 ago
      https://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 ago
    This isn't faster unless you diagonalize the matrix. Then you get the closed form for fibonacci
cryptonector 4y ago
The title is wrong, should be `More recursive definitions`. The title simply engages my pedantic self and makes me want to point out that tail recursion == looping and, really, that recursion is looping.
- kadoban 4y ago
  I think of loops as a ~syntactic concept. You could implement loops with recursion, but I wouldn't call manual recursion a loop. Similarly I wouldn't call a manual "goto" a function call, even if one way you'd implement function calls could be with goto.
- chowells 4y ago
  No, the title is correct. It specifically means "without generating <<loop>> output". That's a diagnostic GHC-generated code emits when it discovers that evaluating a thunk requires the result of evaluating that same thunk. The title does use a bit of shorthand, as it's aimed at Haskell developers. And any Haskell dev using GHC with enough experience has run into <<loop>> before. So the title isn't wrong; it's just for a different audience.

34 points by romes 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 ago
fib 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 ago
  That 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 ago
    https://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 ago
  This isn't faster unless you diagonalize the matrix. Then you get the closed form for fibonacci

cryptonector 4y ago

The title is wrong, should be `More recursive definitions`. The title simply engages my pedantic self and makes me want to point out that tail recursion == looping and, really, that recursion is looping.

kadoban 4y ago
I think of loops as a ~syntactic concept. You could implement loops with recursion, but I wouldn't call manual recursion a loop. Similarly I wouldn't call a manual "goto" a function call, even if one way you'd implement function calls could be with goto.
chowells 4y ago
No, the title is correct. It specifically means "without generating <<loop>> output". That's a diagnostic GHC-generated code emits when it discovers that evaluating a thunk requires the result of evaluating that same thunk. The title does use a bit of shorthand, as it's aimed at Haskell developers. And any Haskell dev using GHC with enough experience has run into <<loop>> before. So the title isn't wrong; it's just for a different audience.