You are viewing ephemient

tachikoma valentines

Long time no blog~ (Part 3/3)

The source of this quote is a reaction to a spate of What I Learned From X That Makes Me a Better Programmer in Y articles (most are of the form «Haskell|Python|Ruby»⇒«C|C++|Java», though I have seen a Qt⇒C++ and a Java⇒Ruby (WTF?!)); it was meant to be contradictory, not sincere.

Why learning Haskell/Python makes you a worse programmer
I find I think in Python, and even in Haskell to some extent, even though I have used Haskell very little. I constantly find myself wanting to use idioms from these languages, or noticing how much less code I'd be able to write if I was using one of these languages (which, although very different from each other, are both much more powerful than the language I use at work, C#). It's very common for me to notice that using either of these languages I could decrease a chunk of code by a factor of 2-5, and not rare to see a factor of 10-20 in certain parts of the code base.

Further, my experience with Haskell means that I now see potential bugs everywhere in imperative code. Before, I was fairly well aware of the problems that stateful programming and side-effects can cause, having dealt with many scores of bugs related directly to this, and spent countless hours debugging these problems. But without any alternative, I guess I had just lived with it. Now I know there are other ways of doing these things, I find it difficult to be satisfied with any of the code I write. I am constantly aware that I am writing traps that other people are likely to fall in.

I also find C# code very ugly compared to both Python and Haskell. On the visual level, the mandatory use of braces everywhere (OK, they're not mandatory everywhere but are enforced by coding standards with good reason) makes code contain a lot of line noise and empty space, and combined with the verbosity of the libraries and type declarations etc, you find that a page of C# hardly does anything. I'm also thinking of beauty on the mathematical level, C# is a grubby mud hut compared to the breathtaking, elegant tower that is Haskell.

The net result of these things is to make me very depressed and demoralised. I feel like a human compiler, translating the Haskell or Python in my head into a language which is a whole level lower.
Reminds me of a snippet of code I wrote recently.
-- Haskell --
import Data.List
data Tree a = Empty | Tree a (Tree a) (Tree a) deriving (Eq, Ord, Read, Show)
makeOptimumTree :: (Num cost, Ord cost) => [(cost, value)] -> Tree value
makeOptimumTree src = snd $ bestSubtree (length src) 0 where
    bestSubtree 0 _ = ((0, 0), Empty)
    bestSubtree sz k = minimumBy (\((c1, _), _) ((c2, _), _) -> compare c1 c2)
      [ add (src !! (k+l)) (bestSubtree l k) (bestSubtree (sz-l-1) (k+l+1))
      | l <- [0 .. sz-1] ]
    add (cost0, a) ((cost1, sum1), t1) ((cost2, sum2), t2) =
        ((cost0+sum1+sum2+cost1+cost2, cost0+sum1+sum2), Tree a t1 t2)
# Python #
class Tree:
    def __init__(self, value, left = None, right = None):
        self.value = value; self.left = left; self.right = right
def make_optimum_tree(src):
    best_subtrees = [[(0, 0, None) for i in range(len(src)+1)]]
    for sz in range(1, len(src)+1):
        for k in range(len(src)-sz+1):
            minCost, minSum, minTree = 1e308, None, None  # 1e308≈infinity
            for l in range(sz):
                curCost, curValue = src[k+l]
                leftCost, leftSum, leftTree = best_subtrees[l][k]
                rightCost, rightSum, rightTree = best_subtrees[sz-l-1][k+l+1]
                addedCost = curCost+leftSum+rightSum+leftCost+rightCost
                if addedCost < minCost:
                    minCost = addedCost
                    minSum = curCost+leftSum+rightSum
                    minTree = Tree(curValue, leftTree, rightTree)
            best_subtrees[sz].append((minCost, minSum, minTree))
    return best_subtrees[len(src)][0][2]
4. Consider a binary search tree storing a set of keys x1<x2<x3<…<xn.  Let’s define the cost of handling a request for some key to be the number of comparisons made in searching for it (1 plus the distance of the node from the root of the tree).  For example, if the root is requested, the cost is 1.
   (c) Give a general algorithm for constructing the optimal binary tree given a sequence of counts c1,c2,…,cn (ci is the number of times xi is accessed).  The running time of your algorithm should be O(n3).  Hint: use dynamic programming.
From a recent Algorithms assignment.  The Haskell solution came very quickly and naturally, while the Python solution was a painful translation.
Well, okay.  The Haskell solution is only O(n3) if the Haskell compiler/runtime automatically memoizes bestSubtree; the Haskell spec allows (but doesn’t require for) this, and in practice, it probably won’t happen.  But manually memoizating is simply a matter of modifying
import Data.Map ((!), fromList)
        [ add (src !! (k+l)) (bestSubtree' ! (l, k))
                             (bestSubtree' ! (sz-l-1, k+l+1))
        | l <- [0 .. sz-1] ]
    bestSubtree' = fromList [ ((sz, k), bestSubtree sz k)
                            | sz <- [0 .. length src - 1]
                            , k <- [0 .. length src - sz] ]
which still leaves one feeling disappointed in the Python solution.
So frustration or dissatisfaction at those poor, feeble, non-____ languages?  Sure.  But makes me a worse programmer?  Certainly not.


tachikoma valentines

November 2009

Powered by