Haskell实现inserter函数构建树报错：类型不匹配问题及解决

原代码及错误信息 #

原代码：

data Tree = EmptyTree | Node Integer Tree Tree deriving (Show, Eq, Ord)

insertElement x EmptyTree = Node x EmptyTree EmptyTree -- BASE CASE
insertElement x (Node a left right) = if x == a -- DO NOTHING
    then (Node x left right)
    else if x < a -- INSERT TO LEFT
    then (Node a (insertElement x left) right)
    else -- INSERT TO RIGHT
    Node a left (insertElement x right)

inserter (x:list) = insertElement x (insertElement (inserter (list)) (EmptyTree))

加载时出现的错误：

Couldn't match type `Tree' with `Integer'
    Expected type: [Integer] -> Integer
      Actual type: [Integer] -> Tree

问题原因 #

insertElement的参数类型是Integer -> Tree -> Tree，但原代码里insertElement (inserter (list)) (EmptyTree)把inserter list返回的Tree作为第一个参数传给insertElement，导致类型不匹配——第一个参数需要Integer，却传入了Tree。同时原代码缺少空列表的基例，递归无法正常终止。

修改后的inserter函数 #

inserter [] = EmptyTree
inserter (x:list) = insertElement x (inserter list)

说明 #

• 新增inserter [] = EmptyTree作为基例，处理空列表输入，返回空树
• 递归逻辑改为将当前元素x插入到inserter list生成的树中，inserter list返回的Tree正好匹配insertElement的第二个参数类型，x匹配第一个参数的Integer类型，完全符合函数签名要求

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