Beginner advice on idiomatic Haskell when writing a Ken-Ken solver

Question

In learning Haskell I have set a puzzle for myself which is to write a 4 X 4 KenKen solver. This involves placing the number 1 to 4 in a 4 by 4 matrix such that each row and column contains distinct values. There are also cages which constrain the numbers contained within based on addition, multiplication, division (two cells only) or subtraction (two cells only). For full rules see wikipedia page on KenKen.

I've been programming imperatively for 30 years and I'm wondering how to approach this in Haskell. It's here that I need some advice as an absolute beginner.

My sketchy overview :-

• for the moment, just hardcode the constraints and any starting numbers to avoid having to learn how to do IO and parsing,
• keep it at 4 by 4 for the moment to make life simplier,
• treat the cells as an immutable list of Maybe int with length 16,
• create a typeclass for constraint which can take a list of cells and return a boolean for if the constranit if violated or not (or is this a bit OO and I should create functions for these?),
• a constraint would say something like cells in positions 1, 2 and 5 must add up to 6. A function would take a list of cells it would return true or false,
• write constraints for plus, minus, divide, multiply and unique,
• create a recursive solve function that takes in the cells and a list of constraints,
• solve will check the cells against each of the constraints and call itself with new list trying out a different number or backtrack

So my question is, does this approach seems like it would work and is it idomatic in Haskell? Can you suggest how I could do something more functional without needing to know anything too advanced. I'm not interested in this being the most performant way to solve this problem since it's just an learning exercise I set myself.

EDIT: The answer and comments below centre around the need for the type class so that's probably the bit I'm getting wrong. I feel the need for it so I can treat all the different sorts of constraints polymorphically. I believe what everyone is saying is that this is insufficient and I can just have a list of functions that accept a list of cells and return the boolean.

Answer 1

That mostly sounds ok, but you are right about constraints being functions not a typeclass. In haskell the job of an interface is split in two. Typeclasses handle the this function can take any type that implements this interface part of the equation. An example of this is the Show typeclass. By implementing the Show type class your data type supports the show (to string) function. This means that print will now print instances of your type.

The part of the interface concept where you implement an interface so that you can have multiple implementations of the same function is handled through higher order functions rather than identically named functions attached to different types. As an example of this doFunc opp a b = opp a b it will have the type (a -> b -> c) -> a -> b -> c. Then this function can take any two operand function and apply it like doFunc (+) 1 2 or doFunc (*) 1 2.

The main thing I would suggest is try working bottom up. I found it really helped with the build small functions and compose them philosophy of FP programming.