在Haskell中反转二进制数

Question

我已经为二进制数定义了数据类型,如下所示

data Bin = Nil | O Bin | I Bin 
           deriving (Show, Eq)

我想定义一个函数,reverse :: Bin -> Bin以便当我给出输入时

reverse (I (O (I (I Nil))))我应该得到 I (I (O (I Nil)))那个意味着作为输入反转的输出,任何身体请告诉我如何能做到这一点？

Answer 1

你为什么这样做？为什么不是这样的:

data Bit = I | O
newtype Bin = List Bit

然后你可以直接使用Prelude的反向操作......

编辑 Prelude函数的简单替换:

reverse x = rev x []
  where
    rev [] a = a
    rev (x:xs) a = rev xs (x:a)

收益率:

reverse x = rev x Nil
  where
    rev Nil a = a
    rev (I xs) a = rev xs (I a)
    rev (O xs) a = rev xs (O a)

问题是,你的类型与列表类型非常相似:

data List a = a : (List a) | []

因此List例程的逻辑直接应用于您的类型.

Answer 2

data Bin = Nil | O Bin | I Bin deriving (Show, Eq)
reverse :: Bin -> Bin
reverse x = rev Nil x
    where
        rev a Nil = a
        rev a ( O b ) = rev ( O a ) b
        rev a ( I b ) = rev ( I a ) b