Ağaç geçişi inorder tail recursion

Question

Kuyruk yinelemeyi kullanarak düz bir şekilde enine ağaç kesiti uyguladım mı?

inorder (Leaf n) temp = n:temp 
inorder (Node (n, left, right)) temp = inorder left (n:inorder right temp) 
inorder :: Tree a -> [a] -> [a] 

Ağacı

data Tree a = Leaf a | Node (a, Tree a, Tree a) deriving Show 

olarak ilan ve döndürür bir nontail pozisyonda yinelemeli çağrı inorder right temp çünkü three = Node (1, Leaf 2, Leaf 3)

Answer 1

Bu teknik olarak kuyruk özyinelemeli değildir çağrı inorder three [] üzerinde [2,1,3]. Bunu düzeltmenin bir yolu, sürekliliklerle olurdu. Daha önce olduğu gibi bir akümülatör alan bir fonksiyon yazıyorsunuz, fakat sadece bir liste olan akümülatörden ziyade, hesaplamada yapılacak işi temsil eden bir fonksiyon. Bu, kuyruğa girmeyen bir arama yapmak ve sadece geri dönmek yerine, aramamızı istediğiniz zaman devam edebilmemiz için her zaman arayabiliriz.

inorder = go id 
    where go :: ([a] -> r) -> Tree a -> r 
      go k Leaf = k [] 
      go k (Node a l r) = go l (\ls -> go r (\rs -> k $ ls ++ n : rs)) 

İşte her çağrı gerektiği gibi bir kuyruk çağrıdır ama kuadratik maliyetler bizi iterek her seviyede bir ++ operasyonu gerektirdiğinden oldukça innefficient bu. Daha verimli bir algoritma bu operasyonların hepsi O(1) toList haricinde olduklarını açık bir listesini oluşturmaya ve bunun yerine bir fark listesi oluşturmak, beton yapı üzerinde inşaatı geciktirerek ve daha verimli algoritmasını

type Diff a = [a] -> [a] -- A difference list is just a function 

nil :: Diff a 
nil xs = xs 

cons :: a -> Diff a -> Diff a 
cons a d = (:) a . d 

append :: Diff a -> Diff a -> Diff a 
append xs ys = xs . ys 

toList :: Diff a -> a 
toList xs = xs [] 

Not vererek önleyeceğini giriş sayısı O(n) olan. Burada önemli nokta fark listeleri çok biz ettik fonksiyonların karşılıksız uygulamasıyla, artık

inorder = go toList 
    where go :: (Diff a -> r) -> Tree a -> r 
      go k Leaf = k nil 
      go k (Node a l r) = 
      go l (\ls -> go r (\rs -> k $ ls `append` cons n rs)) 

sona Ve böylece bizim algoritma bu inşa edeceğiz eklemek ve en somut listesini oluşturmak için ucuz ve kolay olmasıdır tamamen tekdüze bir Haskell programı aldı. Haskell'de aslında kuyruk çağrılarını önemsemediğimizi görüyorsunuz çünkü genellikle sonsuz yapıları doğru bir şekilde ele almak istiyoruz ve herşeyin özyinelemesini talep edersek bu gerçekten mümkün değil. Aslında, özyinelemeli olmasa da, orijinal olarak kullandığınız kodun en aptalca olduğunu söyleyebilirim, bu da Data.Set'da nasıl uygulandığını gösteriyor! Tembel olarak toList sonucunu tüketebileceğimiz bir özelliği vardır ve bizimle birlikte çalışır ve tembel bir şekilde ağacı işler. Yani uygulanmasında, bir şey

min :: Tree a -> a 
min = listToMaybe . toList 

gibi Eğer elle verimliliği bunu akıllıca uygulayacağını nasıl güzel yama yakın olacak! İlk olarak benim versiyonumun yapacağı gibi tüm ağacın çaprazını oluşturmayacak. Tembelliğin bu tür birleşimsel etkileri, gerçek Haskell kodunda daha fazla temettü ödemekte ve kod kullanımımızı sadece kuyruk aramaları yapmakta (bu da aslında alan kullanımını garanti edecek hiçbir şey yapmamaktadır).