I finally found a problem I had no idea how to solve. When writing my generic solver, I used a very simple game to test it. It is a coin toss game, where you are more likely to get heads than tails. The player choses either side of the coin, and adds 1 point to his stack if he guesses right. If he is not, a point is added to another stack. The game ends when one of the stacks reaches, for example, 6 points.
I started working with a game tree, where the nodes are a structure containing the current game state, all decisions that could be taken by the current player, and all outcomes arising from those decisions, the outcome being a probability assorted to another node.
The problem with this approach is that most game are not trees, but directed graphs. It is easy to see with the coin toss game that you can reach the state where both stacks have 1 point in them in two different ways. I knew of that but figured that Haskell was quite smart, and the fact that I only used pure functions could lead to an easy optimization, namely that it was possible to cache function results.
It turns out that this doesn’t happen by default, the rationale being that it is often cheaper to recompute than to store.
As my tree is computed in a recursive way, it could be possible to instead use a Data.Map where keys are game states and values are the outcomes. I could pass this structure around in my tree generating function, and stop the recursion when there is a known state in this structure. But working like this would probably not be optimal, and would not be so nice with parallel computing (which I thought I would get for free by staying purely functional). Also, I would rather have the runtime handle cache expiration and things like that.
So I asked for help on #haskell on freenode. I have to say that contrary to almost all IRC channels, the people here are really helpful. Of course, as it is quite hard to state your whole problem quickly, you start to get answers irrelevant to your problem before you get the chance to describe it. There is also the bunch of people who believe your problem is related to theirs and don’t see it is not. On the other hand I had extremely pertinent pointers, and no stupid answers from the usual IRC crowd of idiots who try to explain to you how stupid your idea is while they clearly have no idea what they are talking about (go on any computer related channel and tell people it is much better to just log as root on servers instead of su-ing or sudo-ing, and you will see what I mean).
Anyway, we arrive to my beef against Haskell. It is clearly made, and appeals to, people from academia. You are assumed to have a really strong background in formal computer science (which I have not), and esoteric mathematical concepts related to functional programming (same here). You can’t read a Haskell related text without having to suffer those terms.
So, caching function results is called “memoizing”, and there are quite a few packages that are supposed to make it easy for you. So I was pointed to this blog post. As you can see, it is filled with mathematics and functional terminology. Just take a look at the module documentation, and tell me if you have a clue about what you are supposed to do with that.
The underlying idea is that data is cached, so if you could map all your function input to an efficient data structure, and most probably have a functor applied on it, the language laziness would behave just like a function cache (this might be wrong, my knowledge on this is shaky at best). You just access the data structure, and the function gets automagically called when the data is accessed. Of course, Haskell people seems to love abstracting stuff as much as possible, so in a perfect world you just have to import that module and add a magic “memo” keyword in front of the function you want memoizing.
This only works if you have a data structure that doesn’t require evaluating much before you get to your state, so you can’t get away with something simple. Most of the modules seem to use a trie structure, which I of course haven’t heard about before that. The only problem with those approaches is that it seems you have to be able to serialize your game state as a sequence of bits. It is easy for the game I described, but a lot of pain for other games I’d like to work with.
I went with this module, because you just have to work with the wrap function. It doesn’t seem to work at all. I have no clue on how you are supposed to use the Data.MemoTrie module, and I had to look in both modules source code to get a clue on what was going on (basically the previous chapters), because the documentation is incredibly arcane for somebody what had most of his experience with programming by auditing shitty Java applications and reversing large binaries.
Of course this is probably my fault, for not knowing how a functor is used, or yet another piece of exotic knowledge.