キューにバランスの取れたリストがある。

Question

私はバランスのとれたリストの定義をhaskellに書こうとしています。 QueueAは、バランスの取れたリストを持つキューする必要があります：インターフェイスキュー

module Queue where 

class Queue a where 
    empty :: a 
    (|>) :: a -> a -> a 
    null :: a -> Bool 
    head :: a -> a 
    tail :: a -> a 
    toList :: a -> [a] 

に基づいて

module QueueA where 

import Queue 

data QueueA a = QA [a] [a] 

instance Queue (Queue a) where 
    empty = QA [] [] 

    (|>) (QA a b) el = norm $ QA a (el : b) 

    head (QA a _) = Prelude.head a 

    tail (QA a b) = norm $ QA (Prelude.tail a) b 

    toList queue = Queue.head queue : Queue.tail queue 


norm :: [a] -> [a] 
norm queue@(QA a b) = if (length a) >= (length b) then queue else QA (a ++ reverse b) [] 

私が正しくインタフェースを定義する方法が分からない、私は私が見つけた例を中心に、これをベース。ほとんどのエラーは、次のようになります。

Couldn't match expected type `a' with actual type `QueueA a1' 
    `a' is a rigid type variable bound by 
     the instance declaration 
     at C:\Users\kroll\Dropbox\WS 16.17\Moderne Funktionale Programmierung\Übung\Blatt 8\Code\Queue 

私は空:: Aを定義することは、おそらく間違っていることを知っているが、空::キューaはどちらか動作しません。

Answer 1

私はあなたがこのTypeFamilies拡張が必要であることをインスタンス

instance Queue (QueueA a) where 
    type Item (QueueA a) = a 

    empty = QA [] [] 

    (QA a b) |> e = norm $ QA a (e : b) 

    ... 

注意して

class Queue q where 
    type Item q 
    empty :: q 
    (|>) :: q -> Item q -> q 
    null :: q -> Bool 
    head :: q -> Item q 
    tail :: q -> q 
    toList :: q -> [Item q] 

ような何かをしたいと思います。

エラーの原因は、キュー自体がキュー内の値と競合しているためです。たとえば、

instance Queue (QueueA b) where -- changed (QueueA a) to (QueueA b) for clarity 
    head :: QueueA b -> QueueA b 
    head ... = ... 

この例では、a ~ QueueA bです。しかし、bをPrelude.headと返すので、エラーです。また、（GHCを有効にするためにどの機能拡張を教えてくれます）MultiParamTypeClassesと共同で

class Queue q item where 
    empty :: q item 
    (|>) :: q item -> item -> q item 
    null :: q item -> Bool 
    head :: q item -> item 
    tail :: q item -> q item 
    toList :: q item -> [item] 

で行くことができますが、私は、一般的なコンテナで作業する場合、このアプローチは、実際には通常あまり柔軟であることがわかりました。

Answer 2

@ bheklilrの答えは必要以上に複雑だと思います。私はキュークラスの良い十分な定義は、純粋なHaskellの98に与えることができ数える：タイプの家族や高度なmono-traversable様トリックを行う必要がある場合を除き、機能の依存関係、ため

class Queue q where 
    empty :: q a 
    push :: a -> q a -> q a 
    pop :: q a -> Maybe (a, q a) 

必要はありません。

​​

先入れ先出しキューが素直Queueのインスタンスにすることができます：

instance Queue QueueA where 
    empty = QA [] [] 

    push x (QA front back) = QA front (x:back) 

    pop (QA [] []) = Nothing 
    pop (QA [] back) = 
     let (x:xs) = reverse back 
     in Just (x, QA xs []) 
    pop (QA (x:front) back) = Just (x, QA front back) 

あなたのクラスでの関数の残りの部分は、この歯磨き粉のチューブを通って圧迫することができます

...できる後入れ先出しキューとして：

newtype LIFO a = LIFO [a] 

instance Queue LIFO where 
    empty = LIFO [] 
    push x (LIFO xs) = LIFO (x:xs) 
    pop (LIFO []) = Nothing 
    pop (LIFO (x:xs)) = Just (x, LIFO xs) 

---

抽象度に優先度キューを含める場合は、優先度キューが優先度の高い要素を選択する方法を知る必要があり、指定されたインタフェースでは要素を比較する方法がないため、やや複雑になります。Queueをアップパッチを適用する一つの方法は、その要素の上に置く制約を指定するqを有効にする（MultiParamTypeClassesとFunctionalDependencies付き）ConstraintKinds拡張子を使用することです：

class Queue c q | q -> c where 
    empty :: c a => q a 
    push :: c a => a -> q a -> q a 
    pop :: c a => q a -> Maybe (a, q a) 

その後、我々は、例えば、使用したプライオリティキューを実装することができ、 スキューPlaying With Priority Queuesからヒープ ...

instance Queue Ord SkewHeap where -- SkewHeap requires that its elements be an instance of Ord 
    empty = Empty 
    push x q = q `merge` SkewNode x Empty Empty 
    pop Empty = Nothing 
    pop (SkewNode x l r) = Just (x, l `merge` r) 

...と、前の2つのキューが新しいQueueで動作するように適合させることができる...

class Trivial a 
instance Trivial a 

instance Queue Trivial QueueA where 
    {- as before -} 
instance Queue Trivial LIFO where 
    {- as before –}