Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

I thought I understood recursion

functional.christmas

Post reply on HN
Print view View original

21–30 of 124 posts

Re: I thought I understood recursion

#21

Post by martin1975 »

"It is rather an attempt to get my head around functional programming, and to me Haskell doesn’t seem to have any practical application beyond that."

Cardano/ADA's core Ouroboros protocol was entirely written, with formal proofs, in Haskell. It is by far the most serious attempt at proof of stake in the crypto industry.

I think what you're really saying is, you won't find many jobs out there w/Haskell as a requirement... but I wouldn't go as far as saying Haskell has no purpose past teaching FP. It certainly is the poster child of FP, however it is not without practical/industrial use. You just have to look harder to see where it's being used.

Re: I thought I understood recursion

#22

Post by merijnv »

cjfd wrote: post #18
millstone wrote: post #8

Ooh, what's the time and space complexity of `primes`?

Clearly much worse than the original solution. Basically, a nested sequence of filters is built, one to filter out multiples of each prime number. One way in which the complexity of this is bad is that if you want prime numbers These kind of functional solutions are very cute mathematically, but... I once wrote this way of generating an infinite list of primes in unlambda. That was kind of interesting to do.

> One way in which the complexity of this is bad is that if you want prime numbers That's not really true, though, because that filter is applied lazily, so it only get evaluated up until the Nth prime and no further.

Re: I thought I understood recursion

#23

Post by cjfd »

merijnv wrote: post #19
millstone wrote: post #8

Ooh, what's the time and space complexity of `primes`?

I'd say O(n) for both. The generated list only contains primes, so that's straightforward linear. Then there is the recursive sieving, which adds an additional pass over the sieve list for every prime we've found so far, we need keep the computation of each pass in memory, so that's some additional memory that's also linear. The time complexity is less obvious, each prime adds an additional pass to evaluate, so that…

clearly O(n^2) for time. Well, perhaps O(n^2/log n) or something, but that is not much different. The thing is, every prime p gets passed through a filter that filters multiples of primes p' for all p' < p.

Re: I thought I understood recursion

#24

Post by hans1729 »

im3w1l wrote: post #10
baq wrote: post #7

> My background is in OO programming, mostly using C#. C# being the versatile language it is, I have had the perception that whatever you do in other programming languages, you can with a little more code and hassle achieve in C# as well. If need be, I can program C# using a functional paradigm. And, of course I use recursion all the time. I know all there is to know about recursion. IME there are two kinds of progra…

It's not obvious to me why choosing the right tool for the job is better than choosing the right job for the tool.

Don't know if you're serious, but for the most devs, the job is chosen for, not by, you

Re: I thought I understood recursion

#25

Post by pintxo »

im3w1l wrote: post #10
baq wrote: post #7

> My background is in OO programming, mostly using C#. C# being the versatile language it is, I have had the perception that whatever you do in other programming languages, you can with a little more code and hassle achieve in C# as well. If need be, I can program C# using a functional paradigm. And, of course I use recursion all the time. I know all there is to know about recursion. IME there are two kinds of progra…

It's not obvious to me why choosing the right tool for the job is better than choosing the right job for the tool.

Might it be easier to switch tools than jobs for most people?

Re: I thought I understood recursion

#26

Post by martin1975 »

cjfd wrote: post #11

To understand recursion you must first understand recursion.

The first rule of recursion is we do not talk about recursion.

The second rule of recursion is we do not talk about recursion.

The third rule of recursion is without a base case, you have no recursion.

The fourth rule of recursion is it breaks you in two or more pieces.

Re: I thought I understood recursion

#27

Post by tonyedgecombe »

gear54rus wrote: post #9
baq wrote: post #7

> My background is in OO programming, mostly using C#. C# being the versatile language it is, I have had the perception that whatever you do in other programming languages, you can with a little more code and hassle achieve in C# as well. If need be, I can program C# using a functional paradigm. And, of course I use recursion all the time. I know all there is to know about recursion. IME there are two kinds of progra…

So if you consider some stack to be inferior (maybe because its highly inconsistent in its design or it only runs on closed and locked down platforms or whatever) you still should just dismiss it as 'oh its just a tool' instead of accepting that it's shitty and makes you miserable when working with it? Why wouldn't I want to work with best thing ever if it helps me keep my sanity every day? Do you want to use somethi…

The things that make work pleasant are a sense of purpose, feeling valued, being stretched, having autonomy, personable colleagues, a good physical environment, decent equipment. These are far more important than what language you happen to be using.

Re: I thought I understood recursion

#30

Post by BerislavLopac »

martin1975 wrote: post #26
cjfd wrote: post #11

To understand recursion you must first understand recursion.

The first rule of recursion is we do not talk about recursion. The second rule of recursion is we do not talk about recursion. The third rule of recursion is without a base case, you have no recursion. The fourth rule of recursion is it breaks you in two or more pieces.

The fifth rule of recursion is that it is not really recursion if it isn't tail-call optimised.
Post reply on HN