The following problem was given to my child as homework. It seems to need a clever idea which I was unable to spot. I would be very grateful for a hint. The problem is to count the number of different rational numbers that can be expressed using the six digits "123456" , and operators for addition, multiplication, subtraction and division, where each digit can occur at most once. Division by zero isn't allowed. I decided to apply brute force, by going through the possible expressions, evaluating them, weeding out duplicates, and counting the different values that results. Brute force seems to work for some small numbers of digits, like "1234", from which 230 different numbers may be defined. But "12345" makes hugs crash. > import List > data Expr = Leaf Char | Fork Char Expr Expr deriving Eq Storing text in a "buffer", by composition. > type Buffer = String -> String > empty :: Buffer > emit :: Buffer -> String > lit :: String -> Buffer > litc :: Char -> Buffer > app :: Buffer -> Buffer -> Buffer > empty = id > emit f = f "" > lit str = (str++) > litc c = (c:) > app = (.) Textual representation of an expression. > showExpr :: Expr -> Buffer > showExpr e = > f '-' e > where f b (Leaf n) = (n:) > f b (Fork c t1 t2) = if b `lt` c then p else brack p > where p = f c t1 > . lit " " > . litc c > . lit " " > . f c t2 > brack p = lit "(" . p . lit ")" > '/' `lt` c = False > '*' `lt` c = c `elem` "/" > '+' `lt` c = c `elem` "/*" > '-' `lt` c = c `elem` "/*+" > instance Show Expr where > showsPrec _ e = showExpr e > ops = "+*/-" The expression trees that can be formed from a given list of leaf labels. > trees ns = [ Leaf n | n <- ns ] ++ trees' ns > trees' ns = [ Fork c t1 t2 | c <- ops > , ms <- pss ns -- propersubsets ns > , t1 <- trees ms > , t2 <- trees (ns \\ ms) ] Another approach to generating expression trees. > splits t = (id,t):psplits t > psplits (Leaf n) = [] > psplits (Fork c t1 t2) = [ (Fork c t1 . s,g) | (s,g) <- splits t2 ] > ++ [ (flip (Fork c) t2 . s,g) | (s,g) <- splits t1 ] > trees2 [] = [] > trees2 (n:ns) = Leaf n : [ s (Fork c (Leaf n) g) | c <- ops, t <- trees2 ns, (s,g) <- splits t ] > ++ [ s (Fork c g (Leaf n)) | c <- ops, t <- trees2 ns, (s,g) <- splits t ] Their evaluation. I have assumed that division by zero has value zero. > eval (Leaf n) = toRational (fromInt (fromEnum n - fromEnum '0')) > eval (Fork '+' t1 t2) = eval t1 + eval t2 > eval (Fork '*' t1 t2) = eval t1 * eval t2 > eval (Fork '-' t1 t2) = eval t1 - eval t2 > eval (Fork '/' t1 t2) = let x2 = eval t2 in > if x2 /= 0 then eval t1 / x2 else 0 The main program, which prints out a table, as below. > main = let text = heading . body > heading = lit "Args\tNumber" > body = cl [ entry t | t <- prefixes "123456" ] > entry str = let nos = numbers str > n = length nos > in lit "\n" . lit str > . lit "\t" . shows n > . lit "\t" . shows (sort nos) > -- numbers = sort . nub . map eval . trees > numbers = nub . map eval . trees2 > in putStr (emit text) Lard. Return a list in increasing order of the initial segments of a list. > prefixes :: [a] -> [[a]] > prefixes xs = [] : case xs of [] -> [] > (x:xs') -> [ x : p | p <- prefixes xs' ] Out of interest, suffices. > suffices :: [a] -> [[a]] > suffices xs = xs : case xs of [] -> [] > (x:xs') -> suffices xs' Return a list of (.proper) sublists of a list. > subsets, propersubsets :: [a] -> [[a]] > subsets xs = xs : propersubsets xs > propersubsets (x:xs) = [ x:s | s <- propersubsets xs ] ++ subsets xs > propersubsets [] = [] Another version. > pss [] = [] > pss (x:xs) = let yss = pss xs in [ x : s | s <- yss ] ++ xs : yss compose a list of functions. > cl :: [a -> a] -> a -> a > cl = foldr (.) id Output: Main> main Args Numbers 0 [] 1 1 [1 % 1] 12 5 [-1 % 1,1 % 2,1 % 1,2 % 1,3 % 1] 123 29 [-5 % 1,-4 % 1,-3 % 1,-5 % 2,-2 % 1,-5 % 3,-1 % 1,-1 % 2,-1 % 3,0 % 1,1 % 6,1 % 5,1 % 3,1 % 2,2 % 3,1 % 1,3 % 2,5 % 3,2 % 1,7 % 3,5 % 2,3 % 1,7 % 2,4 % 1,5 % 1,6 % 1,7 % 1,8 % 1,9 % 1] 1234 230 [-23 % 1,-22 % 1,-21 % 1,-20 % 1,-19 % 1,-18 % 1,-17 % 1,-16 % 1,-15 % 1,-14 % 1,-13 % 1,-12 % 1,-23 % 2,-11 % 1,-21 % 2,-10 % 1,-9 % 1,-8 % 1,-23 % 3,-22 % 3,-7 % 1,-20 % 3,-13 % 2,-6 % 1,-23 % 4,-17 % 3,-11 % 2,-21 % 4,-5 % 1,-19 % 4,-9 % 2,-13 % 3,-4 % 1,-23 % 6,-19 % 5,-11 % 3,-7 % 2,-10 % 3,-13 % 4,-3 % 1,-23 % 8,-17 % 6,-11 % 4,-13 % 5,-5 % 2,-12 % 5,-7 % 3,-9 % 4,-2 % 1,-23 % 12,-13 % 7,-11 % 6,-7 % 4,-12 % 7,-5 % 3,-8 % 5,-3 % 2,-7 % 5,-11 % 8,-4 % 3,-5 % 4,-7 % 6,-1 % 1,-6 % 7,-5 % 6,-4 % 5,-3 % 4,-8 % 11,-5 % 7,-2 % 3,-5 % 8,-3 % 5,-7 % 12,-6 % 11,-1 % 2,-3 % 7,-5 % 12,-2 % 5,-1 % 3,-3 % 10,-1 % 4,-2 % 9,-1 % 5,-2 % 11,-1 % 6,-1 % 7,-1 % 8,-1 % 10,-1 % 12,0 % 1,1 % 24,1 % 20,1 % 18,1 % 14,1 % 12,1 % 11,1 % 10,1 % 9,1 % 8,2 % 15,1 % 7,2 % 13,1 % 6,2 % 11,1 % 5,3 % 14,2 % 9,1 % 4,2 % 7,3 % 10,1 % 3,4 % 11,3 % 8,2 % 5,5 % 12,3 % 7,4 % 9,6 % 13,1 % 2,6 % 11,4 % 7,7 % 12,3 % 5,8 % 13,5 % 8,2 % 3,5 % 7,8 % 11,3 % 4,4 % 5,5 % 6,6 % 7,7 % 8,11 % 12,1 % 1,8 % 7,7 % 6,6 % 5,5 % 4,9 % 7,4 % 3,11 % 8,7 % 5,3 % 2,8 % 5,13 % 8,5 % 3,12 % 7,7 % 4,9 % 5,11 % 6,13 % 7,23 % 12,2 % 1,25 % 12,15 % 7,13 % 6,9 % 4,7 % 3,12 % 5,5 % 2,13 % 5,8 % 3,11 % 4,17 % 6,23 % 8,3 % 1,25 % 8,19 % 6,13 % 4,10 % 3,17 % 5,7 % 2,11 % 3,15 % 4,19 % 5,23 % 6,4 % 1,25 % 6,21 % 5,13 % 3,9 % 2,14 % 3,19 % 4,5 % 1,21 % 4,11 % 2,17 % 3,23 % 4,6 % 1,25 % 4,19 % 3,13 % 2,20 % 3,27 % 4,7 % 1,22 % 3,15 % 2,23 % 3,8 % 1,25 % 3,26 % 3,9 % 1,28 % 3,10 % 1,21 % 2,11 % 1,23 % 2,12 % 1,25 % 2,13 % 1,27 % 2,14 % 1,15 % 1,16 % 1,17 % 1,18 % 1,19 % 1,20 % 1,21 % 1,22 % 1,23 % 1,24 % 1,25 % 1,26 % 1,27 % 1,28 % 1,30 % 1,32 % 1,36 % 1] 12345 INTERNAL ERROR: Bignum expected Main>