忽略类型声明，直到最后一次递归

Question

我正在尝试编写一个函数，该函数将元组中的数据转换为用于运行长度编码的程序的字符串。我以前使用append编写过它，但是我一直在尝试改进它。

函数解码应获取一个元组列表，然后返回一个字符串。

例子

> decode [('h',7),('s',3),('g',1)]
"hhhhhhhsssg"
> decode [('z',9),('z',1)]
"zzzzzzzzzz"

最初，我使用append函数以递归方式编写了该函数，但效果不错，但并非最佳选择，我目前的实现看起来像这样：

decode :: [(Char,Int)] -> String
decode [] = []
decode x = concat(replicate (snd (head x)) (fst (head x)) : decode (tail x)

然后这给了我一个编译错误，因为该decode (tail x)部分不适合我不能更改的类型声明。我确定这是一种不好的做法，但是有没有办法让程序在完成递归之前不符合类型声明？

    * Couldn't match type `Char' with `[Char]'
      Expected type: [[Char]]
        Actual type: String
    * In the second argument of `(:)', namely `decode (tail x)'
      In the first argument of `concat', namely
        `(replicate (snd (head x)) (fst (head x)) : decode (tail x))'
      In the expression:
        concat (replicate (snd (head x)) (fst (head x)) : decode (tail x))
   |
35 | decode x = concat(replicate (snd (head x)) (fst (head x)) : decode (tail x))
   |

Answer 1

代码的问题在于:cons函数。它的类型是a -> [a] -> [a]，这意味着它将单个元素放在列表的开头。在您的情况下，您尝试将列表（复制的元素）添加到列表中，这就是为什么++可行（类型为[a] -> [a] -> [a]）的原因。没有方法可以简单地“忽略类型”，因为类型与haskell编译/运行方式交织在一起，这是一件好事，在这种情况下，编译器使您避免了其他lang中的“类型不匹配”运行时错误。

如果要使用编写代码:，则不能使用replicate，您需要制作一个辅助的递归函数来重复char，并在零时解码列表的其余部分：

decodeA :: [(Char,Int)] -> String
decodeA [] = []
decodeA ((c,n):xs) = rep c n
           where rep ch 0 = decodeA xs
                 rep ch m = ch : (rep ch (m-1))

现在，使用以下方法可以找到更清晰的解决方案++：

decodeB :: [(Char,Int)] -> String
decodeB [] = []
decodeB ((c,n):xs) = replicate n c ++ decodeB xs

并对两个解决方案进行基准测试，第二个方法不仅更清晰，而且速度更快：

基准代码

t1 = [('h',7),('s',3),('g',1)]
t2 = [('z',9),('z',1)]
t3 = [('a',10000), ('b',10000), ('c',10000),('d',10000), ('e',10000), ('f',10000)]

main = defaultMain [
  bgroup "decode" [ bench "t1 decodeA" $ nf decodeA t1
                  , bench "t2 decodeA" $ nf decodeA t2
                  , bench "t3 decodeA" $ nf decodeA t3
                  , bench "t1 decodeB" $ nf decodeB t1
                  , bench "t2 decodeB" $ nf decodeB t2
                  , bench "t3 decodeB" $ nf decodeB t3
                   ]

基准结果

benchmarking decode/t1 decodeA
time                 7.152 ?s   (7.093 ?s .. 7.225 ?s)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 7.129 ?s   (7.091 ?s .. 7.216 ?s)
std dev              190.6 ns   (69.72 ns .. 354.5 ns)
variance introduced by outliers: 31% (moderately inflated)

benchmarking decode/t2 decodeA
time                 6.283 ?s   (6.235 ?s .. 6.340 ?s)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 6.268 ?s   (6.239 ?s .. 6.326 ?s)
std dev              137.8 ns   (71.41 ns .. 211.7 ns)
variance introduced by outliers: 24% (moderately inflated)

benchmarking decode/t3 decodeA
time                 32.67 ms   (32.31 ms .. 33.08 ms)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 32.68 ms   (32.53 ms .. 32.93 ms)
std dev              406.7 ?s   (238.0 ?s .. 613.5 ?s)

benchmarking decode/t1 decodeB
time                 1.208 ?s   (1.199 ?s .. 1.220 ?s)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 1.212 ?s   (1.204 ?s .. 1.228 ?s)
std dev              34.30 ns   (19.59 ns .. 62.18 ns)
variance introduced by outliers: 38% (moderately inflated)

benchmarking decode/t2 decodeB
time                 923.6 ns   (916.9 ns .. 931.6 ns)
                     0.999 R²   (0.997 R² .. 1.000 R²)
mean                 923.8 ns   (917.0 ns .. 950.3 ns)
std dev              38.01 ns   (9.440 ns .. 84.90 ns)
variance introduced by outliers: 57% (severely inflated)

benchmarking decode/t3 decodeB
time                 1.250 ms   (1.229 ms .. 1.274 ms)
                     0.997 R²   (0.995 R² .. 0.999 R²)
mean                 1.248 ms   (1.239 ms .. 1.269 ms)
std dev              47.55 ?s   (32.05 ?s .. 78.69 ?s)
variance introduced by outliers: 26% (moderately inflated)

在这种情况下，decodeB比decodeA最大测试用例快32倍