Why pure functional programming is more difficult than imperative programming.

In this article, the author asks why functional programming isn't more widespread.

I am using functional programming, but in imperative languages. I do not use pure functional programming, because it makes my life more difficult than it ought to be.

The following examples demonstrate clearly my position (in pseudo Java-syntax, to maximize readability).

1) in immutable code, you cannot have mutual pointers. A fine example is parent-child pointers in trees. In imperative languages, it is very simple:

class Node {
    Node parent;
    List<Node> children;
    int data;
}

void addChild(Node child) {
    child.parent = this;
    children.add(child);
}

void printTree(Node node) {
    print(node.data);
    for(Node child : node.children) {
        printTree(child);
    }
}

In pure languages, one has to keep the parent-child relationships in a secondary structure, which is recreated each time it is altered:

class Node {
    int data;
}

class Tree {
    HashMap<Node, Node> parent_to_child;
    HashMap<Node, Node> child_to_parent;
}

Tree addChild(Node parent, Node child) {
    return new Tree(
       parent_to_child.add(parent, child),
       child_to_parent.add(child, parent));
}

void printTree(Tree tree, Node node) {
    print(node.data);
    tree.parent_to_children.filter(node, void (Node child) {
        printTree(child);
    });
}

2) in pure languages, global context must passed around and copied according to what part is changed. For example, in a simple game, the imperative code is:

int score = 0;

Sprite player, playerBullet;

List<Sprite> enemies;

void updatePlayerBullet() {

    for(Sprite enemy : enemies) {

        if (collision(enemy, playerBullet)) {

            enemies.remove(enemy);

            score += 100;

            return;

        }

    }

}

In pure code, the above becomes more complex; the whole game structure must be passed to functions and copied accordingly:

class Game {

    int score = 0;

    Sprite player, playerBullet;

    List<Sprite> enemies;

}

Game updatePlayerBullet(Game game) {

    return updatePlayerBullet(game, head(enemies), tail(enemies));

}

Game updatePlayerBullet(Game game, Sprite enemy, List<Sprite> enemies) {

    if (enemy == null)

        return game;

    else if (collision(enemy, game.playerBullet))

        return new Game(

            score + 100, 

            game.player, 

            game.playerBullet, 

            remove(game.enemies, enemy));

    else

       return updatePlayerBullet(

           game, 

           head(enemies), 

           tail(enemies));

}
 
3) now, let's try to combine the above. Suppose that enemies are trees of sprites, allowing us to destroy part of an enemy with a bullet. The imperative code is straightforward:

class SpriteTree {

    Sprite sprite; 

    SpriteTree parent;

    List<SpriteTree> children;

}

int score = 0;

Sprite player, playerBullet;

List<SpriteTree> enemies;

void updatePlayerBullet() {

    for(SpriteTree enemy : enemies) {

        SpriteTree target = collision(enemy, playerBullet); 

        if (target != null) {

            if (target.parent == null)

                enemies.remove(target);

            else

                target.parent.children.remove(target);

            score += 100;

            return;

        }

    }

}

SpriteTree collision(SpriteTree enemy, Sprite playerBullet) {

    for(SpriteTree child : enemy.children) {

        SpriteTree result = collision(child, playerBullet);

        if (result) return result;

    }

    return collision(enemy.sprite, playerBullet) ? enemy : null;

}

The pure code becomes is much more difficult to write:

class SpriteTree {

    HashMap<Sprite, List<Sprite>> parent_to_children;

    HashMap<Sprite, Sprite> child_to_parent;

}

class Game {

    int score = 0;

    Sprite player, playerBullet;

    List<Sprite> enemies;

    SpriteTree enemyTree;

}

Game updatePlayerBullet(Game game) {

    return updatePlayerBullet(

        game, head(enemies), tail(enemies));

}

Game updatePlayerBullet(Game game, Sprite enemy, List<Sprite> enemies) {

    if (enemy == null) return game;

    Sprite target = collision(
        enemy, game.enemyTree, game.playerBullet);

    if (target == null) return

        updatePlayerBullet(game, head(enemies), tail(enemies));

    Sprite parent = getValue(game.enemyTree, target);

    int newScore = score + 100;

    List<Sprite> newEnemyList = 

        parent != null ? 

        game.enemies : 

        remove(game.enemies, enemy);

    SpriteTree newEnemyTree = 

        parent != null ? 

        remove(game.enemyTree, parent, child) :    

        game.enemyTree;

    return new Game(

        newScore, 

        game.player, 

        game.playerBullet, 

        newEnemyList, 

        newEnemyTree);

   }

}

Sprite collision(Sprite enemy, 

                 SpriteTree enemyTree, 

                 Sprite playerBullet)

{

    List<Sprite> children = getValue(enemyTree, enemy); 

    if (children != null) {

        Sprite childEnemySprite = collision(

            head(children), 

            tail(children), 

            enemyTree, 

            playerBullet);

        if (childEnemySprite != null) 

            return childEnemySprite;

    }

    return collision(enemy.sprite, playerBullet) ? 

        enemy : 

        null; 

}

Sprite collision(Sprite enemy, 

                 List<Sprite> enemies, 

                 SpriteTree enemyTree, 

                 Sprite playerBullet)

{

    if (enemy == null) return null;

    Sprite result = 

        collision(enemy, enemyTree, playerBullet);

    return 

        result != null ? 

        result : 

            collision(head(enemies), 

                tail(enemies), 

                enemyTree, 

                playerBullet);

}

As you can see, the pure code spans many more lines of code than the imperative code; it's also more complex than the imperative code: the structures required to support the operations must be passed around all functions, even if not used by that specific function.

Now multiply the complexity of the state by one million (easily modern applications have a million times more state than this example), and you can see why people don't program in pure functional languages: a complex and hugely stateful program may become such a pure functional puzzle that no one could even begin to solve it.