Hacker News Reader

Hacker News

Comment by choeger | Hacker News Reader

Parent Full thread

choeger

Because functional programming is so damned hard if you don't grasp recursion. Otherwise, it is simple.

Sorry for the cheap pun, but I think the main difficulty is getting along with recursion.

And corecursion, of course ;).

View on HN

I disagree entirely.

I understand recursion just fine. I can look at a problem and think "this problem space is correctly represented by a tree/graph" and can meaningfully translate that into a program that shoves the data into a tree/graph-like data structure, and my natural inclination when computing on a tree/graph-like data structure is to use recursion.

On the other hand, I understand that not all problems lend themselves to recursive solutions. I can look at a problem and think "this problem space is correctly represented by a matrix" and the reality is that linear algebra problems are often iterative, not recursive, in nature. It is certainly possible to do the simplex algorithm recursively with immutable data, but it's just so much straightforward to do it iteratively on a mutable matrix.

The other thing is that most of my day job is just hooking one API up to another API to achieve my business's desired outcome. I don't need "interesting" algorithmic solutions for 95% of what I do. I just... extract data from one API and plug the data into another. You don't need recursion for that, and the "list of steps to do in order and (possibly) loop over that" paradigm with whichever seasonings you wish to add to it is just fine. (OOP is the flavor of the ~~day~~century at my company)

edit: I forgot the bit that ties it all together. I am absolutely no good at functional programming. I've tried to sit down and learn Haskell or Lisp a dozen times and always failed. I've bought books. I'm still no good. It just takes me ten times as much code that's completely unreadable to do something that would be simple and straightforward in C++.

I also think that most people who learn a functional language try to take what they know in an imperative language and translate it on the fly to a functional paradigm.

This seems like a lot more work than just learning how to think functionally.

The intro to programming course for the math department at my University was taught in Haskell. And it was really interesting to see how people who had never programmed before on the whole did better than those who had a bit of programming experience.

Those that had programmed before kept trying to make Haskell behave how they thought a programming language 'should' behave, while those who had never programmed just looked at Haskell and went "I guess this is what programming is" and just rolled with it.

The only problem was that once they moved onto the intermediate course, taught in Java, they where completely lost again.

Introduction to Programming at CMU is done in SML. They make the same observations as you. Those that have prior exposure to programming struggle. Those students without experience find it easy. They are a bit baffled in the next course, which is done in an imperative language.

15-150 (during my time), but it wasn’t the intro to programming - the course is titled “introduction to functional programming”. The intro to programming is Python (unless it changed).

The trajectory for students is Python to C to SML (15-110 to 15-122 to 15-150). Some people take the C and SML courses in the same semester.

I was really happy to have been introduced to many different paradigms over the course of a few years. But to both your points, once we moved on to Java I had a really bad time.

Alternatively, learning a new thing is easier if you have a grounding somewhere. Maybe the ideal would be a guide like "this is how functional programming differe from imperative programming"

> I think the main difficulty is getting along with recursion

meh, recursion is easy. Recursion is mainstream. It _began_ as a way to fake a loop without mutation, but I struggle now to remember a mainstream language without it.

The hardest part is all the new patterns you have to grok, it's like learning programming again from a blank slate, because it kinda is. It doesn't get any easier when Haskell decides it needs 7 new syntaxes and someone rushes to compose them all in one line.

I think recursion is just one of the hurdles.

Another one is the use of higher-level functions and function composition.

Another one is the use of monads (at least in pure functional languages like Haskell).

Monads aren't really related to purity. Haskell uses one instance of a monad, the IO monad to encapsulate IO. But there are other ways of doing it. Most monads have nothing to do with side effects.

You see things like functors/monads all the time even in regular imperative languages. For example in .NET we have Linq, Nullable types, etc... They aren't as well defined as in Haskell but still an incredibly useful pattern.

You also have higher ordered functions and whatnot in imperative languages now. In fact, in JavaScript and .NET they are used all over the place.

I don’t believe .NET’s `System.Nullable<T>` is a monad. For example, a type that can encapsulate any other type fulfils the definition of a monadic-value, but `Nullable<T>` cannot be used with reference-types and delegates, only a strict subset of value-types (as `Nullable<T>` itself is a value-type, but you cannot use `Nullable<T2>` for T1 in `Nullable<T1>`).

