2

好吧，我确实明白，haskell 的全部意义（主要）是使用递归性从更简单的函数中构建更复杂的函数的优势，我有一个名为 pairs 的函数，它从整数字符串返回所有可能的元组组合，我然后有另一个称为操作的函数，它使用给定的元组打印出这两个数字可以执行的所有可能操作（*、+、-、/），现在是我无法理解的部分：

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

我正在尝试实现一个给定一串整数和一个目标数字的函数（最终目标是用整数字符串获得该数字）我打印出所有可能的元组组合及其结果，例如）

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

我对如何解决这个问题感到困惑，因为我知道我已经有一个函数可以在一个元组上打印所有可能的操作，一个产生所有元组的函数但我看不到如何组合它们，任何帮助将不胜感激，谢谢.

我看到了您的解决方案并且很有意义，但是对我来说从头开始为时已晚，

我已经这样做了：

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

（ 100 ， [3,5] ， [(4,1,'-',3)] ），这就是我想要的

我明白了，我想尝试我的工作方式，因为它看起来有点不同，在第二次之后我感到困惑，我在 Haskell 上仍然有点糟糕。所以这就是我的函数所做的： 对：当给定一个字符串时返回所有可能的元组：对 [1,2,3,4,5,6] 将返回 [(1,2),(1,3)... etc] 操作接受一个元组并返回该元组的所有可能操作（必须是正整数结果，否则我们不想要它），最后

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

取 n 为目标数， ns 为 6 个 +ints 的字符串，到目前为止返回一个字符串，其中包含打印的所有元组组合，例如：[(3,'+',4,7),(3,´*´,4 ,12)...等] 但是我希望它在每个阶段打印：

[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)] ),
4

2 回答 2

2

有很多方法可以解决这个问题。下面是一个相对简单的 Haskell 式解决方案的大纲。请注意，它使用代数数据类型，因此如果您还没有熟悉它，您需要熟悉它。

注意：这是一个有点复杂的问题。我的解决方案（相对干净）是 55 行长。

第一步是为您的问题定义适当的数据类型。我会选择以下：

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

类型的值Expr是一个表达式树，它由四个二元运算组成，并且在其叶子处具有整数。使用此定义，您需要定义以下函数：

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

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

然后找到计算为特定数字的表达式就是：

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

写作eval

该eval函数将是一个直接的案例分析：

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

提示：对于除法，查找quot函数。

写作exprs

前几个案例exprs非常简单：

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

当列表中只有一个数字时，您可以创建的唯一表达式是 with Lit。

的最后一个案例是exprs这样的：

  1. 分为xs两个子列表：left和right
  2. 使用列表制定表达式树left
  3. 使用列表制定表达式树right
  4. 将两个表达式树与二元运算符组合

步骤 2 和 3 只是对exprs函数的递归调用。第 4 步只是遍历所有可能的二元运算符。您可以为此使用列表推导。

对于第 1 步，我们需要找到将列表拆分为两个子列表的所有方法。也就是说，我们需要定义一个函数：

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

例如，parts [1,2] = [ ([1,2],[]), ([1],[2]), ([2],[1]), ([], [1,2]) ]。

当然，parts可以递归定义，诀窍是找到模式：

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

这里的一个提示是问问自己你将如何parts (x:xs)从parts xs.

注意事项

我遗漏了一些实现细节。首先，如果你真的想正确实现除法，你可能不得不重新考虑这个类型签名eval：

eval :: Expr -> Int

最初为了让事情正常工作，您可能希望省略除法运算符。然后你可能想阅读Maybe数据类型。

我还遗漏了定义中的细节exprs。在我概述的步骤中潜伏着一个无限循环的陷阱（可以很容易地避开）。

祝你好运！

注释

（由于 SO 不喜欢评论中的长时间运行的线程，我将在这里解决 OP 的问题。）

正如我之前提到的，有很多方法可以解决这个问题，例如，参见 Algorithm for permutations of operator andoperands

这种方法更复杂，但它是一种有用的分解模式，您将看到它在 Haskell 中被广泛使用。它还注意区分以下问题：

  1. 生成可能的树（exprs函数）
  2. 评估表达式树（eval函数）
  3. 找到感兴趣的树 ( filter ...)

您的方法结合了前两个问题。如果您只是解决这个问题，这可能不是问题，但假设您更改了法律表达的标准。例如，如果列表中的数字可以重复使用多次怎么办（目前数字只能使用一次。）或者，如果您不需要使用所有数字怎么办？这些变化只需要改变exprs功能。

于 2013-05-06T07:23:35.897 回答
0

我想我终于明白你想要做什么了。

阅读以下代码时，您应该运行choose1并pairs查看 int 示例列表以查看它们的作用，例如choose1 [2,5,7]和pairs [1,2,3].

phi将所有可能的评估作为一对返回，(x,hs)其中x是最终结果，hs是操作历史（列表）。请注意，历史是向后的 -hs列表的第一个元素是执行的最后一个操作。

列表中的每个元素hs本身就是一个元组，(Int,Char,Int,Int)例如(3,'-',4,-1)，表示操作3-4 => -1。

作为测试，请尝试：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
于 2013-05-08T01:09:11.353 回答