哈斯克尔.(也许是)vs a

Question

belongs :: Eq(a) => a -> [a] -> Maybe a

belongs e (h:t) = if ( h == e) then Nothing else belongs e t
belongs e [] = Just e


nub :: Eq(a) => [a] -> [a]
nub l = nub' l [] 
    where 
        nub' [] new_list = new_list
        nub' (h:t) new_list = nub' t (new_list ++ [(belongs h new_list)])

错误:

Occurs check: cannot construct the infinite type: a0 = Maybe a0
Expected type: [a0]
  Actual type: [Maybe a0]
In the second argument of `belongs', namely `new_list'
In the expression: (belongs h new_list)
In the second argument of `(++)', namely `[(belongs h new_list)]'

我理解错误.但我不知道如何修复它.我不明白为什么Maybe Eq(a)不能配a.那么如何修复它.如果可能,我想在这里使用Maybe.

Answer 1

想象一下如果你实例a化为具体类型会在该行上发生什么,例如Int.belongs会给你一个Maybe Int你要包装的东西,[Maybe Int]然后立即尝试连接它new_list,因为你传递给它belongs必须是一个[Int].这就是编译器告诉你的; 您同时尝试将一个值用作两种不同的类型.

要解决此问题,您可以匹配belongs将其包装在列表中并附加它之前的结果.如果它Just a附加了a.如果Nothing不附加任何东西.旁注:将元素附加到列表的后面是非常低效的*.您可能希望将所有内容添加到前面,然后在最后反转.

你还有一个问题.您定义的nub'同时处理new_list类型Maybe [a](通过返回new_list一个案例)和类型[Maybe a](如果您修复上述内容).编辑:编辑后不再编辑.

*正如@WillNess所指出的,这是一个小说.由于Haskell的普遍存在的懒惰,大多数通常被称为"昂贵"的操作在创建时并不昂贵,而是仅在使用元素时.由于不正确的关联操作顺序导致元素的检索导致线性时间成本,因此发生了大量的二次时间减速与最佳线性时间操作.他的回答是链接是一个很好的解释.