Porting Haskell's Finite Domain Solver to Frege

On learning Haskell/Frege, I thought I would try to write a Sudoku Solver as an exercise in Frege. I was interested in Knuth's Dancing Links approach which I did in Java but found out that it is not that easy or Haskell's way of doing. Instead I found this excellent blogpost Constraint Programming in Haskell.

I learnt a lot from reading that code. So I thought, instead of trying a solver from scratch, why not port(read it as copy-paste :)) this to Frege? I have ported some Java classes to Frege but never attempted a Haskell library to Frege. This is my first attempt at that and it works great!

First, the Sudoku Solver module which is an application of the finite domain solver, explained here in another post A Haskell Sudoku Solver using Finite Domain Constraints:

Sudoku.fr

This is almost the same as Haskell. There are two changes though from the Haskell version:

1. Line 7 in Haskell: sudoku puzzle = runFD $ do but in Frege, it results in compilation error (not sure, why Frege parses it different).
2. Line 10: the lambda parameters in Haskell: \x n -> ... whereas in Frege, each parameter must be preceded by '\' hence it will be \x \n.

Apart from this, main has the type [String] -> IO ()

Next, the main module FD in Frege:

FD.fr

The main problem porting this module from Haskell to Frege is the missing IntSet, StateT, MonadState, MonadTrans in the standard library. So the lines from 150-208 are copy-pastes from Haskell library with few changes (apart from the syntax changes mentioned for the Sudoku module above):

1. MonadState in Haskell introduces Functional Dependency which Frege doesn't support yet. So I just specialized all the functions involving MonadState to (FD s) (lines 169, 207,208)
2. In instance declarations, the constraints come after the class name (line 154, for example)
3. newtype in Haskell is just regular type in Frege where the constructor has only one field (StateT declaration at line 152, for example)
4. Haskell derives instances automatically for 'newtype's but Frege derives instances only for Eq, Ord, Enum, Bounded and Show. So we have to manually derive Monad, MonadPlus for the (FD s) in the above module. But in this module, even for Eq, Ord, I had to manually derive because the constraints were generated even for the phantom type variable in FD while deriving automatically.
5. Unlike in Haskell, the field names for records are not global-scoped in Frege. So while referencing, the field names must be prefixed with either type name or with the record instance itself. Example:
   line 35 for prefixing with record type: FDState.varSupply s
   line 36 for prefixing with record variable itself: v.unFDVar
   

6. In this module, I have added all missing types/classes/instances (StateT,MonadTrans) except IntSet which is really huge. So I created that module in a seperate source file from Haskell source. In that module, I had to remove all preprocessor directives and I replaced .&. and .|. (bitwise 'and/or') with 'band' and 'bor' in Frege and 'shiftRL', 'shiftLL' with 'bshr', 'bshl'.

It seems it is not that difficult to port Haskell to Frege, atleast for this library. In fact, It is a lot easier to port from Haskell to Frege than creating native interface from Java to Frege.

For complete source code: https://github.com/mmhelloworld/finite-domain