Implementing Type inference

See my answer at StackOverflow.

Lunar Lockout

Lunar Lockout is a simple logic game, which was shown to me by a primary school teacher who bought it for the kids in her class. A few pieces are placed on a 5x5 board. The goal is to place a particular piece at the center, while being allowed to move any piece only if it can be blocked by another piece. It's a classic example of a game that can be solved by brute-force search.

I programmed a simple solver in Python. The method by which I programed this solver could be used to solve many other logic games. In fact, you could easily abstract the pieces away. You need:

1. a representation for a state of game (here, I use a list of cartesian coordinates, one per piece, the first element being for the piece that has to be moved to the center),
2. a function to generate all legal moves for a given state game,
3. a function that applies a move to a given game state, returning a new game state (it's easier than mutating the given game state for searching many alternatives at once).
4. a predicate to test whether a game state is a solution (here, I simply check whether the first coordinate is the center of the board).

With this pieces, it's easy to do a brute-force search (here, I use a breath-first search which skips already seen game states).

Probabilistic Modeling in Haskell

I translated the probabilistic modeling example from F# to Haskell. I ran into the restricted monad problem, because Support implemented as a Set requires the type class Ord. Perhaps, this problem is a step up from F#: if one uses a set with a type that doesn't implement Comparable, the error only appears at run-time in F#! 

I don't think this sample as translated does justice to Haskell. I ought to look at the Haskell implementation in the original paper by Ramsey and Pfeffer. In addition, the blog randomhacks.net has a whole series about probabilistic monads in Haskell, culminating in a paper (PDF). There also a functional pearl about probabilistic functional programming in Haskell.

Error Estimation in Scala

At github.

Implementing Probabilistic Modeling Using Monads in F# and Scala

For my induction into Scala, I wanted to translate the probabilistic monad of Chapter 9 of Expert F# (Introducing Language-Oriented Programming). The idea, based on the paper Stochastic Lambda Calculus and Monads of Probability Distributions, is to define a probability monad to compute over distributions of a domain instead of the domain itself. We limit ourselves to distributions over discrete domains characterized by three functions:

1. sampling


2. support
   (i.e. a set of values where all elements outside the set have zero chance of being sampled)


3. expectation of a function over the distribution
   (e.g. the probability of selecting element A by evaluating the function f(x) = 1 if x equals A and 0 otherwise)

Contrast the F# implementation with the Scala implementation. The Scala implementation closely follows the F# one, except for one major frustration: the type inference is not as powerful in Scala, as all function arguments must be declared.

Perhaps, I am missing a few tricks because I am new to Scala. If anyone has any suggestions for improving the Scala implementation, please share.

Cross-posted to the Scala wiki.