與非二叉樹

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]]