Given a string of ints and an objective number print out all the possible combinations of tuples and their results

Question

Well, i do understand that the whole point of haskell (mostly) is the advantage of using recursivity to build more complex functions out of simpler ones, I have a function named pairs that from a String of ints returns all the possible tuple combinations, I then have another function called operations which with a given tuple, prints out all of the possible operations the two numbers can do (*,+,-,/), now comes the part i can't get round my head:

-- Find all possible 2-combinations of the elements of xs.
pairs :: [Int] -> [(Int, Int)]
pairs xs = [(x, y) | (x:ys) <- tails xs, y <- ys]

operations :: (Int, Int) -> [(Int, Int, Char, Int)]
operations (x, y) =
    [ (x, y, '+', x + y) ] ++
    [ (x, y, '*', x * y) ] ++
    [ (x, y, '-', x - y) | x > y, (x/=4 && y/=2) ] ++
    [ (x, y, '/', x `div` y) | x >= y, x `mod` y == 0]

I'm trying to implement a function that given a string of ints and an objective number (ultimate aim is to obtain that number with the String of ints) I print out all the possible combinations of tuples and their results, e.g.)

solve ( 100 , [1,4,5] , [] )

[ ( 100 , [5,5] , [(1,4,'+',5)] ),take first tuple 1,4 add and subs into "new tuple"5,5
( 100 , [3,5] , [(4,1,'-',3)] ),
( 100 , [6,4] , [(1,5,'+',6)] ),
( 100 , [4,4] , [(5,1,'-',4)] ),
( 100 , [9,1] , [(4,5,'+',9)] ),
( 100 , [1,1] , [(5,4,'-',1)] ),
( 100 , [20,1] , [(4,5,'*',20)] ) ]

Im confused as to how to approach this, as i know i already have a function that prints all possible operations on a tuple and one that produces all the tuples yet i can't see how to combine them, any help would be appreciated, thanks.

---

I see your solution and makes sense but its too late for me to start from scratch,

i have done this:

solve(n,ns) = [ e | ns' <- pairs ns
                      , e   <- operations ns'] 

( 100 , [3,5] , [(4,1,'-',3)] ), is what i want

I see, i want to try my way to work as it seems a bit different and i get confused after the 2nd where, i'm still a bit terrible at Haskell. So this is what my functions do: pairs: when given a String returns all possible tuples: pairs [1,2,3,4,5,6] would return [(1,2),(1,3)...etc] operations takes a tuple and returns all possible operations with that tuple (has to be positive integer result else we don't want it) and finally

