1

第一：我的英语不是很好，我很抱歉:(

所以，这是我必须解决的问题：

-- Based on a simple math game: given a list of numbers use the four basic 
-- operations (+, -, /, *)  between them to find (or be as close as possible to) 
-- another given number

有我的问题的例子，但我需要更具体地解决，我无法在“haskell 模式”下思考，我是 C++ 玩家:(

所以，我已经完成了：

-- 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, y, '/', x `div` y) | x >= y, x `mod` y == 0]

我必须实现另一个函数（'solve'）来执行以下操作：

'solve' 函数返回一个包含所有结果节点的列表，以从可用数字列表中选择一对数字，并将可能的操作应用于所选伙伴。

我将不得不更新可用号码列表（删除那些使用并添加新号码）和操作列表（以反映最新操作）

例子：

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)] ) ]

首先取几个数字（使用pairs函数），

'操作'可以做的第二个显示[number,number,'operation',result]。

我有这样的事情：

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

但我不能让它工作，知道吗？

编辑：

我非常感谢您的回答，非常感谢您，但是如果我不能执行我要求的功能，我将无法理解您的发展，因为我在 Haskell 中真的很新:(

正如我所说，我需要一个带有数字列表的函数以及我在主帖中编写的 2 个操作（操作和对）创建另一个函数来执行此操作：

例子）

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

[ ( 100 , [5,5] , [(1,4,'+',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)] ) ]

非常感谢您的快速回答，但我的回答需要更具体。

4

1 回答 1

2

这是一个非常巧妙的问题，但比最初看起来要复杂一些。

我们想要，对于数学运算'+'，'-'，'*'，和'/'

data Op = Plus | Minus | Mult | Div deriving (Eq, Ord)

ops = [Op]
ops = [Plus, Minus, Div, Mult]

instance Show Op where
  show Plus  = "+"
  show Minus = "-"
  show Div   = "/"
  show Mult  = "*"

和一组数字ns，搜索所有可能的算术表达式，这些算术表达式只使用每个数字一次，以获得最接近某个目标的表达式。为了解决这个问题，我们将抽象地表达问题，然后以明显正确的方式解决它，然后应用一些优化。

让我们想想什么样的数据类型可以代表我们的表达。每个术语，称为它Term，需要是一个和它所作用的其他两个的组合，或者是一个“纯”值，一个本身就是一个整数。OpTerms

data Term = Ap Op Term Term | Pure Double

这样我们就(2 + (3 * 4))表示为App Plus (Pure 2) (App Mult (Pure 3) (Pure 4))。给定这样一个Term，我们可以递归地遍历它以将其打印出来或计算结果。

instance Show Term where
  show (Pure x)    = show x
  show (Ap op l r) = "(" ++ show l ++ " " ++ show op ++ " " ++ show r ++ ")"

我们将在适当的时候对此进行更详细的调查，但现在我们需要专注于生成。

给定数字列表中的任何数字n <- ns，我们可以构造 a Term，它以三种不同的方式涉及它，或者Pure n, Term op n other，或者Term op other nwhereop是我们的一个，ops并且是从(没有)other中的数字构造的术语。这是一个完全有效的递归定义，你可以从. 让我们构建它。Data.List.delete n nsnsnTermsns

首先，我们需要一种选择或“关注” ns. 我们将通过形成一个拉链来做到这一点，ns它将pares :: [a] -> [([a], a, [a])]一个列表变成一个三元组列表，一个用于原始列表中的每个元素。中间元素是“聚焦”值，左侧列表是我们聚焦值左侧的元素，右侧列表是右侧的值。这可能看起来有点矫枉过正，但稍后会派上用场。

pare :: [a] -> Int -> ([a], a, [a])
pare xs n = pare' n ([], xs) -- accumulate the left and right sides
  where
    -- we end up storing the left list in reverse, which is the style of zippers
    -- it seems a little weird, but it makes the code very simple and it shouldn't
    -- affect our problem
    pare' 0 (left, x:right) = (left, x, right)
    pare' n (left, x:right) = pare' (n-1) (x:left, right)

-- 'pare' is a little dangerous since it can have out of bounds errors,
-- but 'pares' can not.
pares :: [a] -> [([a], a, [a])]
pares xs = map (pare xs) [0..length xs - 1]

现在我们可以打电话pares [1,2,3]来获取

[ ( []    , 1 ,  [2,3] )
, ( [1]   , 2 ,  [3]   )
, ( [2,1] , 3 ,  []    ) ]

从这里开始，它是一个简单的定义，allTerms :: [Double] -> [Term]，使用List推导。

allTerms ns =
  [ result
  | (left, n, right) <- pares ns
  , result <- Pure n : (concat [ [ Ap op (Pure n) term, Ap op term (Pure n) ]
                               | op   <- ops
                               , term <- allTerms (left ++ right)
                               ])
  ]

好吧，所以不是那么直截了当。由于我们总是希望“至少”返回(Pure n) Term，因此我们必须分离出处理递归项的列表推导。否则，我们[]总是得到结果，因为列表没有返回任何递归子项allTerms []。

这个符号有点难，所以让我们把它改成Monadic 符号，因为所有List的理解都可以转换为List Monad.

allTerms ns = do
  (left, n, right) <- pares ns
  let branches = do
        op <- ops
        term <- allTerms (left ++ right)
        [ Ap op (Pure n) term, Ap op term (Pure n) ]
  Pure n : branches

do表示法让我们去掉了一些不必要的括号，并为我们以后的优化提供了更好的基础。现在，我们可以测试一下。

*Main> mapM_ print $ allTerms [1,2]
1.0
(1.0 + 2.0)
(2.0 + 1.0)
(1.0 - 2.0)
(2.0 - 1.0)
(1.0 / 2.0)
(2.0 / 1.0)
(1.0 * 2.0)
(2.0 * 1.0)
2.0
(2.0 + 1.0)
(1.0 + 2.0)
(2.0 - 1.0)
(1.0 - 2.0)
(2.0 / 1.0)
(1.0 / 2.0)
(2.0 * 1.0)
(1.0 * 2.0)

应该很容易检查这是否......嗯，全面。这也表明了我们定义中的一个弱点——我们忽略了问题的许多对称性。例如，没有必要为我们已经访问过的数字生成子项（这些项将由以后的项再次生成。此外，当opisPlus或时Mult，我们可以利用交换性。这是一个快速的重写来解决这个问题.

allTerms ns = do
  (left, n, right) <- pares ns
  let branches = do
        op <- ops
        term <- allTerms right -- we no longer visit the left terms
                               -- this is the value of using 'pares'
        makeApps op (Pure n) term
  Pure n : branches
  where
    -- makeApps only applies symmetry when the operator is Div or
    -- Minus.
    makeApps Plus t1 t2 = [Ap Plus t1 t2]
    makeApps Mult t1 t2 = [Ap Mult t1 t2]
    makeApps op   l  r  = [Ap op l r, Ap op r l]

如果ns = [1,2,3]那么我们的第一个版本将生成 195Term秒。第二个利用对称性仅生成 57Term秒。这有点合理，所以让我们继续前进。

所以现在我们已经生成了所有可能Term的 s，我们需要评估它们。就像我们的Show实例一样，这是一个相对简单的递归定义。

calcTerm :: Term -> Double
calcTerm (Pure x) = x
calcTerm (Ap Plus  l r) = calcTerm l + calcTerm r
calcTerm (Ap Minus l r) = calcTerm l - calcTerm r
calcTerm (Ap Mult  l r) = calcTerm l * calcTerm r
calcTerm (Ap Div   l r) = calcTerm l / calcTerm r

假设我们正在寻找Term值最接近 的goal :: Double。我们可以Term t用它的“错误”注释每个，abs (goal - calcTerm t)然后按它排序。我们需要使用专门sortBy :: (a -> a -> Ordering) -> [a] -> [a]的 from Data.List。

import Data.List (sortBy)

bestTerm :: Double -> [Term] -> (Double, Term)
bestTerm g =
  minimumBy (\(a, _) (b, _) -> a `compare` b)
  . map (\t -> (abs (g - calcTerm t), t))

或者，使用一些专门的函数Control.Arrow.&&&，Data.Ord.comparing我们可以最快地编写

bestTerm :: Double -> [Term] -> (Double, Term)
bestTerm g =
  minimumBy (comparing fst) . map (first error) where error t = abs (g - calcTerm t)

我们可以开始回答这个问题

*Main> bestTerm 31 $ allTerms [1..5]
(0.0,(1.0 + ((3.0 * (4.0 * 5.0)) / 2.0)))

但只是有时，因为等待会length $ allTerms [1..10]破坏我的耐心。看起来有(7^n-1)/6关于n数字的术语（参见Sloane），所以我们会等待它来计算 47,079,208Term秒。

希望这展示了您如何计算问题的答案，并为您提供缓行位置以寻找优化结果的方法。

我认为你的例子的答案是(79.0, (1.0 + (4.0 * 5.0)))

于 2013-07-11T19:35:49.843 回答