1

最小限の変更を加えた作業バージョン、thx @Matt、Petr、Landei !!!

insert :: (Ord el) => el -> Menge el -> Menge el
insert a (Menge (x:xs)) = ins a (Menge (x:xs)) (Menge [])

ins a (Menge []) (Menge ys) = Menge (ys ++ [a])
ins a (Menge xs@(x:xs')) (Menge ys)
       | a <  x     = Menge (ys ++ [a] ++ xs)
       | a >  x     = ins a (Menge xs') (Menge (ys ++ [x]))
       | otherwise  = Menge (ys ++ xs)

独自の Datatype Menge を持ち、リストのように機能し、正しい位置に要素を挿入する必要があります...

module Menge (
  Menge,
  empty,
  insert,
  ins
) where

data Menge el = Menge [el] deriving (Eq)

instance (Show el) => Show (Menge el) where
 show (Menge liste) = "{" ++ (elms liste) ++ "}"
     where
       elms :: (Show a) => [a] -> String
       elms [] = ""
       elms (x:[]) = show x
       elms (x:xs) = show x ++ ", " ++ elms xs

empty :: Menge el
empty = Menge []

insert :: (Ord el) => el -> Menge el -> Menge el
--insert a (Menge []) = (Menge [a]) 
insert a (Menge (x:xs)) = ins a (Menge (x:xs)) (Menge [])

ins a (Menge []) (Menge (y:ys)) = (Menge ((y:ys) ++ [a]))
ins a (Menge (x:xs)) (Menge (y:ys)) 
       | a <  x = (Menge ((y:ys) ++ [a] ++ (x:xs)))
       | a >  x = ins a (Menge xs) (Menge ((y:ys) ++ [x]))
       | a >  x && xs == [] = error "same function as: ins a empty (Menge (y:ys))"
       | a == x = (Menge ((y:ys) ++ (x:xs)))
       | otherwise = error "blabla"

私は次のように入力します: insert 2 (Menge ([1,3]))、私の意見では、次のように動作するはずです:

--> ins 2 (Menge (1:3)) empty --> 2 > 1 --> ins 2 (Menge [3]) (Menge [] ++ [1])
--> ins 2 (Menge [3]) (Menge [1]) --> 2 < 3 --> (Menge ([1] ++ [2] ++ [3])) --> [1,2,3]

しかし、代わりに次のように表示されます：「関数insの非網羅的なパターン」

と入力しても同じエラーが発生するins 2 (Menge ([1,3])) (Menge [])ため、最初のステップが機能します。コンパイラは「空」/「(Menge [])」を好まないようです。入力すると、答えins 2 (Menge ([1,3])) (Menge [1,3])が得{1, 3, 2}られるためです。

4

3 に答える 3

3

には次の 2 つの大きな問題がありinsます。

  1. の値を使用してパターン マッチを試みているようですempty-- これは機能しません。Menge空でないリストを持つものを含め、任意の が一致します。これemptyは、 が関数に対してローカルなバインディングとして使用されているためです (他のバインディングをシャドーイングします)。したがって、代わりに次のものが必要になります。

    ins a (Menge []) (Menge (y:ys)) = ...

    この問題の症状はpattern match(es) are overlapped、コードをロードするときに Haskell のインストールで警告が表示されることです。これは基本的に、デッド コードがあることを意味します。

  2. あなたのパターンは、3 番目の引数が次の場合に一致しません。Menge []これは、表示されたメッセージを表示するエラーであると思います (ただし、エラー メッセージ全体が表示されていないため、わかりません)。両方の方程式は、空でないリストにのみ一致します。

    例えば：

    ghci> ins x (Menge []) (Menge [])

    どのパターンとも一致しません。

于 2012-08-13T17:50:56.750 に答える
1

insertゼロから実装してみました。まず、unmenge値の分解を簡単にする関数を追加し、Menge宣言をnewtypeに変更しました（パフォーマンスの最適化だけです。このようにすると、実行時に新しいデータコンストラクターが実際に作成されることはありません）。

newtype Menge el = Menge { unmenge :: [el] }
  deriving (Eq)

これで、insert関数は次のように記述できます。

insert :: (Ord el) => el -> Menge el -> Menge el
insert a (Menge []) = (Menge [a]) 
insert a (Menge xs@(x:xs'))
    | a <= x    = Menge (a : xs)
    | otherwise = Menge (x : unmenge (insert a (Menge xs')))

aがリストの最初の項目よりも小さい場合は、単に先頭に追加されます。そうでない場合xは、が最小の数であるため、最初に配置aされ、残りの部分に再帰的に挿入されます。

このソリューションは末尾再帰ではないことに注意してください。

さらに簡単な解決策は、span関数を使用することです。

insert :: (Ord el) => el -> Menge el -> Menge el
insert a (Menge xs) = let (smaller, bigger) = span (<= a) xs
                        in Menge (smaller ++ [a] ++ bigger)

編集：修正したコードは期待どおりに機能しているようです。少し簡略化しましたが、実質的な変更はありませんでした。

insert :: (Ord el) => el -> Menge el -> Menge el
insert a (Menge (x:xs)) = ins a (Menge (x:xs)) (Menge [])

ins a (Menge []) (Menge ys) = Menge (ys ++ [a])
ins a (Menge xs@(x:xs')) (Menge ys)
       | a <  x     = Menge (ys ++ [a] ++ xs)
       | a >  x     = ins a (Menge xs') (Menge (ys ++ [x]))
       | otherwise  = Menge (ys ++ xs)

改善のためのいくつかのアイデア：

  • as-patternsを見てください（私はここでそれらを使用しました）。

  • リストの最後に要素を追加すると、O（n）の複雑さがあります。リスト全体を再計算する必要があります。リストを逆の順序で保持し、最後にのみ修正することをお勧めします。

    ins a (Menge []) (Menge ys) = Menge (reverse ys ++ [a])
ins a (Menge xs@(x:xs')) (Menge ys)
       | a <  x     = Menge (reverse (a : ys) ++ xs)
       | a >  x     = ins a (Menge xs') (Menge (x : ys))
       | otherwise  = Menge (reverse ys ++ xs)

  • Data.Setと呼ばれるデータ構造があり、必要なことだけを実行します。バイナリツリーを使用して、ソートされた要素のセットを保持します。ほとんどの操作には、O（1）またはO（log n）の複雑さがあります。

于 2012-08-13T18:06:21.717 に答える
1

私の見解：

insert :: (Ord el) => el -> Menge el -> Menge el
insert a mx = merge (Menge [a]) mx 

merge :: (Ord el) => Menge el -> Menge el -> Menge el
merge mx (Menge []) = mx  
merge (Menge []) my = my
merge (Menge (x:xs)) (Menge (y:ys)) 
  | x == y = merge (Menge xs) (Menge (y:ys))   
  | x < y = merge (Menge xs) (Menge (x:y:ys))
  | x > y = let Menge zs = merge (Menge (x:xs)) (Menge ys) 
            in Menge (y:zs)
于 2012-08-14T07:45:32.057 に答える