-- Task: compute all arithmetic expressions containing exactly
-- the numbers 2,3,6,8 having the value 24

perm :: [Int] -> [Int]
perm []     = []
perm (x:xs) | perm xs == us ++ vs
            = us ++ [x] ++ vs
 where us,vs free

-- Representation of arithmetic expressions:
data Exp = Num Int  -- a number
         | Add Exp Exp
         | Sub Exp Exp
         | Mul Exp Exp
         | Div Exp Exp
 deriving Show

-- Evaluate some arithmetic expression to a value if
-- this arithmetic expression contains a given list of numbers
test :: Exp -> [Int] -> Int
--test (Num y) [z] | y == z = y
test (Num x) [x] = x
test (Add e1 e2) zs | split u v zs = test e1 u + test e2 v where u,v free
test (Sub e1 e2) zs | split u v zs = test e1 u - test e2 v where u,v free
test (Mul e1 e2) zs | split u v zs = test e1 u * test e2 v where u,v free
test (Div e1 e2) zs | split u v zs =
  opdiv (test e1 u) (test e2 v)
 where u,v free
       opdiv a b = if b == 0 || a `mod` b /= 0 then failed
                                               else a `div` b

-- Split is satisfied if the two first non-empty(!) lists concatenates
-- to the third list.
split :: [Int] -> [Int] -> [Int] -> Bool
split (u:us) (v:vs) xs | (u:us) ++ (v:vs) == xs = True

-- The main expression to compute all solutions to the puzzle:
-- > solve $ test e (perm [2,3,6,8]) == 24 where e free