代码之家  ›  专栏  ›  技术社区  ›  Bercovici Adrian

Concat方法类型说明

  •  -1
  • Bercovici Adrian  · 技术社区  · 6 年前

    有人能给我解释一下为什么我的concat实现中的源列表类型不起作用吗?

    conc::[[a]]->[a]
    conc xs@(x1:xs')=foldr (:) [] xs
    

    为什么源列表应为 [a] 而不是 [[a]] ? 如果我想继续 [[1,2],[3,4]] 不是那种类型 [[a]] [答] 元素类型为 [答] .

    我得到以下错误:

    Couldn't match type `a' with `[a]'
          `a' is a rigid type variable bound by
            the type signature for:
              conc :: forall a. [[a]] -> [a]
    
    2 回复  |  直到 6 年前
        1
  •  4
  •   Igor Drozdov    6 年前

    实际上编译器在错误中显示了有用的提示(实际上比您发布的消息低几行)

    Expected type: [a]
    Actual type: [[a]]
    

    在下面的代码中,参数的类型确实是 [[a]] ,但结果也是类型 [[a]] ,它与类型定义冲突:

    conc :: [[a]] -> [a]
    conc xs@(x1:xs') = foldr (:) [] xs
    

    xs 代码中的类型为 [[a]] 您可以使用 foldr 并添加类型为 [a] 添加到列表。因此,您将收到一个类型列表 [[a]] .

        2
  •  1
  •   Will Ness Derri Leahy    6 年前

    foldr (:) [] xs == xs True 对于任何 xs . 这意味着 foldr (:) [] 是列表上的标识函数。这一事实广为人知,是哈斯克尔传说的一部分,以至于 foldr(:)[] 自动读取为 id 在一个有经验的Haskell程序员的头脑中。

    一种看的方式 foldr c n 替换“cons”(即。 (:) )使用 c 以及 [] 具有 n ,在给定列表中。更换 (:) 具有 (:) [] 具有 [] 显然不会改变什么:

    [a, b, ..., z]  ==>  a : b : ... : z : []  ==  [a, b, ..., z]
    

    更换 (:) s与 (++) 另一方面,将把输入列表中的所有列表连接在一起,形成一个:

    [a, b, ..., z]  ==>  a ++ b ++ ... ++ z
    

    这就是你想要实现的。

    所以正确的实现 concat 具有 foldr foldr (++) [] .