haskell 带折叠的二进制到十进制

fwzugrvs  于 2022-12-19  发布在  其他
关注(0)|答案(1)|浏览(162)

嘿伙计们我们有个问题:我们应该写一个函数bin2dez,条件是:获取一个自然数,并以字符串形式返回该自然数的十进制表示形式。2使用fold。

bin2dez :: (Int -> [Int] -> [Int]) -> [Int] -> Int -> [Int] 
bin2dez xs = foldr f 0 
  where
  f = bin1dez (drehe xs) 
  bin1dez :: [Int] -> Int
  bin1dez [] = 0
  bin1dez (x:xs) = 2*(bin1dez xs) + x
  drehe [] = []
  drehe (x:xs) = drehe xs ++ [x]

我搞不懂这里的fold,因为你需要一个函数f和一个中性元素,中性元素应该是0,但是我怎么把它输入到Haskell里,有人能帮我吗,谢谢

bin2dez :: [Int] -> Int
bin2dez xs = foldr f b
where b = 0
      f result x = bin1dez (drehe xs) 
  bin1dez [] = 0
  bin1dez = 2*(bin1dez xs) + x
  drehe [] = []
  drehe (x:xs) = drehe xs ++ [x]
2wnc66cl

2wnc66cl1#

当你被要求“使用fold”时,你的想法是用fold来替换输入结构上的递归。例如,如果你有一个递归来对一列数字求和:

mysum (x:xs) = x + mysum xs
mysum [] = 0

并且你被要求“使用一个fold”,你应该分离出空列表的基本情况(result 0)和用于组合列表头的计算以及用于组合列表尾的递归计算结果:

f head_of_list result_for_tail = head_of_list + result_for_tail

用fold把它写成一个非递归函数

mysum xs = foldr f b xs
  where b = 0          -- base case
        f h t = h + t  -- combine head with result for tail

或者更简单地说:

mysum = foldr (+) 0

您已经有一个递归的二进制到十进制转换函数:

bin1dez :: [Int] -> Int
bin1dez [] = 0
bin1dez (x:xs) = 2*(bin1dez xs) + x

例如,

> bin1dez [1,1,0,1]   -- least significant bit first
11

要“使用fold”,您需要识别基本情况(easy),并分离出组合头部x和递归计算的尾部结果bin1dez xs的函数。也就是说,您需要派生一个(非递归)函数:

f x result_for_xs = ...expression using x and result_for_xs...

使用基本情况和该函数,您将能够定义您的文件夹。
如果您的二进制表示是“最高有效位优先”(看起来是这样的,给出了你的drehe函数),你可能需要考虑 left fold函数foldl,它接受一个列表的空“开始”的基本情况,以及一个组合列表初始部分结果的函数(第一个参数)与列表中的下一个元素(第二个参数)进行比较,以产生列表的初始段的结果。
换句话说,如果您有一个最低有效位优先的右折解:

bin2dez = foldr f b
  where b = ...
        f x result = ...

> bin2dez [1,1,0,1]
11

可以将其转换为最高有效位优先的左折叠解决方案,而不必颠倒列表:

bin2dez = foldl f b
  where b = ...same as above...
        f result x = ...same function body...
          ^^^^^^^^- swap these arguments

> bin2dez [1,1,0,1]
13

这个问题的额外部分“将数字的十进制表示返回为字符串”很奇怪。你通常不会对fold执行此操作。(它实际上是一个“展开”。)如果你不允许对fold的结果调用show,我不确定你的老师实际上想让你在这里做什么。

相关问题