Functional programming in Python: 2048 merge functions

Question

I've written the core functions for a basic 2048 game. I know Python isn't a functional programming language, but I like the "functional style" (easier to maintain, simple to understand, more elegant), and have tried to use this rather than iteration, mutation, etc when I can.

From a functional perspective, what more can be done to improve my code? From an organizational perspective, would it be best to include these functions inside a "game client" class, or better to leave them in a separate module? Right now I have the separate, but coming from a OOP background, my feeling is that the helper functions should be in one class.

def merge(row):
    """ Returns a left merged row with zeros

    >>> merge([2, 2, 4, 4])
    [4, 8, 0, 0]
    >>> merge([0, 0, 4, 4])
    [8, 0, 0, 0]
    >>> merge([1, 2, 3, 4])
    [1, 2, 3, 4]
    """

    def inner(b, a=[]):
        """ 
        Helper for merge. If we're finished with the list,
        nothing to do; return the accumulator. Otherwise
        if we have more than one element, combine results of first
        with right if they match; skip over right and continue merge
        """

        if not b:
            return a
        x = b[0]
        if len(b) == 1:
            return inner(b[1:], a + [x])
        return inner(b[2:], a + [2*x]) if x == b[1] else inner(b[1:], a + [x])

    merged = inner([x for x in row if x != 0])
    return merged + [0]*(len(row)-len(merged))

def reverse(x):
    """ Returns a reversed list of x """
    return list(reversed(x))

def left(b):
    """ Returns a left merged board

    >>> merge([2, 2, 4, 0])
    [4, 4, 0, 0]
    """

    return [list(x) for x in map(merge, iter(b))]

def right(b):
    """ Returns a right merged board

    >>> reverse(merge(reverse([2, 2, 4, 0])))
    [0, 0, 4, 4]
    >>> reverse(merge(reverse([4, 4, 4, 4])))
    [0, 0, 8, 8]
    """

    t = map(reverse, iter(b))
    return [reverse(x) for x in map(merge, iter(t))]

def up(b):
    """ Returns an upward merged board
        NOTE: zip(*t) is transpose

    >>> b = [[2, 4, 0, 4],[2, 4, 4, 4],[2, 0, 0, 2],[2, 2, 0, 4]]
    >>> up(b)
    [[4, 8, 4, 8], [4, 2, 0, 2], [0, 0, 0, 4], [0, 0, 0, 0]]
    """

    t = left(zip(*b))
    return [list(x) for x in zip(*t)]

def down(b):
    """ Returns an upward merged board
        NOTE: zip(*t) is transpose

    >>> b = [[2, 4, 0, 4],[2, 4, 4, 4],[2, 0, 0, 2],[2, 2, 0, 4]]
    >>> down(b)
    [[0, 0, 0, 0], [0, 0, 0, 8], [4, 8, 0, 2], [4, 2, 4, 4]]
    """

    t = right(zip(*b))
    return [list(x) for x in zip(*t)]

def can_move(b):
    """ Returns the status (over/not over) of the game

    >>> b = [[1,2,3,4],[5,6,3,8],[1,2,3,4],[5,6,7,8]]
    >>> can_move(b)
    True
    >>> b = [[1,2,3,4],[5,6,7,8],[1,2,3,4],[5,6,7,8]]
    >>> can_move(b)
    False
    >>> b = [[1,2,3,4],[5,6,7,8],[1,2,3,4],[5,6,7,0]]
    >>> can_move(b)
    True
    """

    def inner(b):
        for row in b:
            for x, y in zip(row[:-1], row[1:]):
                if x == y or x == 0 or y == 0:
                    return True
        return False
    return inner(b) or inner(zip(*b))

Here's the client:

class Game2048:
    """
    A 2048 game client

    Merge like tiles to reach tile 2048
    """
    def __init__(self):
        self.b = [[0]*4 for i in range(4)]
        self._spawn(2)

    def _spawn(self, k):
        dist = [2]*9 + [4]
        rows = list(range(4))
        cols = list(range(4))

        random.shuffle(rows)
        random.shuffle(cols)
        count = 0
        for r, c in itertools.product(rows, cols):
            if count == k:
                return
            if self.b[r][c] == 0:
                self.b[r][c] = random.sample(dist, 1)[0]
                count += 1

    def pprint(self):
        print('\n'.join([''.join(['{:4}'.format(item) for item in row])
                         for row in self.b]))

    def play(self):
        while can_move(self.b):
            self.pprint()
            direc = input("Please enter a direction (w, a, s, d): ")

            if   direc == "w": self.b = up(self.b)
            elif direc == "s": self.b = down(self.b)
            elif direc == "a": self.b = left(self.b)
            elif direc == "d": self.b = right(self.b)
            else:
                continue 

            self._spawn(1)

Answer 1

I don't have anything substantial to say, but bravo on the extent to which you've done functional programming in Python. Your code looks quite clean and functional to me; I could probably translate it line by line into totally idiomatic Clojure.

If you want to be functional up to the very architecture, the best way to organize your code would be to put your functions into modules with suitable names rather than classes. Most functional languages don't have classes (OCaml, F#, and Scala are exceptions, to the extent that you consider Scala a functional language), but most of them do have some namespace or module concept. (Clojure has namespaces, and Erlang and Haskell have modules.)

If I wanted very functional Python code, I'd mostly use modules to organize my code, and use classes as data containers, to define new types, or for polymorphism, since Python lacks Clojure's and Haskell's fancy polymorphic tools like multimethods or pattern matching. This pretty much mimics Clojure's namespaces and records, or Haskell's modules and types. You might be interested in When should objects be used in OCaml? for some advice on when to use classes in functional languages that support them.

For example, in your code, you have some functions that modify the game state, down, left, merge, etc. Those functions are all pretty much pure functions that take arguments and return values. In object-oriented style code we might put them in a class just because they're logically grouped together, maybe as class methods or static methods to signify that we don't need separate instances. But you could also just drop all the functions from your first code sample into a module called something like gamestate. In Clojure I would just have a namespace, maybe called something like game.state, that contained all those functions as top-level definitions. It would look something like this:

(ns game.state)

(defn left [b]
  (comment code for left))

(defn right [b]
  (comment code for right))

(defn merge [row]
  (comment code for merge))

If I wanted to use those functions in another namespace, I would require the namespace, like this:

(ns game.core
  (:require [game.state :as state]))

(defn move-left [board]
  (state/left board))

That's very similar to putting some functions in a Python module and importing the module:

import state

def move_left(board):
    return state.left(board)

It looks uncomfortably like C code, where you have global functions in files that you include in other files. Like C, Clojure and Haskell don't have classes; all behavior is in functions. I'm doing a Clojure simulation project right now. I have a state namespace, an events namespace, and an entities namespace. The state namespace functions are all concerned with managing the state of the simulation; the events functions are different events which occur in the simulation—fight, move, spawn and their helpers; the entities namespace contains functions and declarations for defining entities, like new-witch.

You can achieve the same thing with Python modules. Even when I'm not trying to be very functional in Python, I often default to organizing my code like this if I don't expect my objects to manage any state. All that said, there's nothing particularly wrong with using classes for this purpose in Python. Python is an object-oriented language; being able to mix usages like that is its strength. In Scala, another multi-paradigm language, people certainly don't shy away from using classes.