Pure recursively defined sets without looping in Haskell

[romes]

https://www.joachim-breitner.de/blog/792-More_recursive_definitions

[tromp]

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)

[downvotetruth → tromp]

  fib n = head (apply (Matrix [[0,1], [1,1]] ^ n) [0,1])

https://wiki.haskell.org/The_Fibonacci_sequence

[tromp → downvotetruth]

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

[downvotetruth → tromp]

https://en.wikipedia.org/wiki/Exponentiation_by_squaring

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 → downvotetruth]

This isn't faster unless you diagonalize the matrix. Then you get the closed form for fibonacci

[cryptonector]

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.

[chowells → cryptonector]

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.

[kadoban → cryptonector]

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.