How to implement the Thistlethwaite's algorithm in Haskell?

Question

I am trying to implement the Thistlethwaite's algorithm in Haskell, following the descriptions found here, but encountered difficulties.

So far, I have managed to represent the cube, make it move as one likes, and display it on the terminal (a 2-dimensional representation), but I got problems when trying to reduce a general cube to one which can be obtained from a standard cube by moves in the group (R, L, F, B, U2, D2) (notations as in the link), as there are too many cases to consider: how many colors on the up layer are wrongly-oriented, on the middle layer, etc. This is only the first stage in the description, but I found a mess in my codes already, so I must have missed something.

As I am not sure if my description above is clear, I put up the relevant codes below, which are not correct, but indicate the problem.

--To intersect lists, of which the sizes are not very large, I chose to import the Data.List
import Data.List

--Some type declarations
data Colors = R | B | W | Y | G | O
type R3 = (Int, Int, Int)
type Cube = R3 -> Colors
points :: [R3] --list of coordinates of facelets of a cube; there are 48 of them.
mU :: Cube -> Cube --and other 5 moves.
type Actions = [Cube -> Cube]
turn :: Cube -> Actions -> Cube --chains the actions and turns the cube.
edges :: [R3] --The edges of cubes

criterion :: Colors -> R3 -> Bool -- determine if the edges are mis-placed.
criterion co p@(x, y, z) = case co of --W and Y are up and down faces respectively.
 R -> not (or [abs(x) == 3, abs(y) == 3])
 B -> not (or [abs(y) == 3, abs(z) == 3])
 O -> not (or [abs(x) == 3, abs(y) == 3])
 G -> not (or [abs(y) == 3, abs(z) == 3])
 _ -> True


stage1 :: Cube -> Cube 
stage1 c = turn c opes where
    wrongs = do
            res <- [[]]
            eg <- edges
            if criterion (c eg) eg
              then res
              else res ++ [eg]
    ups = filter (\(x, y, z) -> y == 3) points
    downs = filter (\(x, y, z) -> y == -3) points
    middles = filter (\(x, y, z) -> y == 0) points
    opes = do
         res <- [[]]
         case length (intersect middles wrongs) of
         0 -> case [length (intersect ups wrongs) == 0, length (intersect downs wrongs) == 0] of
            [True, True] -> res
            [True, False] -> [mD] --A quarter turn of the downside of the cube.
            [False, True] -> [mU]
            _ -> [mD, mU]
         1 -> let [(x, y, z)] = intersect middles wrongs in
                if x == 3 then case [length (intersect ups wrongs) == 0, length (intersect downs wrongs) == 0] of
                    [True, True] -> if z > 0 then [mR, mU] else [mR, mD]
                    [True, False] -> if z > 0 then [mD, mR, mU] else [mD, mR, mD]
                    [False, True] -> if z > 0 then [mU, mR, mU] else [mU, mR, mD]
                    _ -> if z > 0 then [mD, mU, mR, mU] else [mD, mU, mR, mD]
                else []

Then I realized that the above code is wrong as I cannot simply make a quarter turn U or D which makes the correct edges, if any, become incorrect, and I shall discuss 125 = 5 * 5 * 5 cases according to how many wrong edges are on each of the three layers of the cube, which I think of as not "right."

So my question is how to implement an algorithm that can handle so many cases, in a nice way?

If something about the description is unclear, please tell me so that I can explain what I am doing and what my problem is.

Any ideas and suggestions are greatly appreciated, thanks very much in advance.

P.S. I originally wanted to implement Korf's or Kociemba's algorithms, though it turned out that I cannot even handle the simplest case.

Answer 1

One thing - this code:

wrongs = do
        res <- [[]]
        eg <- edges
        if criterion (c eg) eg
          then res
          else res ++ [eg]

is better written as filter (\eg -> not (criterion (c eg) eg)) edges.