1

これは比較的単純なhaskellの質問ですが、私は多くの問題を抱えています。この関数'add'を適用して、文字列のリストをBSTに変換しようとしています。（add関数は単に用語を挿入するだけです）私の質問は、add関数を[String]に適用して、基本的に各関数を1つずつ挿入するようにフォールドを定義する方法です。

私の最初の考えは、xsに適用する関数は（_ basetreeを追加）であり、_はxsの各要素であり、ベースツリーは1つの要素xを持つツリーであるというものでした。次に、foldrはその関数をxsの各要素に適用します。何が悪いのかわかりませんが、これは私にエラーを与えています。

*** Expression     : foldr1 (add x (add x Empty)) xs
*** Term           : add x (add x Empty)
*** Type           : BST
*** Does not match : [Char] -> [Char] -> [Char]

 

data BST = MakeNode BST String BST
           | Empty

add :: String -> BST -> BST

listToTree :: [String] -> BST
listToTree (x:xs) = foldr (add x (add x Empty)) xs -- Here***

誰かが私を助けてくれるなら、それは素晴らしいことです。私はすでにこのフォルダを理解しようとしてほぼ3時間のように過ごしました..

4

3 に答える 3

8

Gabrielがコメントで述べているように、手動の再帰（パターンマッチ(x:xs)）とfoldr非常に珍しい方法を組み合わせています。通常、手動再帰を使用するかfoldr、再帰が「リストを使い果たすまでリストの要素に関数を繰り返し適用する」というパターンに従う場合に使用します。

あなたのadd関数は次のようになっていると思います：

add :: String -> BST -> BST
add string Empty            = MakeNode Empty string Empty
add string (MakeNode l s r) =
    if string < s
        then MakeNode (add string l) s r
        else MakeNode l s (add string r)

これが邪魔にならないようにすると、関数listToTreeは通常2つの方法のいずれかで記述されます。1つ目は、パターンマッチングと再帰を使用することです。

listToTree []     = Empty
listToTree (x:xs) = add x (listToTree xs)

つまり、空のリストがある場合は空のツリーを返します。または、ヘッドの後にテールが続く場合は、リストのテールによって返されるツリーにリストのヘッドを追加します。

もう1つのアプローチはlistToTree、リストを折りたたんで書くことです。これはあなたのために再帰を抽象化するので、あなたはただ書くことができます

listToTree = foldr add Empty

foldrタイプがあるのでこれは機能します

foldr :: (a -> b -> b) -> b -> [a] -> b

とタイプがありaddますEmpty

add   :: String -> BST -> BST
Empty :: BST

タイプを専門にするaとb、

foldr :: (String -> BST -> BST) -> BST -> [String] -> BST

つまり、

foldr add Empty :: [String] -> BST

これらのどれを好むべきですか？おそらく、最初のものは初心者が読んで理解するのが簡単です。ただし、Haskellの経験を積むにつれて、2番目のバージョンが理解しやすくなることがわかります。また、より簡潔であり、フォールドの観点から記述されているため、リスト融合ルールをより頻繁にトリガーできるため、コードの効率が向上する可能性があります。

foldrを理解する

私の意見では、フォールドを理解するための鍵は、フォールドがリストコンストラクターを指定した関数や定数に置き換えることを理解することです。Haskellには、リストに2つの可能なコンストラクターがあります。

[]  :: [a]
(:) :: a -> [a] -> [a]

すべての構文を脱糖すると、リストは実際には次のようになります（これは有効なHaskellです-試してみてください！）

xs = 1 : 2 : 3 : []

を呼び出すfoldr op x0 xsと、foldは、のすべてのコンストラクターを効果的に置き換え、(:)すべてのコンストラクターをxs：で置き換えます。op[]x0

foldr op x0 xs = 1 `op` 2 `op` 3 `op` x0

opもちろん、ここにはあいまいさがあります。これは、アソシエートが左にあるのか右にあるのかがわからないためです。タイプが機能するためには、次のように、右に関連付ける関数を提供する必要があります（これが右フォールドと呼ばれる理由です）。

foldr op x0 xs = 1 `op` (2 `op (3 `op` x0))

左の折り目は同じですが、代わりに左に関連付けられる（そして、初期値をリストの最後ではなく最初に置く）ので、最終的には次のようになります。

foldl op x0 xs = ((x0 `op` 1) `op` 2) `op` 3
于 2013-02-28T23:01:08.537 に答える
2

フォルダーの種類は

(a -> b -> b) -> b -> [a] -> b,

つまり、abを受け取る関数と、[a]のリストを取り、abを返します。ここに追加します

(String -> BST -> BST),

だからそれは

(String -> BST -> BST) -> BST -> [String] -> BST,

今はadd機能がないのでコンパイルできませんが、

listToTree (x:xs) = foldr add (add x (add x Empty)) xs

トリックを行います。型アノテーションは少なくとも同じです。これでリストの先頭が2回追加されるはずですが、Add関数が重複を無視している可能性がありますか？それを含めることができれば、さらに調査することができます。

于 2013-02-28T22:55:09.063 に答える
2

あなたが望むように見えます：

listToTree = foldr add Empty

foldrタイプがあります(a -> b -> b) -> b -> a

したがって、アキュムレータ関数と初期値が必要です。Emptyは初期ツリー値でありadd、要素と既存のツリーを指定して新しいツリーを構築します。

于 2013-02-28T22:57:28.027 に答える