5

これは、Ord などのクラスのカスタム インスタンスを作成する最初の試みです。

リストを表す新しいデータ構造を定義しました。

data List a = Empty | Cons a (List a)
    deriving (Show, Eq)

ここで、List a <= List b が「List a の要素の合計が List b の要素の合計以下である」ことを意味するように、List の Ord の新しいインスタンスを定義したいと考えています。

まず第一に、プレリュードで定義された合計は新しいリストデータ型では機能しないため、新しい「合計」関数を定義する必要がありますか? では、Ord for List の新しいインスタンスを定義するにはどうすればよいでしょうか。

ありがとう

4

5 に答える 5

13

まず第一に、これは通常のリスト インスタンスとまったく同じようには機能しません。通常のインスタンスは、リストのアイテム自体が順序付け可能であることにのみ依存します。あなたの提案は、それらの数（Numクラス内など）に依存するため、より狭いものになります。

新しいsum関数を定義する必要があります。sum幸いなことに、単純な再帰関数として書くのはとても簡単です。(偶然にも、関数 を呼び出すことができます。sum'これは「サム プライム」と発音され、慣例により、 に非常によく似た関数であることを意味しsumます。)

Numさらに、インスタンスはクラスだけでなくクラスにも依存する必要がありますOrd。

新しいsum関数を作成したら、次のようにインスタンスを定義できます。

instance (Ord n, Num n) => Ord (List n) where compare = ... 
  -- The definition uses sum'

このインスタンス ステートメントは、すべての型nについて、 if nis inOrdおよびNum、List nis in Ordwhere 比較が次のように機能することを示していると読むことができます。構文は数学に非常に似ていますが、ここで=>は含意です。これにより、構文を覚えやすくなることを願っています。

の合理的な定義を与える必要がありcompareます。参考までに、compare a b次のように動作しa < bます。LTa = bEQa > bGT

これは実装が簡単な関数なので、読者の演習として残します。(私はいつもそれを言いたかった:P)。

于 2012-05-25T04:51:02.860 に答える
4

どうですか...

newtype List a = List [a]

これは、特定の型に対して新しい「互換性のない」型クラス インスタンスを導入する場合に非常に一般的です ( egまたはおよびZipListのようないくつかのモノイドを参照) 。SumProduct

リストのインスタンスを簡単に再利用できるようになりsumました。

于 2012-05-25T07:16:51.960 に答える
2

@Tikhonのアプローチを少し一般化すると、 as 制約Monoidの代わりにNum、定義済みの「合計」が既にある場合に使用することもできますmconcat（もちろん、まだ必要でしOrdた）。これにより、数値だけでなく、さらにいくつかの型を考慮することができます (たとえばList (List a)、再帰的に簡単に定義できるようになりました)。

一方、 a をモノイドとして使用したい場合Numは、毎回Sumorを決定する必要がありますProduct。これを明示的に記述しなければならないことは、短さと可読性を低下させる可能性があると主張することができますが、最終的にどの程度の一般性を持たせたいかによって決まる設計上の選択です。

于 2012-05-25T05:46:52.143 に答える
0

..またはプレリュードの合計関数を使用した別のソリューション。

data List a = Empty | Cons a (List a)
                deriving (Show, Eq)


instance (Ord a, Num a, Eq a) => Ord (List a) where

      -- 2 empty lists

      Empty <= Empty            =   True

      -- 1 empty list and 1 non-empty list

      Cons a b <= Empty         =   False
      Empty <= Cons a b         =   True

      -- 2 non-empty lists

      Cons a b <= Cons c d      =   sum (listToList (Cons a b)) 
                                              <= sum (listToList (Cons c d)) 


-- convert new List to old one

listToList      ::      (Num a) => List a -> [a]

listToList Empty                =       []
listToList (Cons a rest)        =       [a] ++ listToList rest
于 2012-05-25T14:54:36.840 に答える
0

どうですか..

data List a = Empty | Cons a (List a)
                deriving (Show, Eq)


instance (Ord a, Num a, Eq a) => Ord (List a) where

      -- 2 empty lists

      Empty <= Empty            =   True

      -- 1 empty list and 1 non-empty list

      Cons a b <= Empty         =   False
      Empty <= Cons a b         =   True

      -- 2 non-empty lists

      Cons a b <= Cons c d      =   sumList (Cons a b) <= sumList (Cons c d) 


-- sum all numbers in list

sumList         ::      (Num a) => List a -> a

sumList Empty               =       0
sumList (Cons n rest)       =       n + sumList rest

これはあなたが探しているものですか？

于 2012-05-25T14:19:47.670 に答える