2011-12-07 34 views
16

yılında paylaşımı ile ağaç temsil etmek nasıl Haskell aşağıdaki şeklin bir "ağaç" temsil etmek istiyorum. Herhangi bir düğümden başlayarak, soldaki yolu izleyerek, sağdaki yolu takip eden soldaki gibi aynı düğüme ulaştığınızı görebilirsiniz. Yaprakları etiketleyebilmeli, her bir düğümde iki dekleranın bir işlevini uygulayabilmeli ve bu bilgiyi O (n^2) zamanında köke iletmelisiniz. Benim saf çabalarım bana üstel bir çalışma süresi veriyor. Herhangi bir ipucu?Haskell

+0

Oldukça ağacın amacını alamadım. Bir liste de kullanmak mümkün mü? Yapraklarınız soldan sağa, v1 - v5 değerleri ile etiketlenmişse, ağacınızı bir liste [v1, ..., v5] ile temsil edebilir misiniz? Örneğin, bir değer aramak için, yalnızca listenizdeki doğru değeri tanımlamak için yolunuzdaki doğru adımların sayısını saymanız gerekir. Diğer bir deyişle, bir yaprağı etiketlediyseniz paylaşım yapısını korumak ister misiniz? Yani, yaprağı sola, sola, sola, sağa etiketlersek, soldaki, soldaki, sağdaki, soldaki de değişecek mi? –

+1

Jan, Yapraklardaki değerleri temel alarak iç düğümleri de etiketlemek ve daha sonra bu bilgileri programın ilerideki bir noktasında verimli bir şekilde aramak istiyorum. –

cevap

20

bir inşa etmek kesinlikle mümkündür paylaşılan düğümler ile ağaç.

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

ve daha sonra dikkatli bir şekilde

tree :: Tree Int 
tree = Node t1 t2 
    where 
    t1 = Node t3 t4 
    t2 = Node t4 t5 
    t3 = Leaf 2 
    t4 = Leaf 3 
    t5 = Leaf 5 

(bu durumda t4 olarak) Alt ağaçlardan paylaşımı sağlamak için olduğu gibi, bu tür bir değer oluşturmak: Örneğin, sadece tanımlayabilir. paylaşımı bu formu Haskell gözlemlenebilir olmadığı için

Ancak, muhafaza etmek çok zordur: örneğin onun yaprakları

relabel :: (a -> b) -> Tree a -> Tree b 
relabel f (Leaf x) = Leaf (f x) 
relabel f (Node l r) = Node (relabel f l) (relabel f r) 

Eğer gevşek paylaşım relabel bir ağaç travers eğer. tabandan tavana hesaplama yaparken Ayrıca, bu tür

sum :: Num a => Tree a -> a 
sum (Leaf n) = n 
sum (Node l r) = sum l + sum r 

gibi paylaşım almayan avantajını sonuna kadar ve muhtemelen çalışmaları çoğaltmak.

yapabilirsiniz, bu sorunların üstesinden gelmek için paylaşım grafiği benzeri şekilde ağaçları kodlayarak açık (ve dolayısıyla gözlemlenebilir):

type Ptr = Int 
data Tree' a = Leaf a | Node Ptr Ptr 
data Tree a = Tree {root :: Ptr, env :: Map Ptr (Tree' a)} 

yukarıda şimdi

olarak yazılabilir örnekten ağaç
tree :: Tree Int 
tree = Tree {root = 0, env = fromList ts} 
    where 
    ts = [(0, Node 1 2), (1, Node 3 4), (2, Node 4 5), 
      (3, Leaf 2), (4, Leaf 3), (5, Leaf 5)] 

ödemek fiyat bu yapıları çapraz fonksiyonlar yazmak için biraz hantal olmasıdır, ama şimdi örneğin

paylaşımı korur bir yeniden etiketlenmesi fonksiyonu tanımlayabiliriz
relabel :: (a -> b) -> Tree a -> Tree b 
relabel f (Tree root env) = Tree root (fmap g env) 
    where 
    g (Leaf x) = Leaf (f x) 
    g (Node l r) = Node l r 

ve ağaç düğümleri paylaştı zaman işi aynı olmayan bir sum fonksiyonu:

sum :: Num a => Tree a -> a 
sum (Tree root env) = fromJust (lookup root env') 
    where 
    env' = fmap f env 
    f (Leaf n) = n 
    f (Node l r) = fromJust (lookup l env') + fromJust (lookup r env') 
+3

Teşekkürler Stefan! İlk formunuz, başlangıçta sahip olduğum şeydi ve siz de paylaştığınız şeyi sürdürmenin zor olduğunu belirttiniz. Açık etiketler gerektirmeyen bir versiyona sahip olmayı umuyordum (sizin durumunuzda Ints) ama belki de bu imkansız. –

+6

Bu yılki Hollanda FP Günü'nde, her iki dünyanın en iyilerini nasıl alacağımız hakkında konuşmuştum: gözlemlenebilir paylaşımın avantajlarına sahipken ağaçlarınızı (katamorfizmalar ve benzerlerini kullanarak) geçiyormuşsunuz gibi işlevlerinizi yazınız. Bu konuşmanın slaytları web sitemde bulunabilir: http://www.holdermans.nl/talks/assets/nlfp11.pdf. Bu konuda bir yazı hazırlanmaktadır. –

+0

@dblhelix - birkaç yıl sonra, bu kağıt hiç gerçekleşti mi? – ajp

2

Belki yaprakların bir liste olarak basitçe temsil ve tek değere, yani aşağı oluncaya kadar düzeyine göre işlev düzeyini uygulayabilirsiniz böyle bir şey:

type Tree a = [a] 

propagate :: (a -> a -> a) -> Tree a -> a 
propagate f xs = 
    case zipWith f xs (tail xs) of 
    [x] -> x 
    xs' -> propagate f xs' 
+0

Kesinlikle, ama aynı zamanda ara düğümleri denetim için kullanılabilir tutmak ve bir düğümden kendi soyuna doğru verimli bir şekilde gezinmek istiyorum. –