在 Haskell 中不使用 + 运算符将两个数字相加

Question

我想将两个正数相加，而不使用任何基本运算符（例如 + 进行加法运算）。我已经解决了这个问题（在 add''' 函数中）（我认为）可能效率不高，但这不是现在的重点。我遇到了很多类型错误，但是我不知道如何处理，这让我很困惑，因为它在纸上有效而且我来自 python.

加1245 7489

--add :: Int -> Int -> Int
add x y = add'' (zip (add' x) (add' y))
 where
 add' :: Int -> [Int]
 add' 0 = []
 add' x = add' (x `div` 10) ++ [x `mod` 10]

转换 [1,2,4,5] [7,4,8,9] 然后将它们压缩在一起 [(1,7),(2,4)....]

 add'' :: [(Int,Int)] -> [Int]
 add'' (x:xs) = [(add''' (head x) (last x))] ++ add'' xs

summary [8,6,...] 和达到 10 时会发生什么尚未实现。

  where
  --add''' :: (Int,Int) -> Int
  add''' x y = last (take (succ y) $ iterate succ x)

两个数相加

Answer 1

您不能在元组上使用 head 和 last。 ...坦率地说，你根本不应该永远使用这些函数，因为它们不安全（部分），但它们可以用于列表。在 Haskell 中，列表与元组完全不同。
要获取元组的元素，请使用 模式匹配。
```
add'' ((x,y):xs) = [add''' x y] ++ add'' xs 
```
（要获取列表的元素，模式匹配通常也是最好的。）或者，您可以使用 fst 和 snd，它们在二元组上执行您想要的操作显然认为 head 和 last 会。
清楚哪些函数是柯里化的，哪些不是。你写add'''的方式，它的类型签名实际上是Int -> Int -> Int。 相当于到(Int, Int) -> Int，但它仍然与类型检查器不同。
add'' 的结果是 [Int]，但您试图将其用作 add 的结果中的 Int。那行不通，您需要再次从数字转换为数字。
add'' 不处理空的情况。这很容易解决，但比使用标准组合器进行递归要好。在您的情况下，这无论如何只能在元素方面起作用，因此您可以简单地使用 map – 或者直接在压缩中使用 zipWith。然后你也不需要解包任何元组完全，因为它使用柯里化函数。

您尝试的干净版本：

add :: Int -> Int -> Int
add x y = fromDigits 0 $ zipWith addDigits (toDigits x []) (toDigits y [])
 where
       fromDigits :: Int -> [Int] -> Int
       fromDigits acc [] = acc
       fromDigits acc (d:ds)
            = acc `seq`  -- strict accumulator, to avoid thunking.
                fromDigits (acc*10 + d) ds

       toDigits :: Int -> [Int] -> [Int]                -- yield difference-list,
       toDigits 0 = id                                  -- because we're consing
       toDigits x = toDigits (x`div`10) . ((x`mod`10):) -- left-associatively.

       addDigits :: Int -> Int -> Int
       addDigits x y = last $ take (succ x) $ iterate succ y

请注意，zipWith 要求两个数字的位数相同（zip 也是如此）。

此外，是的，我在 fromDigits 中使用了 +，这让整个事情变得毫无意义。在实践中你当然会使用二进制，然后它只是一个按位或乘法是左移。你实际上不需要在这里做的是特别注意 10-overflow，但这只是因为在 fromDigits 中使用 + 的作弊。

Answer 2

head 和 last 你的意思是 fst 和 snd，但你根本不需要它们，组件就在那里：

add'' :: [(Int, Int)] -> [Int]
add'' (pair : pairs) = [(add''' pair)] ++ add'' pairs 
  where
  add''' :: (Int, Int) -> Int
  add''' (x, y) = last (take (succ y) $ iterate succ x)
                = iterate succ x !! y
                = [x ..] !! y          -- nice idea for an exercise!

现在剩下的大问题是如何处理那些大可怕的 10 和更多数字。这是一个想法：用

产生一个数字和一个进位

   = ([(d, 0) | d <- [x .. 9]] ++ [(d, 1) | d <- [0 ..]]) !! y

你能从这里拿走吗？提示：数字倒序是你的朋友！

Answer 3

其他答案涵盖了您的方法中出了什么问题。但是，从理论的角度来看，它们都有一些缺点：它们要么让您到达 [Int] 而不是 Int，要么在从 [Int] 返回到 [Int] 的转换中使用 (+) Int。更重要的是，他们使用 mod 和 div 作为定义加法的子例程——这没关系，但是为了理论上合理，您需要确保可以定义 mod 和div自己不用加法作为子程序！

既然你说效率无关紧要，那我建议用数学家对加法的常用定义，即：0 + y = y, and (x+1) + y = (x + y)+1。在这里，您应该将 +1 视为一个单独的操作而不是加法，这是一种更原始的操作：只是增加一个数字的操作。我们在Haskell中拼写为succ（而它的"inverse"是pred）。考虑到这个理论定义，Haskell 几乎是这样写的：

add :: Int -> Int -> Int
add 0 y = y
add x y = succ (add (pred x) y)

所以：与其他答案相比，我们可以采用 Int 和 return Int，我们使用的唯一子程序是 "feel" 更原始的子程序：succ、pred，并检查数字是零还是非零。（我们只用了短短的三行代码……大约是最短提议替代方案的三分之一长。）当然，我们付出的代价是非常糟糕的性能……试试 add (2^32) 0!

与其他答案一样，这仅适用于正数。当您准备好处理负数时，我们应该再聊一次——有一些 fascinating mathematical tricks 可以拉。

Answer 4

我教授给的正式答案

也适用于正数和负数，但仍要求两个数字的长度相同

add 0 y = y
add x y
 | x>0 = add (pred x) (succ y)
 | otherwise = add (succ x) (pred y)

在 Haskell 中不使用 + 运算符将两个数字相加

Adding two numbers together without using the + operator in Haskell

haskell

addition