1

今のところ、夢はまだ続きます。Haskell の概念を学ぶたびに、私はより魅力的になります。それでも、カタモルフィズムに関する以前の質問に対するこの貴重な@luquiの回答に完全に取り組んでいないので、問題が解決するまで戻ってきます。ウィキペディアのこのサンプル コードについてで、BINARY ツリーのカタモルフィズムを扱っています。

それにもかかわらず、 NON BINARYツリーにカタモルフィズムを実装しようとしましたが、いくつかの問題に直面しています。

data Composition a = Leaf a
                   | Composite [Composition a]

data CompositionAlgebra a r = CompositionAlgebra { leaf      :: a →  r
                                                 , composite :: [r] →  r }

foldComposition :: CompositionAlgebra a r →  Composition a →  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite [y]) =  map g [y]

-- その最新行は "map g [y]" で ghc を喜ばせません

maxOfPair :: a →  a →  a
maxOfPair x y = if( x > y) -- this doesnt please ghc either, Ordering trouble
                then (x) 
                else (y)

maxInList :: [a] →  a
maxInList (x:xs) = maxOfPair x (maxInList xs)

treeDepth :: CompositionAlgebra a Integer
treeDepth = CompositionAlgebra { leaf = const 1, composite = λx →  1 + maxInList x }

sumTree :: (Num a) ⇒ CompositionAlgebra a a
sumTree = CompositionAlgebra { leaf = id, composite = (+) }

-- そして、この最新の sumTree は ghc でも間違っています

C++ 演算子の > と + と同じように > と + が表示されます。だから私は、オブジェクトを実装するオブジェクトを与えることなく、ghcが私に怒っていることを理解していません >/+ かどうか。

次に、パターン マッチングのガイドのように見える => (-> ??? とは異なる) と @ の意味について、私は完全に漠然としていることを認めなければなりません。

このコードをどのように修正しますか?

そして最新の質問ですが、C++ で複合パターンがたまたま私にとって最も重要だったので、私もこれをやろうとしています。そして明らかに、Haskell では 1 ～ 2 行でほぼ記述できることがわかります (これは私にとって本当に驚くべきことです)。

しかし、コンポジションのリーフ コンストラクターとコンポジット コンストラクターがある種の同じインターフェイスを持つ可能性があるという事実を、どのように表現しますか? (データは可変ではないため、適切な言葉ではないことは承知していますが、私の懸念/目標を推測して理解していただければ幸いです)

これはコンパイル エラーの合計です。

src\Main.hs:27:79:
    Couldn't match expected type `[r]'
           against inferred type `Composition a'
    In the expression: y
    In the second argument of `map', namely `[y]'
    In the expression: map g [y]

src\Main.hs:30:20:
    Could not deduce (Ord a) from the context ()
      arising from a use of `>' at src\Main.hs:30:20-24
    Possible fix:
      add (Ord a) to the context of the type signature for `maxOfPair'
    In the expression: (x > y)
    In the expression: if (x > y) then (x) else (y)
    In the definition of `maxOfPair':
        maxOfPair x y = if (x > y) then (x) else (y)

src\Main.hs:41:0:
    Occurs check: cannot construct the infinite type: a = [a] -> [a]
    When generalising the type(s) for `sumTree'

編集 したがって、これは非バイナリカタモルフィズムの最終バージョンです

data Composant a = Leaf a
                 | Composite [Composant a]

data CompositionAlgebra a r = CompositionAlgebra { leaf      :: a →  r
                                             , composite :: [r] →  r }

foldComposition :: CompositionAlgebra a r →  Composant a →  r
foldComposition a@(CompositionAlgebra {leaf = f}) (Leaf x) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite ys) =  g(map(foldComposition a) ys)

maxOfPair :: Ord a ⇒ a →  a →  a
maxOfPair x y = if( x > y) 
                then (x) 
                else (y)

maxInList :: Ord a => [a] →  a
maxInList (x:xs) = maxOfPair x (maxInList xs)

