在Haskell中用'：'代替'++'。錯誤

data Tree a = Node a (Tree a) (Tree a) | Empty 


toList :: (Tree a) -> [a] 
toList (Node v l r) = (toList l) ++ [v] ++ (toList r) 
toList Empty = []

正如我們所知，它不是最優的，因爲每個++連接O（n）操作鏈接列表。替代解決方案是使用:而不是++。但是由於事實toList Empty = []而導致錯誤。那麼如何使我的解決方案最優化？在Haskell中用'：'代替'++'。錯誤

來源

2016-03-19 Gilgamesz

「：」和「++」具有不同的類型並且提供不同的功能。如果你願意，你可以寫'toList l ++（v：toList r）'，但是你不能用'：'來表示兩個列表。 – Mephy

@Mephy：正確。順便說一下，因爲「：」和「++」都是「infixr 5」，所以不需要。 – leftaroundabout

您需要*重新關聯* ++應用程序，直到每個應用程序的左操作數爲單例。然後你可以（基本上）用'：'替換每個。 – dfeuer

你不能直接這樣做，因爲:只能將單個元素加到列表中。但是在兩個孩子分支你通常會給出多個元素。緩慢的遞歸實現是需要來解決這個問題！

所以，要走的路是使用一個更高效的串聯操作的容器！這在圖書館中是可用的，例如， sequence。但有一個容器類型，你可以非常快速地釀自己：

newtype DList a = DList { getDList :: [a] -> [a] } 

instance Monoid (DList a) where 
    mempty = DList id 
    mappend (DList l1) (DList l2) = DList $ l1 . l2 

singletonD :: a -> DList a 
singletonD x = DList (x:)

有了這個，你可以做

toDList :: Tree a -> DList a 
toDList (Node v l r) = toDList l <> singletonD v <> toDList r 
toDList Empty = mempty

這是你定義的精確翻譯，但它不會有與連接普通列表時相同的性能問題。

因爲這些difference lists是很容易實現，這是相當普遍在Haskell只是做它內聯沒有再提起：

toList :: (Tree a) -> [a] 
toList t = tdl t [] 
where tdl (Node v l r) = toList l . (v:) . tdl r 
     tdl Empty = id

來源

2016-03-20 00:27:22 leftaroundabout

你需要把東西放在一起不同，以實現自己的目標。您不能只用:替換++。試試這個：

toList t = toListPlus t [] 
toListPlus :: Tree a -> [a] -> [a]

toListPlus t xs應該產生toList t ++ xs，但遞歸調用實施toListPlus，不使用++或toList。讓我們通過它。基本情況很容易：

toListPlus Empty xs = xs

遞歸情況也不算太差。我們希望將左側子樹轉換爲列表，並在其後粘貼其他內容：

toListPlus (Node v l r) xs = 
    toListPlus l ???

後來是什麼？根，然後將右子樹的結果，然後不管大幹快上上漲：

toListPlus (Node v l r) xs = 
    toListPlus l (v : toListPlus r xs)

此功能使用隱式堆棧跟蹤剩餘的工作。這可能是最有效的方法。如果你想要的話，你可以使用拉鍊風格的表示來顯示棧。

這個解決方案與左邊所描述的方法有什麼關係？那麼，他們實際上是一樣的。我們可以看到，通過移動列表參數：

toListPlus Empty = \xs -> xs 
toListPlus (Node v l r) 
    = \xs -> toListPlus l (v : toListPlus r xs) 
    = toListPlus l . (v :) . toListPlus r

來源

2016-03-20 00:35:39 dfeuer

在Haskell中用'：'代替'++'。錯誤

回答

相關問題