Haskell十进制到二进制

问题描述 投票:4回答:5

我正在尝试构建一个将Decimal(Int)转换为二进制数的函数。不幸的是,除了在Java中,不可能在haskell中将int除以2。我对函数式编程非常陌生,因此问题可能很简单。到目前为止,我找不到该问题的另一种解决方案,但是这是我的第一次尝试:

 fromDecimal :: Int -> [Int]

fromDecimal 0 = [0]
fromDecimal n = if (mod n 2 == 0) then 
                do

                0:fromDecimal(n/2) 

                else 
                do  
                1:fromDecimal(n/2) 

我以前在这里有一个Java实现:

   public void fromDecimal(int decimal){
    for (int i=0;i<values.length;i++){

        if(decimal % 2 = 0)
        values[i]=true ; 
        decimal = decimal/ 2;
        else {values[i]= false;
        }       }
}

希望这将有助于找到解决方案!

haskell binary decimal
5个回答
8
投票

您的解决方案存在一些问题。首先,我建议not使用do atall,直到您了解do的作用。在这里,我们根本不需要do

不幸的是,除了在Java中,不可能在haskell中将int除以2。

实际上是,但是/运算符(实际上是(/)函数)的类型为(/) :: Fractional a => a -> a -> a(/) :: Fractional a => a -> a -> a不是Int。您可以使用Fractional执行整数除法。

因此,代码如下:

div :: Integral a => a -> a -> a

但是我们绝对可以使它更加优雅。 div :: Integral a => a -> a -> a只能产生两个结果:fromDecimal :: Int -> [Int] fromDecimal 0 = [0] fromDecimal n = if (mod n 2 == 0) then 0:fromDecimal (div n 2) else 1:fromDecimal (div n 2)mod n 2,而这些正是我们在0运算符左侧使用的结果。

所以我们根本不需要使用1-(:)-if

then

可能仍然不是您想要的:这里我们写二进制值,使得最后一个元素是最重要的一个。此函数将添加一个tailing零,这不会造成语义上的差异(由于该顺序),但也不美观。

如果给定值不为零,我们可以定义一个忽略此零的函数else,例如:

fromDecimal :: Int -> [Int]
fromDecimal 0 = [0]
fromDecimal n = mod n 2 : fromDecimal (div n 2)

但是,如果我们想首先写入最高有效位(因此与写入十进制数字的顺序相同),那么我们就必须反转结果。我们可以通过使用accumulator

来做到这一点。
go

4
投票

您不能在Haskell中使用fromDecimal :: Int -> [Int] fromDecimal 0 = [0] fromDecimal n = go n where go 0 = [] go k = mod k 2 : go (div k 2)整数-除法不是根据整数定义的!对于积分除法,请使用fromDecimal :: Int -> [Int] fromDecimal 0 = [0] fromDecimal n = go n [] where go 0 r = r go k rs = go (div k 2) (mod k 2:rs)功能,但更适合的是/(附带免费提供的div)。

此外,您将获得反向输出,因此您可以在之后手动divMod,或将更多内存效率的版本与累加器一起使用:

mod

reverse将为您提供decToBin :: Int -> [Int] decToBin = go [] where go acc 0 = acc go acc n = let (d, m) = n `divMod` 2 in go (m : acc) d 的空白列表。如果列表为空,则可以手动添加它:

go

1
投票

仔细考虑算法的工作原理。它从2⁰开始,因此它将生成比我们通常认为的要低的位,即最低有效位在前。您的算法只能表示非负二进制整数。

0

在Haskell中,当我们反向生成列表时,请继续执行此操作,但最后将结果decToBin = (\l -> if null l then [0] else l) . go [] where ... 。这样做的原因是要整理一个列表(将新项目粘贴在fromDecimal :: Int -> [Int] fromDecimal d | d < 0 = error "Must be non-negative" | d == 0 = [0] | otherwise = reverse (go d) where go 0 = [] go d = d `rem` 2 : go (d `div` 2) 的最前面)的成本是恒定的,而最后reverse的成本是线性的,但是追加:的成本是二次的。] >

常见的Haskell样式是有一个名为reverse的私有内部循环,当外部函数对参数满意时,将应用该内部循环。基本情况是当++达到零时以空列表终止。否则,我们将当前余数取模2,然后将go减半并截断。

没有零的特殊情况,d将是空列表,而不是d


1
投票

二进制数字通常是字符串,在计算中并未真正使用。字符串也不太复杂。


0
投票
导入Data.Listdec2bin x =反向$ binstr $展开ndiv x哪里binstr =地图(\ x->“ 01” !! x)例子(a,b)=(b,a)ndiv n =的情况n0->无_-> Just $ exch $ divMod n 2
© www.soinside.com 2019 - 2024. All rights reserved.