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

41–50 of 124 posts

Re: I thought I understood recursion

#41

Post by Hercuros »

roenxi wrote: post #15
gear54rus wrote: post #9

Earlier quoted context omitted.

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…

Maybe you should look within yourself and fix up whatever part of your personality is making you miserable? I'm not being flippant. Programming languages don't make people miserable. There isn't really an argument, just an observation that the most efficient way of thinking about programming is in data structures and algorithms which are mostly language independent. Nobody should be spending most of their time levera…

Programming is in my opinion not just about data structures and algorithms. It is also about designing abstractions that capture the domain you're working in well, whether it be by designing classes in an OOP language, or data types and functions in a functional language.

It's not just about what a program does and how quickly it does it. What matters at least as much is how easy it is to understand, modify and extend. Of course, that isn't necessarily language-dependent either, but I think some languages make it easier for you to design nice abstractions.

For example, C can make it more difficult to write nice abstractions since it forces you to worry about memory allocation and memory safety, and doesn't really offer facilities for generics.

Re: I thought I understood recursion

#42

Post by leibnitz27 »

leibnitz27 wrote: post #37

Sure you can. Here's a super grotty (and expensive) c# version. static IEnumerable infinite() { int x = 2; while (true) { yield return x++; } } static IEnumerable primes(IEnumerable l) { int head = l.First(); yield return head; foreach (var x in primes(l.Skip(1).Where(x => x % head != 0))) yield return x; } static void Main(string[] args) { System.Console.WriteLine(string.Join(",", primes(infinite()).Take(20).Select(…

(and yes, the nested yield is ABSOLUTELY an anti-pattern. They did promise to do a bulk yield at some point, I haven't used C# in a few years so don't know if I'm out of date!)

Re: I thought I understood recursion

#43

Post by cousin_it »

Using functional programming to find primes is tricky:

https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Melissa O'Neill shows that the typical FP sieve has worse big-O complexity than imperative.

https://wiki.haskell.org/Prime_numbers#Sieve_of_Eratosthenes

The Haskell wiki gives several sieve implementations and can't figure out the big-O complexity. (The imperative sieve is O(n log log n).)

Re: I thought I understood recursion

#44

Post by d--b »

C# equivalent:

    IEnumerable filter(int p, IEnumerable xs) {
     foreach(var j in xs)
      if (j % p > 0) yield return j;
    }
    
    IEnumerable sieve(IEnumerable s) {
     var p = s.First();
     yield return p;
     foreach(var e in sieve(filter(p,s.Skip(1))))
      yield return e;
    }
    
    var n = sieve(Enumerable.Range(2, 10000)).Skip(10).First();

Re: I thought I understood recursion

#45

Post by tempestn »

martin1975 wrote: post #21

"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 requiremen…

Or maybe it was just a joke...

Re: I thought I understood recursion

#48

Post by javajosh »

martin1975 wrote: post #21

"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 requiremen…

>You just have to look harder to see where it's being used.

This is where advocacy slips over the line into a kind of blind faith evangelism -- with an added pinch of pedantry peculiar to our field.

I will state without proof that every language ever invented is currently being used for something practical somewhere. E.g. someone has a useful shell utility they wrote in Brainfuck that they run every day and that they love. This does not mean that BF has 'practical application' in the usual sense of the phrase. In the same way, just because there is a real program written in Haskell somewhere does not mean it has practical application.

IMHO a language (or a tool in general) should have a community of practitioners that regularly think in and create with the tool, and a good signal that that is happening are the number of open-source releases in that language. I have never in my life installed a Haskell program, or known of anyone installing one. (The exception being this one Haskell fan at JPL who loved talking about the language and the lambda calculas, but to my knowledge, never wrote anything real in it, and he just installed learning toys, not utilities.)

All that said, there are some good examples of unpopular tools that enjoyed success later in life. Quaternions lost to vectors historically, but graphics programmers rediscovered their benefits and resurrected them. Maybe Haskell will have it's time, but that time is not now.

Re: I thought I understood recursion

#49

Post by [deleted] »

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…

[deleted]

Re: I thought I understood recursion

#50

Post by orange8 »

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…

"Love is understanding.." MLK

"People fear what they don't understand and hate what they can't conquer." Andrew Smith

Post reply on HN