非バイナリツリーに対するカタモフィの初心者と複合設計パターン

Question

今のところ、夢はまだ続いています。各Haskellの概念で、私はもっと魅力的であることがわかります。しかし、私はこの貴重な @luquiの答えに取り組むことを完全に満たしていませんでした カタルフィズムに関する私の以前の質問, 、そして私はそれが大丈夫になるまでそれに戻ってくるつもりです。ウィキペディアのこのサンプルコードについて、 バイナリツリーのカタモルフィア.

それにもかかわらず、私はカタルフィズムを実装しようとしました 非バイナリ 木ですが、私はいくつかのトラブルに直面しています：

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] 

- その最新の行は、「マップ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 = (+) } 

- そして、この怠latteはGHCにとっても間違っています

C ++演算子>と +のように、>と +が見えます。ですから、GHCがOpertor>/+を実装するObjetsを与えることなく、GHCが私に腹を立てていることを理解していません。

第二に、私は=>（ - > ???）と @の感覚について完全にかすんでいることを認めなければなりません。

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

そして最新の質問は、複合パターンがたまたまC ++で最も重要だったので、私もこれを試しています。そして、明らかに、Haskellの1つのラインのみでほぼ記述できると思います（私にとっては本当に驚くべきことです）。

しかし、Haskellの人々は、組成の葉と複合コンストラクターが何らかの界面を持っているかもしれないという事実をどのように表現しますか？ （データは変化しないので、それは良い言葉ではないことを知っていますが、私の懸念/目標を理解できることを願っています）

これは合計編集エラーです。

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を求めていたのは、タイプクラスの制約のようです。

したがって、構成を構築するときにタイプクラスの制約を適用することにより、設計パターンの複合材が達成されます。たぶん、新しい専門データを定義する必要があります。しかし、私はそれをする前にタイプクラスを学ぶべきです:-)

Answer 1

ここにはいくつかの異なるエラーがあるので、それに対処するための最良の方法はわかりませんが、何が一体何なのかわかりません。

将来的には、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.

   ANを変換するため a に r あなたはあなたを適用する必要があります CompositionAlgebra それに： g (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

適用されます Ord タイプへの制約 a.

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

Answer 2

第二に、私は=>（ - > ???）と @の感覚について完全にかすんでいることを認めなければなりません。

CONSINDER エレム リストに特定の値が含まれているかどうかをテストする関数。あなたはそれをとして定義することができます

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].