While .NET allows for composition with delegates, it’s not very smart, and results in unnecessary type information erasure; for example in Linq if you take a projection of a fixed-size list, then that length information is lost if you then add another step after the projection. (Linq internally has some ugly, but inconsistent implementation hacks; for example, IList<T> length information may be preserved but IReadOnlyCollection<T> length information will not.

C# has nullable reference types now. But I agree it's not perfectly a monad in implementation due to engineering decisions. But the pattern generally follows that of the Option monad in Haskell, even if it falls short. If you know the Option monad you'll find it really easy to pick up .NET's nullable types.

That's my point, you find these patterns all over in common programming languages and even though they are hard to learn it's worth it.

It's going the other way that's the problem. I understand .net nullable, including some of the weird edge cases and trivia. None of that seems to provide any illumination into the working of more general monads.

That's because Nullable<T> and nullable-reference-types aren't monads - precisely because they aren't composable.

I think this SO post covers it well: https://stackoverflow.com/questions/44965/what-is-a-monad

Weird, when I was learning Haskell I felt like the Option type looked very familiar. Then when I learned about fmap and bind it was immediately obvious why these would be useful. You mean I can apply a function to a nullable type that has no knolwedge of nullable? Cool! Or I can compose general operations on nullables? That is neat.

In fact I think this was the easiest way for me to learn monads - to learn them in the context of things I already understood.

All essential applications of monads in Haskell are there to work around the limitations of purity. The I/O monad, ST monad, State monad, etc.

Yes, I know List and Maybe are also technically monads in Haskell. But you don't need to think of them as monads or even understand monads to do anything useful with them. Applying monad operators to lists and maybes is only occasionally useful.

In most impure functional languages (LISP, ML) you rarely model any data types as monads explicitly. As soon as you have side-effects, they lose their appeal.

This is just not true, you throw out some of the most useful monads :)

Also ST and State have no side effects. The only monad in Haskell that has side effects is IO (unless you were to sneak in an unsafePerformIO but that is an entirely different discussion). So they aren't there to work around the limitations of purity, because they are pure.

> This is just not true, you throw out some of the most useful monads :)

Namely?

> Also ST and State have no side effects.

I didn't say they do. I said they are useful only because Haskell doesn't allow side-effects. In ML or Lisp you'd just update a local variable instead.

Lists, Option, Either, Reader, Logging (non-effectful), STM etc... There is even a probability monad that I have found quite useful.

ST & State are far more useful than updating a local variable. If you are going to choose the simplest use case for them ever and then say that is the only thing they can do it is not a productive discussion. The state monad is a lot like a context object that allows state to flow through function composition (for functions that have no knowledge of such state). For example you could compose a bunch of functions and have the results of each function call stored without changing any of the functions to know about the operation. It's a method of abstraction and encapsulation.

It's not just monads that are useful either, it is the full hierarchy of Monoids, functors, applicatives, monads, etc...

recursion is always synonymous to me of unbounded memory usage. Understanding the memory consumption of a for loop updating a local variable looks easy. But a recursive function ? forget it...

They can be made to work very much the same with the compiler. The main difference is tail recursive or not. Basically whether the answer is being accumulated along the way or requires returns from the call stack to accumulate the result.

Otherwise there’s no law of computer science making the two very different. Some language compilers implement recursion naively, that’s mostly it.

The call stack itself is literally just a stack provided by the OS with restrictions meant to protect the other programs in the os.

Yes. Fundamentally, the problem is cultural, not mathematical. A modern language like Racket with proper recursion optimizations will compile and optimize a recursive solution that is as fast or nearly (and even sometimes faster) than a mutable imperative one.

The problem is that the idea of recursion as slow or resource hungry has become a kind of circular just-so story among imperative programmers and compiler developers who don't want to write recursion optimizations (or don't even know how).

The argument goes that recursion is slow, so don't use recursion, and if you raise the idea of optimizing recursion, the compiler dev dismisses it, because why would you write recursion support, recursion is slow.

