John Hughes '`foldtree' 'Ne yanlış anlama var?

Question

John Hughes, Why Functional Programming Matters başlıklı meşhur makalesinde, listeler ve sipariş etiketli ağaçlar için

listof * ::= Nil | Cons * (listof *) 
treeof * ::= Node * (listof (treeof *)) 

ve foldtree adlı bir işlev, veri türleri açıklanmıştır

foldtree f g a (Node label subtrees) = 
     f label (foldtree f g a subtrees) 

foldtree f g a (Cons subtree rest) = 
     g (foldtree f g a subtree) (foldtree f g a rest) 

foldtree f g a Nil = a 

Bu iki veri tipini uygulamalıyım Haskell es ve şu anda, foldtree

data Listof a = Nil | Cons a (Listof a) 
    deriving (Read, Show, Eq) 

-- implementation of some list functions... (skipped) 

data Treeof a = Node a (Listof (Treeof a)) 
    deriving (Read, Show, Eq) 

foldtree f g a (Node label subtrees) = f label (foldtree f g a subtrees) 
foldtree f g a (Cons subtree rest) = g (foldtree f g a subtree) (foldtree f g a rest) 
foldtree f g a Nil     = a 

uygulamak çalışıyorum ama tip uyuşmazlıklar alıyorum: (Hughes hakkında biraz daha düşündükten sonra

Couldn't match expected type ‘Treeof t’ 
      with actual type ‘Listof (Treeof t)’ 
Relevant bindings include 
    subtrees :: Listof (Treeof t) (bound at whyFunMatters.hs:27:28) 
    label :: t (bound at whyFunMatters.hs:27:22) 
    f :: t -> t1 -> t1 (bound at whyFunMatters.hs:27:10) 
    foldtree :: (t -> t1 -> t1) 
       -> (t1 -> t1 -> t1) -> t1 -> Treeof t -> t1 
    (bound at whyFunMatters.hs:27:1) 
In the fourth argument of ‘foldtree’, namely ‘subtrees’ 
In the second argument of ‘f’, namely ‘(foldtree f g a subtrees)’ 

(vs)

pseudo) foldtree'un uygulanması, bunu anladığımdan pek emin değilim ve bu tür uyumsuzluklar benim için açık görünüyor. Son iki desenlerde

ise sahip olduğu, bu argüman Treeof a tip vardır, ilk desende

• : Daha spesifik olarak, foldtree 'ın dördüncü bağımsız değişken türü üç kalıplarının arasında tutarlı görünmüyor Listof (Treeof a) yazın.

Neyi eksik?

foldtree :: (a -> c -> b) -> (b -> c -> c) -> c -> Treeof a -> b 
foldtree f g a (Node label subtrees) = f label (foldforest f g a subtrees) 

foldforest :: (a -> c -> b) -> (b -> c -> c) -> c -> Listof (Treeof a) -> c 
foldforest f g a (Cons subtree rest) = g (foldtree f g a subtree) (foldforest f g a rest) 
foldforest f g a Nil     = a 

Yazar, yanlışlıkla bir araya düşünüyorum:

Answer 1

düzgün bir tanımı ormanlar (ağaç listeleri) katlamak için ağaçlar ve bir bölme işlemi için karşılıklı yinelemeli fonksiyonları, bir bir çift oluşmalıdır iki farklı (ama yakından ilişkili) birlikte çalışır. Yazarın yazdığı şeyin gerçekten Haskell değil, Haskell benzeri bir sözde koddan ibaret olduğunu sanıyorum, bu yüzden kod sadece algoritmayı gayri resmi bir şekilde sunmak için kullanıldı.

Kağıdın, Haskell'in selefi olan Miranda olduğunu öne sürdüğünü unutmayın, ancak bunun yasal Miranda kodu olup olmadığını doğrulayamıyorum.

Answer 2

Rufflewind'in cevabı, Hughes'un ünlü gazetesinden foldtree'un şüpheli tanımını düzeltmenin en belirgin yoludur. Yine de sadece bir satır kod gerektiren ve foldr'u yeniden kullanan çok daha özlü ve modüler bir çözüm var. Bu tanımı görmek için bu yayının en altına gidin. Tanımın bir tür türevi için okumaya devam edin.

foldforest ait Rufflewind tanımına karşılaştırın:

foldforest f g a (Cons subtree rest) = g (foldtree f g a subtree) (foldforest f g a rest) 
foldforest f g a Nil     = a 

...Hughes' ile kağıttan foldr tanımını (biraz değişmiş):

foldr f a (Cons e rest)    = f e (foldr f a rest) 
foldr f a Nil      = a 

ikisi de müthiş benzer bakmayın? Aslında tek fark foldforest biz g onları "birleştirme" den önce foldtree f g a alt ağaçlar listedeki tüm diğer öğelere subtree ve (özyineleme yoluyla) uygulanır olmasıdır. Biz bunu yapar ve foldr geçirilen edilebilir bir operatör tanımlayabilir misin?

Gerçek çalışmanın yapıldığı foldforest çekirdeğine daha yakından bakalım: g (foldtree f g a subtree). ((f . g) h = f (g h) olarak Hughes'un kağıt tanımlanan) işlevi bileşimini kullanarak biz farklı bu bölümü ifade edebiliriz:

foldforest f g a (Cons subtree rest) = (g . foldtree f g a) subtree (foldforest f g a rest) 

Şimdi kısalık için h = (g . foldtree f g a) tanımlayabilir ve foldforest yeni gösterimi kullanılarak Özyinelemeyi açılımı için alt ağaçlar somut listesini geçmesine izin:

foldforest f g a (Cons subtree1 (Cons subtree2 Nil)) 
            = h subtree1 (h subtree2 a) 

Benzer bir aramanın yinelemesini foldr'a açmak nasıldır?

foldr f a (Cons subtree1 (Cons subtree2 Nil)) 
            = f subtree1 (f subtree2 a) 

Biz bir başlangıç ​​durumuna a ve Treeof s listesiyle birlikte foldr için geçebildiği foldforest gelen bir operatör ayıklamak başardık artık açıktır. Ben de Miranda bilmiyorum

foldtree f g a (Node label subtrees) = f label (foldr (g . foldtree f g a) a subtrees)