[HN Gopher] Pure recursively defined sets without looping in Has...
       ___________________________________________________________________
        
       Pure recursively defined sets without looping in Haskell
        
       Author : romes
       Score  : 25 points
       Date   : 2022-09-08 14:19 UTC (8 hours ago)
        
 (HTM) web link (www.joachim-breitner.de)
 (TXT) w3m dump (www.joachim-breitner.de)
        
       | tromp wrote:
       | 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]
        
         | downvotetruth wrote:
         | fib n = head (apply (Matrix [[0,1], [1,1]] ^ n) [0,1])
         | 
         | https://wiki.haskell.org/The_Fibonacci_sequence
        
           | tromp wrote:
           | 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 wrote:
             | 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.
        
       | cryptonector wrote:
       | 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 wrote:
         | 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 wrote:
         | 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.
        
       ___________________________________________________________________
       (page generated 2022-09-08 23:02 UTC)