Haskell'de bir ağaca geçme ve filtreleme

Question

Haskell'e oldukça yeni geliyorum (hala tamamen anlayış monadları üzerinde çalışıyor). Ben ne yapmak istersiniz bir filtre ile yeni bir ağaç bu çapraz ve üretmek mümkün olan

type Tree = [DataA] 

data DataA = DataA1 [DataB] 
      | DataA2 String 
      | DataA3 String [DataA] 
       deriving Show 

data DataB = DataB1 [DataA] 
      | DataB2 String 
      | DataB3 String [DataB] 
       deriving Show 

yapı gibi bir ağaç var bir sorun var. Örneğin ağaçtaki tüm DataB2'yi "foo" olarak değiştirmek isteyebilirim.

Aynı veri bölümünde olduklarında ağaç örnekleri gördüm ve yapıcılar benzer.

Python dünyasında, yalnızca listeden geçebilir, ihtiyacım olanı eşleştirebilir ve değeri değiştirebilirim.

Haskell'de ağacımı kopyalayabilmem gerektiğini tahmin ediyorum, fakat kurucularda ve farklı veri türlerinde gömülü listelerle nasıl başa çıkıyorsunuz?

Answer 1

Bunun için genel programlamayı kullanabilirsiniz.

Böyle bir genel programlama kitaplığına, Kalor Komutanlığınızı (Scrap Your Boilerplate) denir.

{-# LANGUAGE DeriveDataTypeable #-} 

İthalat modülünü Data.Generics: En modülün en üst kısmında yazılı göre klişe Hurda sağlar. Ardından, Show'un yanı sıra, veri türleriniz için Typeable ve Data örneklerini de elde edin. Eğer bu işi yapmak için yapmanız gereken tek şey

toFoo :: Data a => a -> a 
toFoo = everywhere (mkT step) 
    where 
    step (DataA2 _) = DataA2 "foo" 
    step x   = x 

:

Şimdi böyle istenen işlevi yazabilirsiniz. Örneğin, toFoo [DataA1 [], DataA2 "hi", DataA3 "yo" []]'u aradığınızda, yanıt [DataA1 [],DataA2 "foo",DataA3 "yo" []] olur.

Bu yardımcı olur umarız!

Answer 2

Sorunuza genel bir cevap bilmiyorum. Veri tipi oldukça çekişmeli ve muhtemelen bir filtre yerine bir kat uygulamayı tercih ediyorum. Ancak burada, dört konumdaki dizeleri güncelleyebilen bazı filtre işlevleri vardır. Kodu derleyiciye koydum, bu yüzden typechecks, ama ben çalıştırmadım.

type SFilter = String -> String 

-- to filter a tree, say how A2, A3, B2, and B3 should be changed 

type Filter tree = SFilter -> SFilter -> SFilter -> SFilter -> (tree -> tree) 

afilter :: Filter DataA 
bfilter :: Filter DataB 
tfilter :: Filter Tree 

tfilter a2 a3 b2 b3 = map (afilter a2 a3 b2 b3) 
afilter a2 a3 b2 b3 = fil 
    where fil (DataA1 bs) = DataA1 $ map (bfilter a2 a3 b2 b3) bs 
     fil (DataA2 s) = DataA2 (a2 s) 
     fil (DataA3 s as) = DataA3 (a3 s) (map fil as) 

bfilter a2 a3 b2 b3 = fil 
    where fil (DataB1 as) = DataB1 $ map (afilter a2 a3 b2 b3) as 
     fil (DataB2 s) = DataB2 (b2 s) 
     fil (DataB3 s bs) = DataB3 (b3 s) (map fil bs) 

Answer 3

Tüm veri yapısını değiştirmek ve buradaki bazı öğeleri değiştirmek istiyorsunuz. Bu, genellikle veri yapısını bir parametre olarak alan ve , yapının yeni, değiştirilmiş sürümünü döndüren bir işlev tarafından yapılır.

Her giriş durumu için, bu işlev, döndürülen yeni değerin nasıl görüneceğini tanımlar.

(DataA değerlerin bir liste olan) bir Tree değiştirir temel işlevi muhtemelen sadece modifiye değerlerin yeni bir liste dönmelidir.

-- # function to change a |Tree| 
mutate :: Tree -> Tree 
mutate as = map mutateA as 
    -- # (The |map| function applies the |mutateA| function to every 
    -- # element of |as|, creating a list of all the return values) 

Şimdi mutateA fonksiyon tüm olası DataA değerlerini değiştirmek için tanımlanması gerekir ve öyle iyi: Biz bir modifyA işlevine değerlerin bu modifikasyonları erteleme ise ana değişiklik işlevi şöyle DataB değerlerini işleyen mutateB işleviyle birlikte.

Bu fonksiyonlar uygun yeni değerler değerlerin farklı olası durumlarda bakıp dönüş:

-- # function to change |DataA| items 
mutateA :: DataA -> DataA 
    -- # A |DataA1| is a |DataA1| with modified values 
mutateA (DataA1 bs) = DataA1 (map mutateB bs) 
    -- # A |DataA3| is a |DataA3| with modified values 
mutateA (DataA3 s as) = DataA3 s (map mutateA as) 
    -- # In the remaining case(s) the value stays the same 
mutateA d    = d 

-- # function to change |DataB| items 
mutateB :: DataB -> DataB 
mutateB (DataB1 as) = DataB1 (map mutateA as) 
mutateB (DataB3 s bs) = DataB3 s (map mutateB bs) 
    -- # Here comes a real change 
mutateB (DataB2 _) = DataB2 "foo" 

yeni eleman nerede tüm DataB2 değerleri her yerde, hesaplanan ağaçtaki her element için bu yolu ağacında "foo" ile değiştirilir.

Nispeten ayrıntılıdır, çünkü içinden geçilmesi gereken bir değer içeren listesini içeren beş farklı vakanız vardır, ancak bu Haskell'e özgü değildir. 'da zorunlu bir dil, genellikle 'un map numaralı telefonunun yerine beş adet döngüye sahip olacaktır.

Belki bu "yükü" azaltmak için veri yapınızı basitleştirebilirsiniz.Bu tabi ki gerçek kullanım durumunuza bağlıdır, ancak, örneğin, Data2 kasalarına ihtiyacınız yoktur: DataA2 "abc" ve DataA3 "abc" [] arasında bir fark var mı?

Answer 4

Karşılıklı özyinelemeli veri türleri ile çalışmak için multirec kitaplığına göz atmak isteyebilirsiniz. Kullanmıyorum, ama anlattığın şeyden, tam olarak çalıştığın sorunun türünü hedeflemesi gibi geliyor. Burada önerilen diğer cevaplar gibi jenerik programlama kullanır, ancak her şeyi kendinizin gerçekleştirme zamanından kurtarabilir.