Comment by rkts | Hacker News Reader

Comment by rkts | Hacker News Reader

Parent Full thread

Kool-Aid-free answer:

"Functional programming" can mean one of three things.

1. Higher-order programming: the use of higher-order functions to make code more general/compact. Since you know Ruby, you're already doing some higher-order programming, but you may not understand it well enough to take full advantage of it. The best way to learn higher-order programming is to read SICP.

2. The use of immutable (aka persistent, nondestructive) data structures, i.e. data structures that can be updated without mutation. For example, linked lists allow you to prepend an element without changing the original list. This makes code cleaner in some cases and has advantages for concurrency. For specifics, look up Clojure.

3. Functional purity, aka referential transparency: the property that, for any input x, a function must always produce the same output x'. That is, all functions must be functions in the mathematical sense of the word. In practice, this doesn't really mean eliminating impure functions, but rather partitioning your program into "provably pure functions" and "possibly impure functions," using a clever hack (monads) to ensure that the output of possibly-impure functions is invisible to the provably-pure ones.

So, supposing you had a pure function whose behavior you wanted to randomize, you couldn't just throw in a call to the random() function, but would also have to convert it and all the functions that depend on it into impure (monadic) functions, replacing all function calls with the bind operator (>>=). It's quite complicated and I have never found a reason to believe it's a good idea, other than some theoretical stuff about "safety" and compiler optimizations that make your program 2% faster. I suggest not wasting your time on it.

You don't understand monads very well, they are orthogonal to 'impurity', and don't even necessarily involve state or sequencing at all.

A more straightforward way to describe how you do random() is that your function takes the randomness as an argument. Functions that take input take IO as an argument, and those that produce output return IO in some form. You don't even have to mention the dreaded word.

monads... don't even necessarily involve state or sequencing at all

I never said that they do.

You used the word "impurity". What other meaning did you intend?

Consider the getLine function:

  getLine :: IO String

getLine takes nothing as its input--not the state of the world, or whatever, but nothing--and produces a string that's inside an IO monad. To all appearances, it's an impure function. But because the String is inside a box (so to speak) you can't peek at it--instead, you can only give it to another function, provided that function also returns a box you can't peek into.

In effect, this creates two classes of functions. Some, like getLine, can have side effects, generate random values, look into other boxes, whatever. These are technically "pure" in a mathematical sense since their outputs are always inside identical boxes, but in practice they behave just like impure functions, and you reason about them the same way. The rest have more restricted capabilities, and because their values aren't inside boxes, the compiler can verify that they return distinct values in a pure manner.

So, for an extreme example, consider this function:

  foo (x) { x++; return x; }

In Haskell foo would return "IO Int," which means the "Int" may be produced impurely. Actually, the integer is produced in a pure manner, so it would be fine for foo to return a plain Int. But the way Haskell determines purity is too crude to figure that out: all it knows is that foo depends on a mutation, which may make the output impure. Impurity is contagious, so foo "catches" it from ++ and thus has to put its output in a box.

Hence, the typical description of pure functional programming as "functions only transform inputs to outputs" is only true in the most trivial mathematical sense, and has no practical import. Pure functional programming really means writing a crude proof that a certain subset of your program is pure, and the compiler checking the proof for you.

(Disclaimer: I understand that this is a very vague high-level description of monads, that monads can work in other ways and do many other things, and that purely functional languages can handle state/side effects/etc. in other ways. It's a complex issue and I'm just trying to convey the way that it usually works in practice.)

I don't really agree with your treatment of monads, but perhaps I don't understand your point of view.

What did you mean by "you can't peek at it"? I can peek into the String returned by getLine in pure code, as in the following example:

  myStr <- getLine
  let len = length myStr
  print len

Here, myStr is of type String and 'length' is a pure function of type [anything] -> Int. The <- ("gets") syntax unwraps the IO box around the result of getLine (which is of type IO String, as you noted). Once it's unwrapped, we can treat it as a purely functional value and call length on it. Then I can pass it to the 'print' function, which is also in the IO monad. The compiler will ensure that 'length' is pure.

I also don't understand what you mean when you say getLine "takes nothing as its input". Since it's in the IO monad, it implicitly takes the "RealWorld" as its input, updates it, and implicitly returns a new RealWorld. I prefer this treatment of the IO monad, because it's easy to see how _every function_ is pure in Haskell -- it's just a matter of giving it different (implicit or explicit) arguments.

To be fair, the RealWorld analogy is not exactly how the system works. But it is the abstraction that the Haskell language likes to make (from the docs: "RealWorld is deeply magical. It is primitive, but it is not unlifted (hence ptrArg). We never manipulate values of type RealWorld; it's only used in the type system, to parameterise State#.")

Anyway, an example which is actually purely functional but uses mutation:

  import Control.Monad.State.Lazy
  
  incr :: State Int ()
  incr = modify (+1)
  
  add2 :: Int -> Int
  add2 val = execState incrTwice val 
        where
        incrTwice = do
                incr
                incr
  
  main :: IO ()
  main = do
        print (add2 5)

This program prints 7.

The 'incr' function here, like the getLine function, accepts no explicit arguments. However, it is in the State monad, parameterized with an Int, meaning that it implicitly accepts a mutable Int which it can modify. In this case, it adds one to that int, and doesn't return anything (that's the () data type, pronounced "unit").

The 'add2' function here is purely functional: it has type Int -> Int. And yet it depends on mutation occurring because it calls incr (twice). The execState "creates" a State monad from scratch and gives it an initial state (val), and then runs the given State action (incrTwice).

The main difference between the functional State monad and IO (which -- awesomely -- is actually defined in the source code as a State of RealWorld) is that you can't create instances of RealWorld, so you can't execState an IO action. In order to run an IO action, you have to get the RealWorld from the only place it enters your program, the main function.

Did I clarify anything, or did I misunderstand you?

Ok, you're right. That is a better explanation of monads than the one I gave.

I intended my example to represent cases where you want real mutation, in the sense of modifying a data structure in place. Your code using the State monad, if I understand it correctly, just abstracts functional updates in a way that looks like mutation.

Anyway, my intent in my original comment was simply to explain the practical consequences of pure functional programming. That, for instance, if you have a pure function that you want to randomize, this change must be reflected in all the code that depends on it. My intuition is that this is a bad thing, but I don't have enough experience to say for sure. However, it is apparent to me that purity

1. adds a lot of complexity to the language, and

2. has no clear practical benefits,

which is why I say it's a waste of time.

I think you are conflating the IO monad with monads in general. For example a stateful idom like x++ in your foo example could be simulated with a state monad, but that does not have anything to do with IO, and would certainly not require the IO monad as you seem to suggest.

You can encapsulate the use of a state monad so you can indeed return a pure int even if you use a state monad inside the function. It is only the IO monad which (for obvious reasons) cannot be encapsulated. So only the IO monad is "contagious" in the way you describe. This is only a problem for you if you have input and output spread all over your program.

Reply on news.ycombinator.com