Haskell中AssocList类型的doubleMap函数实现错误修复咨询

定义的数据类型 #

data AssocList k a = 
     Nil
   | Cons(k,a,AssocList k a)
   deriving (Eq,Show)

原错误实现 #

doubleMap :: (k -> a -> (k',a')) -> AssocList k a -> AssocList k' a'
doubleMap f Nil = Nil
doubleMap f (Cons(k, a, t)) = Cons(k , f k a, doubleMap f t)

报错信息 #

Couldn't match type ‘a'’ with ‘(k', a')’
      Expected: AssocList k (k', a')
        Actual: AssocList k' a'

问题分析与正确实现 #

原代码的核心问题是没有正确处理高阶函数f的返回值：f k a返回的是元组(k',a')，但原代码直接把这个元组作为Cons的第二个参数，同时错误保留了原k作为第一个参数，导致类型不匹配。

正确实现需要先解构f返回的元组，提取出新的键和值，再传入Cons构造器：

doubleMap :: (k -> a -> (k',a')) -> AssocList k a -> AssocList k' a'
doubleMap f Nil = Nil
doubleMap f (Cons(k, a, t)) = let (newK, newA) = f k a
                               in Cons(newK, newA, doubleMap f t)

验证示例 #

调用代码：

doubleMap (\x y -> (x,x+y)) (Cons(1,2,Cons(3,4,Nil)))

将得到预期结果：

Cons(1,3,Cons(3,7,Nil))

内容的提问来源于stack exchange，提问作者chen