二进制补码尽可能简单，无需高阶函数

Question

作业要求我在 Haskell 中实现二进制补码方法，当给定一个二进制数字列表时 returns 该列表的二进制补码列表。

>>>twoComplement [0,0,0,1,1,0,1,0]
[1,1,1,0,0,1,1,0]

所以我不允许使用高阶函数，例如last、init等，这必须尽可能简单。我要学写漂亮的代码

我想在不使用反向函数的情况下执行此操作，但如果需要，我可以这样做。

我已经尝试了很多东西。我知道我需要翻转所有位，这并不复杂。

flipBits [] = []
flipBits (x:xs)
         |x == 0 = 1:flipBits xs
         |x == 1 = 0:flipBits xs
         |otherwise: error "Only 0 and 1 are allowed."

但是我觉得加一个部分真的很复杂。特别是如果我将 1 添加到已经存在的 1，则结转。此外，不允许使用列表生成器。这都是关于理解列表和连接器 :。

编辑： 在 vkuo 的帮助下，我写了以下内容，到目前为止似乎做得很好。

twoComplement:: [Integer] -> [Integer]
twoComplement [] = []
twoComplement lst = turn(tC(turn(lst)))
                where
                    tC (x:xs)
                        |x == 1 = 1:flipp xs
                        |x == 0 = x:tC xs
                    flipp [] = []
                    flipp(x:xs)
                        |x == 0 = 1:flipp xs
                        |x == 1 = 0:flipp xs
                    turn [] = []
                    turn (x:xs) = turn xs ++ [x]

如果我们要使用reverse，我们必须自己制作。所以我就那样做了。请问有没有办法不逆向啊？

Answer 1

如果您不想反转，那么您随时都会看到原始数字和列表其余部分的结果。余数的结果是一个二进制补码加上一个进位数字。您必须 return 相同类型的结果，即一个进位数字加上一个二进制补码，尽管还要考虑一个数字。

像这样：

invAdd :: Int -> (Int,[Int]) -> (Int,[Int])
invAdd 0 (0,ds) = (0,1:ds)
invAdd 0 (1,ds) = (1,0:ds)
invAdd 1 (0,ds) = (0,0:ds)
invAdd 1 (1,ds) = (0,1:ds)

现在如果你只有一个数字，那么整个操作将是：

twos :: [Int] -> (Int,[Int])
twos (d:[]) = invAdd d (1,[])

(1,[]) 满足 1 除了翻转位之外还必须添加的内容。

如果你有一个以上的数字你需要向下递归

twos (d:ds) = invAdd d (twos ds)

这给出了二进制补码加上最后的进位。如果您不想看到进位，请使用 snd:

*Main> snd (twos [0,0,0,1,1,0,1,0])
[1,1,1,0,0,1,1,0]

您也可以使用 Bool 轻松地做到这一点，因为没有使用数学函数，并且在 invAdd 中所有情况都被明确拼写出来。

二进制补码尽可能简单，无需高阶函数

Two's Complement as simple as possible without higher order functions

haskell

twos-complement