Why are there no loops in FP?

Recursion is looping. Some iterative loops can be expressed recursively - these are the ones that can be tail call optimized. SICP has a good explanation:

https://mitpress.mit.edu/sicp/full-text/sicp/book/node15.htm...

The advantage of using recursive definitions for loops is that it avoids modifying places in favor of returning values. Rich Hickey gives a good talk on the subject in The Value of Values:

http://www.infoq.com/presentations/Value-Values

Would you expect to see a for loop in a mathematical equation? You're correct in noticing that a lot of the reasons why you'd use a for loop are taken care of with basic functions such as map (to perform some action on different elements in a list), reduce (to do some sort of aggregation).

So you kinda just don't need for loops anymore and they're inherently imperative because you need to setup some sort of condition to say keep performing this sequence of actions (which is the main idea behind imperative programming) until this condition is no longer satisfied.

You can use forM. As for why for loops are imperative or if they are... Not sure. A few thoughts come to mind:

For loops dont return a value, whereas forM and even forM_ both return values. They are normal functions rather than just control structures.

Also, if you can post some code examples where you "feel you are missing something" I (or others) might be able to provide the functional examples.

So, it's not like loops are an inherently imperative idea, so much as that they typically are something that only make obvious sense in an imperative world.

Let's start with a simple function that counts down from five in Javascript:

    var countDownFromFive = function() {
        console.log(5);
        console.log(4);
        console.log(3);
        console.log(2);
        console.log(1);
        console.log(0);
    }

So, that's the purely imperative way of doing things. We notice a pattern, though: the numbers are just a list from [5,4,3,2,1,0]. So, we could just describe them as the series S(n) = n + S(n-1), where n >= 0. So, we write it in that form:

    var countDownFrom = function(num) {
        console.log( num );
        if (num >= 0) {
            countDownFrom(num - 1);
        }
    }

And then our count down from five becomes:

    var countDownFromFive = function() {
        countDownFrom(5);
    }

So, that's great, and that's a nice recursive definition of the problem. The problem is, though, that for a really big number, say 2^32, we've got to store a stack of results, and that blows everything up. We can fix this with tail call optimization, because we know we can reuse the same stack frames, but that's an optimization many low-level languages don't have.

Indeed, until we've invented them, we don't even have the necessary concepts of a stack with function frames. So, let's look at our problem again.

Let's pretend we're in a very limited assembly language, with just registers:

    LOAD registerA 5
    PRINT registerA
    LOAD registerA 4
    PRINT registerA
    LOAD registerA 3
    PRINT registerA
    LOAD registerA 2
    PRINT registerA
    LOAD registerA 1
    PRINT registerA
    LOAD registerA 0
    PRINT registerA

So, that mirrors our pure imperative case. Aha, but let's say we're smarter than that, and we have a branch instruction and a decrement operator:

    start:
        LOAD registerA 5
    doPrint:
        PRINT registerA
        DECREMENT registerA
        JUMP_IF_NOT_NEGATIVE registerA doPrint
    finish:
        HALT

So, even without the notion of a function stack, we can still print a list of numbers. We are now experts at counting down from five.

~

The thing we see, though, is that the difference in implementation comes from basically whether or not you can compose functions: if you can, you use the functional approach. If you can't, you refactor the problem to have an explicit accumulator (your loop variable).

Loops can be considered an inherently imperative idea because you have this changing context wrapping the function being invoked (a mutating accumulator, if you will)--in the functional world, you merely wrap another function which itself creates a new context with the desired mutation, and that function in turn calls another function setting up its own context and so on and so forth. It's somewhat handier to prove correctness and behavior of these recursive functions compared with their mutating accumulator imperative solutions; at the same time, they are slower without compiler support.

Checkout the clojure loop form.

It's not necessarily that the two concepts never shall meet; Racket, Heresy, and F# all contain for loops, but there are crucial differences in how the former two handle them vs. how for loops are usually used in other languages.

In most languages, the usefulness of for loops is almost entirely contingent upon either mutability (in the form of some accumulating variable and/or explicit alteration of program state) or on side effects like I/O routines. Partly, these things are often only necessary because the language itself doesn't handle recursion well; why use a for loop to generate a factorial, for example, when I can simply call the function again?

However, you can get something an awful lot like a traditional for loop, while still staying relatively functional pure: in Racket and Heresy, for loops are actually just some familiar syntax sugar layered on top of what's actually a recursive function. They actually become an abstraction over a very common pattern in Lisp languages: the let loop.

In Racket, often times I still need to accumulate some value over successive computations, but I don't necessarily need to build a whole named function to do it. In those scenarios I can make a let loop, which looks like this:

  (let foo ([var 0]
            [l '()])
    (if (> var 10)
      l
      (foo (+ 1 var) (cons var l))))

If that looks a lot like a for loop, well, that's because it basically is! It's just the recursive, functional method of writing a similar pattern. Rather than having to rewrite that pattern over and over again in our code, Racket provides a whole range of built-in for loop styles, so that the same pattern can more simply be written:

  (for/list ([x (in-range 10)])
    x)

Underneath, it's still the same functional code (well, with a lot of other toys to allow things like breaking on a condition, skipping entries, etc.). Heresy goes a step further towards simplifying the huge breadth of specialized for/functions that Racket uses, allowing you to write a for loop in a functional style while explicitly defining your carrying values. So you can write stuff like this:

  (for (x in (range 1 to 10) with '()) 
    (carry (join x cry)))

Which seems more complicated, except that you can use that 'with' keyword to define any starting point for the 'cry' variable you like, meaning you can easily write all manner of different patterns with the same basic syntax.

There are of course complications with this; the functional for loop is great in dynamically typed languages but it can be tricky to correctly type-check, which is why in Haskell it's a monad-y thing, and in Typed Racket there's a number of bugs still being worked out for handling the for loops.

Still, the two aren't necessarily mortal enemies, or explicitly imperative or functional, it just takes some thinking about what you wish to do.