John Hughesの「foldtree」について私は誤解していますか？

Question

ジョン・ヒューズは、Why Functional Programming Matters題した彼の有名な論文では、リストや注文したラベル付き木ため

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

と foldtreeと呼ばれる機能を、データ型について説明し

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 

私はこれら2つのデータtyp HaskellではESは、と私は現在、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 

を実装しようとしているが、私は型の不一致取得しています：（ヒューズについてのいくつかのより多くのことを考えた後

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)’ 

（など）

を擬似）の実装をfoldtree、私はそれを理解していないと、これらのタイプのミスマッチは今私にとって明らかに思える。より具体的には、foldtreeの第四の引数の型は、3つのパターン間で一貫思われない：第一のパターンにおける

• 、その引数は、それが持っている最後の2つのパターンの
• 一方、Treeof aを入力しましたタイプListof (Treeof a)と入力します。

私は何が欠けていますか？

Answer 1

適切な定義は、相互再帰関数の一対の森林（木のリスト）折り曲げるため木一つを折り畳むための1つから構成されなければならない。私は著者が誤っ合わせた考える

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 

を2つの異なる（ただし、密接に関連する）機能を一緒に使用します。私は著者が書いたものが実際はハスケルではなく、もっとハスケルのような擬似コードであると考えているので、このコードはちょうど非公式な方法でアルゴリズムを提示するために使われた。

この論文は、ハスケルの前身であるミランダを示唆しているようだが、これが合法ミランダコードであるかどうかを確認することはできない。

Answer 2

Rufflewindの答えは、ヒューズの有名な論文から疑問のあるfoldtreeの定義を修正する最も明白な方法です。しかし、コードの1行だけを必要とし、再利用するためには、より簡潔でモジュラーなソリューションがあります。foldrこの定義を見るには、この投稿の一番下までスクロールしてください。何らかの種類の定義のために読書を続けてください。

はfoldforestのRufflewindの定義の比較：

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

...ヒューズの紙からfoldrの（若干変更）の定義で：

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

彼らの両方がとても似てないのですか？実際には唯一の違いは、foldforestではgを「マージする」前にサブツリーのリスト内の他のすべての要素にfoldtree f g aを、subtreeに（再帰を介して）適用するということです。これを行い、foldrに渡すことができる演算子を定義できますか？

具体的な作業が行われるfoldforestのコアを詳しく見てみましょう。g (foldtree f g a subtree) （(f . g) h = f (g h)としてヒューズの論文で定義された）関数合成を用いて、我々は異なり、この部分を表現することができます

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

は今度は、簡潔にするためh = (g . foldtree f g a)を定義し、私たちの新しい表記法を使用して再帰を展開foldforestにサブツリーの具体的なリストを渡してみましょう：

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

foldrと同様の呼び出しの再帰を展開するとどうなりますか？

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

我々が開始状態aとTreeof Sのリストと共にfoldrに渡すことができるfoldforestからオペレータを抽出することができたことは、今は明らかです。モジュール性と簡潔を最大foldtreeの完全な定義は、そのようになります。

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