Now it's fair to say in an earlier era, this was somewhat justifiable, but the logic has been passed down far longer than it's actually been true of the technology available. I remember reading "recursion bad" in C books in the 90s, and it's still so pervasive that even though TCO has been in the JS standard since ES6 years ago, most browsers still can't be bothered to support it.

Well that's why you want a function to be tail recursive, right?

yeah but how do i know for sure that the compiler is going to optimize the memory or not ? Some compilers are smarter than other to rewrite recursion in a tail recursive way, and others aren't, and it's probably not possible all the time anyway..

It seems like a very convoluted way to do a simple thing ( sometimes).

In Scala, as I recall, you could annotate a method as tail recursive so it wouldn't build if it weren't. A serious functional language pretty much has to have an answer for this since you're supposed to use recursion instead of iteration.

Scala has the '@tailrec' annotation for this, and OCaml has the '[@@tailcall]' attribute for the same reason.

A tail recursive function can always be optimised into code which does not consume memory on recursion, and it’s a pretty basic fact to learn about a given language/implementation.

my question was more about cases where the tail recursive version isn't possible, or even worst when the code isn't written in a tail recursive way but you expect the compiler to rewrite it to the tail recursive version.

the fact that FP works over a model of computation (aka an abstraction over the underlying hardware limits) makes it a bit harder to visualize its behavior in the bounded real-world environment ( imho ).

The more i progress the more i want to develop with "visible wires", and reduce the amount of abstraction to its most basic components..

I suspect you think about recursion in terms of a call stack, yes? So when you have tail recursion, you're still pushing a frame onto the stack by default, unless the compiler recognizes that it can optimize that way. Yes?

The traditional FP model of computation doesn't have a call stack. It proceeds by reduction: replace one subexpression with another, in the program text itself, and repeat until you can't do it anymore.

So if I've got a fibonacci function in two clauses, `fib 0 a b = b` and `fib n a b = fib (n - 1) b (a + b)`, then a reduction may look like this:

      fib 3 0 1         -- initial program
    = fib 2 1 (0 + 1)   -- substitute second clause of `fib`
    = fib 2 1 1         -- evaluate `+`
    = fib 1 1 (1 + 1)
    = fib 1 1 2
    = fib 0 2 (1 + 2)
    = fib 0 2 3
    = 3                 -- substitute first clause of `fib`

Notice how the tail-recursion naturally falls out of the substitution steps performed by the interpreter. There are no stack frames; the whole "rest of the program" (which is what a call stack is) is just the program itself.

This isn't just an analogy; this is the way computation works in an FP. To an FP system, the call stack is the invisible, behind-the-scenes optimization.

Functional languages will typically guarantee you that tail recursion is constant space. The exception is languages running on a FP adverse runtime such as the jvm, and they tend to provide a special keyword and rewrite into a loop.

Also, mutual recursion is a bit more general than loops :)

Mutual single recursion is still a loop; you just pick where you want to cut the cyclic dependencies to return to the top. In the worst case, you can put a `switch` in the loop and track what state you're in, although that's gross (you have to keep the union of all variables that might be used in each state).

Multiple recursion, like in `fib n = fib (n - 1) + fib (n - 2)`, is more general than loops... in a world without higher-order functions. You can make such a function tail-recursive by doing the continuation-passing transform, which basically just makes the stack explicit. (You'd then want to "defunctionalize the continuation" [0] to clean up.)

(I've actually done this in Java! Writing the multiply-recursive solution is sometimes a lot easier to do (and verify); transforming it into an iterative solution mechanically exposes a lot more hidden details, but you still have your recursive solution you can test and compare against.)

[0] http://www.pathsensitive.com/2019/07/the-best-refactoring-yo...

How is this not equally applicable to "constructing an object"?

it's pretty rare to have the size of an objet in memory be proportional to the number of times one of its method is called. It's usually proportional to the amount of "data" it stores.

In the case of recursion, the "time" of computation may have a direct consequence, in itself, on the occupied memory (in the case of non-tail optimized calls)

just do a "pure object procedural" style of functional...

all "objects" are immutable (or by value), as are the functions arguments and return values.

But within a function you can still use variables and for loops.

Reply on news.ycombinator.com