treeDepth :: CompositionAlgebra a Integer
treeDepth = CompositionAlgebra { leaf = const 1, composite = λx →  1 + maxInList x }

addList :: Num a ⇒ [a] → a
addList (x:xs) = x + addList xs 

sumTree :: (Num a) ⇒ CompositionAlgebra a a
sumTree = CompositionAlgebra { leaf = id, composite = addList }

以下の有効な回答によると、C++ インターフェイス契約に相当する Haskell を求めていたのは、型クラスの制約のようです。

したがって、デザイン パターン Composite は、Composition a を構築するときに型クラスの制約を適用することによって実現されます。おそらく、新しい特殊なデータを定義する必要があります。しかし、それを行う前に型クラスを学ぶ必要があります:-)

4

2 に答える 2

5

ここにはいくつかの異なるエラーがあるため、SO でこれを処理する最善の方法はわかりませんが、一体何なのでしょう。

将来的には、GHC が提供するエラーをさらに含めるようにしてください。

の：

foldComposition :: CompositionAlgebra a r →  Composition a →  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite [y]) =  map g [y]

関数foldComposeには 2 つのエラーがありますが、そのうちの 1 つだけが型チェッカーによって検出されます。

  1. でパターン マッチングを行っています(Composite [y])。これは、1 つの要素のリストに対してのみ一致します。おそらく、リスト全体(Composite ys)にバインドするが必要です。ys

  2. map g [y]のリストを取得するように既に定義しているため、型チェッカーに合格しませんが、gのリストを指定してrいますa。

    aanを anに変換するには、 yourをそれrに適用する必要があります。CompositionAlgebrag (map (foldComposition a) ys)

だから私はこれを次のように書きます：

foldComposition :: CompositionAlgebra a r →  Composition a →  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite ys) = g (map (foldComposition a) ys)

次のエラーの場合:

maxOfPair :: a →  a →  a
maxOfPair x y = if( x > y) -- this doesnt please ghc either, Ordering trouble
                then (x) 
                else (y)

Haskell では、(aここのような) 型変数は、呼び出し元の選択により、呼び出し元によって任意の型で埋められる可能性があります。

maxPairこれは、型シグネチャで、関数がすべての入力型で機能すると主張していることを意味します。GHC は (独自の方法で) 演算子がすべて>の型に対して機能するわけではないと不平を言っているため、プログラムのコンパイルを拒否しています。

この問題を解決するには、型クラスを使用する必要があります。Haskell では、型クラスにより、呼び出し元が使用する型を選択できますが、いくつかの制約があります。typeclasses に関するHaskell チュートリアルを読むことをお勧めします。

正しい型シグネチャは次のようになります。

maxOfPair :: Ord a => a →  a →  a

Ordtype に制約を適用しますa。

また、標準関数を使用する必要がありますmax。

于 2011-01-20T02:39:03.420 に答える
3

次に、=>（-> ???とは異なります）と@の意味について完全にぼんやりしていることを認めなければなりません。これは、パターンマッチングのガイドのようです。

リストに特定の値が含まれているかどうかをテストするelem関数を検討してください。あなたはそれを次のように定義することができます

elem _ [] = False
elem x (y:ys) | x == y = True
              | otherwise = elem x ys

この機能を持つ署名はどれですか？のように見えelem :: a -> [a] -> Boolます。しかし、あなたが書いたのでコンパイラは文句を言いますx == y、そしてすべてaの==関数が定義されているわけではなくa、Eq型クラスにあるものだけのために。したがって、「Eq...にあるすべてのaに対して」のようなものを指定する必要があります。そしてまさにこれのためにあなたは必要=>です。したがって、の正しい署名はelemですelem :: Eq a => a -> [a] -> Bool。

は@、構造全体に名前を付け、同時にパターンマッチングを行う可能性を提供します。たとえば、パターンがa@(x:xs)あり、その関数をで呼び出す場合[1,2,3,4]、aは[1,2,3,4]、xであり1、xsはです[2,3,4]。

于 2011-01-20T12:53:37.977 に答える