如何在Haskell中实现十进制到二进制函数
我在Haskell中实现了一个二进制到十进制的函数,目前我正在开发一个将十进制转换为二进制值的函数。 (我知道这些功能在某些地方是可用的,虽然它们不是Prelude.hs的一部分)如何在Haskell中实现十进制到二进制函数
我想出了下面的C语言程序代码,但是我很难适应它的功能范例。
while (n > 0)
{
if (n % 2 == 1)
str = str + "1";
else
str = str + "0";
n = n/2;
}
我刚刚冒险进入Haskell的函数式编程,所以我对功能思维方式很陌生。我试图使用递归和列表理解,但我不确定如何正确放置守卫和逻辑,因为这涉及多个条件。我使用一个Int列表来保存单独的二进制位。
--Decimal to binary
toBin:: Int -> [Int]
toBin 0 = [0]
toBin n | (n % 2 == 1) =
|(n % 2 == 0) =
我明白了,上面的模式可以让程序选择保护和结束评估函数。我在这里错了吗?
下面是我想出原始递归来将任何基数(小于10,代替2)转换为小数。
toDecimal :: [Int] -> Int
toDecimal [] = 0
toDecimal (x:xs) = (x * 2 ^(length xs)) + bin xs
谢谢先进。
有没有%
操作;你可能会寻找替代`mod`
:
toBin 0 = [0]
toBin n | n `mod` 2 == 1 = ...
| n `mod` 2 == 0 = ...
逆天让你的函数的多个分支之间进行选择。在这种情况下,如果其相应条件为真,则每个...
将是toBin n
的结果。为了两个列表追加在一起,你可以使用++
运营商,并`div`
对应于整数除法:
toBin 0 = [0]
toBin n | n `mod` 2 == 1 = toBin (n `div` 2) ++ [1]
| n `mod` 2 == 0 = toBin (n `div` 2) ++ [0]
然而,这有几个问题。首先,它始终以0
开始,这是多余的;另外,使用++ [1]
的速度很慢,因为它必须通过整个列表来添加一个元素到最后;最好是预先每个元素,因为我们去,然后反向结果在最后。
要解决这两个东西,我们会达到分裂toBin
为主要功能和辅助功能:
toBin 0 = [0]
toBin n = reverse (helper n)
helper 0 = []
helper n | n `mod` 2 == 1 = 1 : helper (n `div` 2)
| n `mod` 2 == 0 = 0 : helper (n `div` 2)
在这个版本中,我们使用:
运营商,需要一个值和一个列表,并返回带有预置在开头的值的列表。我们还会在我们的帮助器中返回0的空结果,并在toBin
中处理0的情况,以便结果中不再有0。
我们可以完全跳过警卫,因为我们只写一遍的n `mod` 2
结果的右侧简化helper
的代码:
helper 0 = []
helper n = (n `mod` 2) : helper (n `div` 2)
最后,还有,做了div
和功能一个在一个mod
去,从而可以更高效:
helper 0 = []
helper n = let (q,r) = n `divMod` 2 in r : helper q
作为附加的注释,这并不能真正十进制转换为二进制,将其转换为二进制的整数; Haskell实现不太可能以十进制格式存储整数,尽管它们是以该格式书写和打印的。要编写十进制到二进制的完整转换,需要一个将十进制字符串解析为整数的函数。
toBin :: Int -> [Int]
toBin 0 = [0]
toBin 1 = [1]
toBin n
| n `mod` 2 == 0 = toBin (n `div` 2) ++ [0]
| otherwise = toBin (n `div` 2) ++ [1]
0和1是微不足道的情况。 如果n是偶数,那么你应该追加零到最后,否则你追加一个。 这是很好的做法在你的最后守卫表达式捕捉一切(这就是为什么我使用,否则这是一样的真)
toBinary :: Int -> [ Int ]
toBinary 0 = [ 0 ]
toBinary n = toBinary (n `quot` 2) ++ [ n `rem` 2 ]
您可以从Data.Char
使用unfoldr
函数从Data.List
模块和intToDigit
:
dec2bin :: Int -> [Char]
dec2bin = reverse . map intToDigit . unfoldr (\x -> if x==0 then Nothing else Just(rem x 2, div x 2))
这里发生的是unfoldr
功能过程与所提供的匿名函数的输入,直到它返回Nothing
,同时将第一个值Just
汇总在一个列表中。此列表包含Int
s,因此需要使用intToDigit
将其转换为Char
,然后进行反转,因为它们是按相反顺序收集的。一个列表Char
s是Haskell中的一个字符串,所以你完成了。
“需要将一个十进制字符串解析为一个整数的函数” - 就像,erm,'read'? – 2012-02-06 20:02:06
@DanielFischer:是的,但大概是OP试图从头开始实现这一点:)毕竟,'showIntAtBase'也存在。 – ehird 2012-02-06 20:04:22