与非二叉树

Question

函数返回的树我有一个非二叉树：

data MultTree b = DataNode b | IndexNode Int Int [MultTree b] deriving (Show) 

注意：DataNode's像对待叶子和IndexNode's状分枝。

现在我尽量做到在IndexNode较小Int值设置为子树的DataNode最小值和较大Int值设置为子树的DataNode最大的价值。

为IndexNode's不小Int值设置为​​子树和更大的一个maxBound::Int

这是我的功能至今：

dataInterval:: (Ord a) => MultTree a -> MultTree a 
dataInterval (DataNode x) = (DataNode x) 
dataInterval(IndexNode x y []) 
     | x > y = (IndexNode (maxBound :: Int) (minBound :: Int) []) 
     | x < y = (IndexNode (minBound :: Int) (maxBound :: Int) []) 
     | x == y = (IndexNode x y []) 
datenInterval (IndexNode x y subtrees) 
     | x > y = (IndexNode (maxValue subtrees) (minValue subtrees) (map (dataInterval subtrees))) 
     | x < y = (IndexNode (minValue subtrees) (maxValue subtrees) (map (dataInterval subtrees))) 
     | x == y = (IndexNode x y (map (dataInterval subtrees))) 

必须调用函数dataInterval递归。

现在我不知道该怎么做，因为dataInterval预计一棵树，但不知何故，我要打电话的完整列表。 dataInterval不允许。

问题：我怎样才能实现在使用列表中的子树调用dataInterval递归？那么subtrees列表中的每棵树会被调用？

我想可能是这样地图的一些功能，但是返回子树而不是列表。

此刻的错误信息看起来像这样：

无法比拟预期型MultTree A2 与实际类型[MultTree A] *在datenIntervalle的第一个参数，即子树 在地图中，即（datenIntervalle子树） 的第一个参数在IndexNode的第三个参数，即 （地图（datenIntervalle子树））

样本树&完整代码：

t2 :: MultTree Int 
t2 = IndexNode 3 42 [IndexNode 7 8 [DataNode 3, DataNode 5, DataNode 7, DataNode 9], DataNode 6, IndexNode 10 23 [DataNode 99, DataNode 78, DataNode 24]] 

dataList:: MultTree a -> [a] 
dataList(DataNode x) = [x] 
dataList(IndexNode _ _ subtress) = concat' (map dataList subtress) 

maxValue :: (Ord a) => MultTree a -> a 
maxValue tree = maximum (dataList tree) 

minValue :: (Ord a) => MultTree a -> a 
minValue tree = minimum (dataList tree) 

dataInterval:: (Ord a) => MultTree a -> MultTree a 
dataInterval(DataNode x) = (DataNode x) 
dataInterval(IndexNode x y []) 
     | x > y = (IndexNode (maxBound :: Int) (minBound :: Int) []) 
     | x < y = (IndexNode (minBound :: Int) (maxBound :: Int) []) 
     | x == y = (IndexNode x y []) 
dataInterval(IndexNode x y subtrees) 
     | x > y = (IndexNode (maxValue subtrees) (minValue subtrees) (map (dataInterval subtrees))) 
     | x < y = (IndexNode (minValue subtrees) (maxValue subtrees) (map (dataInterval subtrees))) 
     | x == y = (IndexNode x y (map (dataInterval subtrees))) 

Answer 1

我将张贴在你的问题也回答你最后的评论答案：

我已删除了弯曲托架，并得到一个错误。如果您发布了一些代码，我将不胜感激。我的错误消息：无法与实际类型[MultTree a]匹配的预期类型MultTree Int'

此处的问题是您指定的类型为minBound :: Int。但是在你的功能类型中，你说你有任何类型的树a这就是Ord。

dataInterval:: (Ord a) => MultTree a -> MultTree a 

所以，Int不等于a。如果你不希望你的树是多态的，例如你可以只有dataInterval :: MultTree Int -> MultTree Int。 但这不是最好的解决方案。对于多态类型，可以使用minBound和maxBound，但是您需要将Bounded约束添加到类型签名中的a。你不需要在你的函数中指定minBound的类型，因为Haskell有类型推断。因此，这里是完整的工作示例（我也删除了一些()因为哈斯克尔不Lisp的）：

data MultTree b = DataNode b | IndexNode b b [MultTree b] deriving (Show) 

t2 :: MultTree Int 
t2 = IndexNode 3 42 [ IndexNode 7 8 [ DataNode 3 
            , DataNode 5 
            , DataNode 7 
            , DataNode 9 
            ] 
        , DataNode 6 
        , IndexNode 10 23 [ DataNode 99 
             , DataNode 78 
             , DataNode 24 
             ] 
        ] 

dataList :: MultTree a -> [a] 
dataList (DataNode x)    = [x] 
dataList (IndexNode _ _ subtrees) = flattenSubtrees subtrees 

flattenSubtrees :: [MultTree a] -> [a] 
flattenSubtrees = concatMap dataList 

maxValue :: Ord a => [MultTree a] -> a 
maxValue trees = maximum (flattenSubtrees trees) 

minValue :: Ord a => [MultTree a] -> a 
minValue trees = minimum (flattenSubtrees trees) 

dataInterval :: (Bounded a, Ord a) => MultTree a -> MultTree a 
dataInterval (DataNode x) = DataNode x 
dataInterval node@(IndexNode x y []) 
     | x > y = IndexNode maxBound minBound [] 
     | x < y = IndexNode minBound maxBound [] 
     | x == y = node 
dataInterval (IndexNode x y subtrees) 
     | x > y = IndexNode (maxValue subtrees) (minValue subtrees) mappedSubtrees 
     | x < y = IndexNode (minValue subtrees) (maxValue subtrees) mappedSubtrees 
     | x == y = IndexNode x y mappedSubtrees 
    where 
    mappedSubtrees = map dataInterval subtrees 

我要注意，这个功能的实现是没有效率的。因为每次需要评估最小值和最大值时遍历整棵树，而在找到结果subtrees后，实际上它只能遍历最后一层。函数调用对t2结果是：

ghci> dataInterval t2 
IndexNode 3 99 [IndexNode 3 9 [DataNode 3,DataNode 5,DataNode 7, 
DataNode 9],DataNode 6,IndexNode 24 99 [DataNode 99,DataNode 78, 
DataNode 24]]