solve(n,ns) = [ e | ns' <- pairs ns
                      , e   <- operations ns'] 

takes n the objective number, ns a string of 6 +ints and so far returns a string with all combinations of the tuples printed such as: [(3,'+',4,7),(3,´*´,4,12)...etc] however i want it printing at each stage:

[n,(result of tuple operation,string number)(tuple operation)]
eg ( 100 , [5,5] , [(1,4,'+',5)] ),take first tuple 1,4 add and subs into "new tuple"5,5
( 100 , [3,5] , [(4,1,'-',3)] ),
( 100 , [6,4] , [(1,5,'+',6)] ),

Answer 1

I think I finally understand what you are trying to do.

When reading the following code you should run choose1 and pairs on sample lists of ints to see what they do, e.g. choose1 [2,5,7] and pairs [1,2,3].

phi returns all the possible evaluations as a pair (x,hs) where x is the final result and hs is the history of operations (a list). Note that the history is backwards - the first element of the hs list is the last operation that was performed.

Each element of the hs list is itself a tuple of the form (Int,Char,Int,Int) -- e.g. (3,'-',4,-1) and denotes the operation 3-4 => -1.

As a test, try: head $ solve [3,7,13,19,23,29] 823

import Data.List (inits,tails)

always _ _ = True
canDivide a b = (b /= 0) && (a `mod` b) == 0

ops :: [ ( Int -> Int -> Int, Char, Int -> Int -> Bool) ]
ops = [ ((+), '+', always),
        ((-), '-', always),
        ((*), '*', always),
        (div, '/', canDivide) ]

choose1 xs = zip xs zs
  where zs = zipWith (++) (inits xs) (tail $ tails xs)

pairs xs = [ (x,y,r2) | (x,r1) <- choose1 xs, (y,r2) <- choose1 r1 ]

phi xs = go xs []
    where
      go [] hs  = []
      go [x] hs = [ (x,hs) ]
      go xs hs  = [ (x,h) |
          (a,b,rest) <- pairs xs,
          (op,name,can) <- ops,
          can a b,
          let c = op a b,
          (x,h) <- go (c:rest) ((a,name,b,c):hs) ]

solve :: [Int] -> Int -> [ (Int, [ (Int, Char, Int, Int) ] ) ]
solve xs n = filter (\(x,hs) -> (x == n)) $ phi xs

Answer 2

There are a lot of ways to solve this problem. What follows is an outline of a relatively straight-forward Haskell-esque solution. Note that is uses algebraic data types, so you'll want to become familiar with that if you aren't already.

Note: This is a somewhat involved problem. My solution (which is relatively clean) is 55 lines long.

The first step is to define the appropriate data type for your problem. I will choose the following:

data Expr = Lit Int
   | Plus Expr Expr
   | Times Expr Expr
   | Minus Expr Expr
   | Divide Expr Expr
  deriving Show

A value of type Expr is an expression tree that is composed of four binary operations and has integers at its leaves. Using this definition you'll want to define the following functions:

eval :: Expr -> Int       -- "evaluate" a expression

exprs :: [Int] -> [Expr]  -- derive all expression trees whose literals come from
                          -- a list of integers

Then finding expressions which evaluate to a particular number is just:

findexprs :: [Int] -> Int -> [Expr]
findexprs xs y = filter (\e -> eval e == y) $ exprs xs

Writing eval

The eval function is going to be a straight-forward case analysis:

eval (Lit x) = x
eval (Plus a b) = (eval a) + (eval b)
eval (Minus a b) = (eval a) - (eval b)
...

Hint: for division, look up the quot function.

Writing exprs

The first couple of cases for exprs is pretty easy:

exprs :: [Int] -> [Expr]
exprs []  = []
exprs [x] = [ Lit x ]
exprs xs  = ...

When there is only one number in the list, the only expression you can create is with Lit.

The final case of exprs goes something like this:

1. divide xs into two sub-lists: left and right
2. formulate an expression tree using the list left
3. formulate an expression tree using the list right
4. combine the two expression trees with a binary operator

Steps 2 and 3 are just recursive calls to the exprs function. Step 4 just iterates through all of the possible binary operators. You can use a list comprehension for this.

For step 1 we need to find all the ways of splitting a list into two sub-lists. That is, we need to define a function:

parts :: [Int] -> [ ([Int], [Int]) ]

For example, parts [1,2] = [ ([1,2],[]), ([1],[2]), ([2],[1]), ([], [1,2]) ].

Of course, parts can be defined recursively, and the trick is to find the pattern:

parts [] = [ ([],[]) ]
parts (x:xs) = ...???...

A hint here is to ask yourself how you would form parts (x:xs) from parts xs.

Caveats

I've left out some implementation details. First of all, if you really want to implement division correctly you'll probably have to re-consider this type signature for eval:

eval :: Expr -> Int

Initially to get things working you may want to leave out division operator. Then you may want to read up on the Maybe data type.

I've also left out details in the definition of exprs. There's an infinite-loop pitfall (which can be easily side-stepped) lurking in steps I've outlined.

Good luck!

Comments

(Since SO doesn't like long-running threads in the comments, I'll address the OP's questions here.)

As I mentioned before, there are many ways to solve this problem, e.g. see Algorithm for permutations of operators and operands

This approach is more complicated, but it is a useful decompositional pattern which you will see widely used in Haskell. It also takes care to separate the following concerns:

1. generating the possible trees (the exprs function)
2. evaluating an expression tree (the eval function)
3. find the trees of interest (filter ...)

Your approach combines the first two concerns. That may not be a problem if you are just solving this problem, but suppose you change the criteria for a legal expression. For instance, what if numbers in the list can be reused multiple times (currently numbers may only be used once.) Or, what if you don't need to use all of the numbers? These variations would only require changing the exprs function.