일반 '타입이없는'Haskell의 스택

Question

내가 작업중인 것을 위해 일반적인 스택을 구현해야한다. 이 스택은 다른 유형의 요소를 보유 할 수 있어야합니다. 예를 들어, (1, 'c', True, "Strings"). 지원되는 기능은 top, pop 및 push입니다.

튜플이 가장 기본적인 아이디어입니다.

push x s = (x,s) 
pop s = snd s 
top s = (fst s, s) 

하지만 빈 스택도 지원해야합니다. 여기서 pop과 top은()에 정의되어 있지 않습니다. 그래서 새로운 유형을 만들려고했습니다. 내가 함께이 문제를 해결하는 경우

Couldn't match expected type ‘b’ with actual type ‘x’ 
    because type variable ‘x’ would escape its scope 
This (rigid, skolem) type variable is bound by 
    a pattern with constructor 
    Cons :: forall x. (x, Stack) -> Stack, 
    in a case alternative 
    at try.hs:11:9-18 
Relevant bindings include 
    x :: x (bound at try.hs:11:15) 
    top :: Stack -> (Either() b, Stack) (bound at try.hs:9:1) 
In the first argument of ‘Right’, namely ‘x’ 
In the expression: Right x 

:

data Stack x = Empty | forall y. Cons (x, Stack y) 

나는 팝에 대해 동일한 오류가 여기에

data Stack = Empty | forall x. Cons (x, Stack) 
push x s = Cons (x,s) 
pop s = case s of 
     Empty -> Left s 
     Cons (x, y) -> Right y 
top s = case s of 
     Empty -> (Left(), s) 
     Cons (x,y) -> (Right x, s) 

는, 최고는 나에게 오류를 제공합니다.

나는이를 추가하는 시도 :

type AnyStack = forall x. Stack x 

그러나 다시 비슷한 오류 얻을 :

이

Couldn't match expected type ‘b’ with actual type ‘Stack y’ 
    because type variable ‘y’ would escape its scope 
This (rigid, skolem) type variable is bound by 
    a pattern with constructor 
    Cons :: forall x y. (x, Stack y) -> Stack x, 
    in a case alternative 
    at try.hs:8:9-19 
Relevant bindings include 
    y :: Stack y (bound at try.hs:8:18) 
    pop :: Stack t -> Either (Stack t) b (bound at try.hs:6:1) 
In the first argument of ‘Right’, namely ‘y’ 
In the expression: Right y 

사람이 스택의 이런 종류의 권리 유형 서명 또는 형식 정의 좀 도와 수를 ? 아니면 이것에 관련된 좋은 참고 서를 가르쳐 주시겠습니까?

고맙습니다.

편집 :

나는 또한이 스택에 대한 get 함수를 포함 할 수있을 것입니다 경우가 완벽 할 것입니다. 정수 i와 스택 s가 주어지면 get은 s의 i 번째 요소를 반환합니다. 나는 언젠가 밀어 넣기, 팝과 윗부분을 정렬 해 놓았지만 아마도 나 자신을 할 수있을 것이라고 기대했다. 이 사람들에 관한 아이디어가 있습니까?

Answer 1

유형을 지정해야합니까?

{-# LANGUAGE GADTs, DataKinds, KindSignatures, TypeOperators #-} 
{-# LANGUAGE FlexibleInstances, FlexibleContexts #-} 

module Stack (Stack(..), push, pop, top, empty) where 

data Stack (h :: [*]) where 
    Empty :: Stack '[] 
    Push :: x -> Stack xs -> Stack (x ': xs) 

instance Show (Stack '[]) where 
    showsPrec d Empty = showParen (d > 11) $ showString "Empty" 

instance (Show x, Show (Stack xs)) => Show (Stack (x ': xs)) where 
    showsPrec d (Push x xs) = showParen (d > 10) $ 
     showString "Push " . showsPrec 11 x . showChar ' ' . showsPrec 11 xs 

instance Eq (Stack '[]) where 
    _ == _ = True 

instance (Eq x, Eq (Stack xs)) => Eq (Stack (x ': xs)) where 
    (Push x xs) == (Push y ys) = x == y && xs == ys 

instance Ord (Stack '[]) where 
    compare _ _ = EQ 

instance (Ord x, Ord (Stack xs)) => Ord (Stack (x ': xs)) where 
    compare (Push x xs) (Push y ys) = case compare x y of 
    EQ -> compare xs ys 
    LT -> LT 
    GT -> GT 


push :: x -> Stack xs -> Stack (x ': xs) 
push = Push 

pop :: Stack (x ': xs) -> Stack xs 
pop (Push _ xs) = xs 

top :: Stack (x ': xs) -> x 
top (Push x _) = x 

empty :: Stack '[] 
empty = Empty 

ghci에서 몇 가지 용도는 다음과 같이 : 고급 GHC 기능을 사용하고자하는 경우, 당신은 같은 것을 할 수있는이 표현은 좋은 기능이

[1 of 1] Compiling Stack   (typelist.hs, interpreted) 
Ok, modules loaded: Stack. 
*Stack> :t push True . push (Just 'X') . push 5 . push "nil" $ empty 
push True . push (Just 'X') . push 5 . push "nil" $ empty 
    :: Num x => Stack '[Bool, Maybe Char, x, [Char]] 
*Stack> push True . push (Just 'X') . push 5 . push "nil" $ empty 
Push True (Push (Just 'X') (Push 5 (Push "nil" Empty))) 
*Stack> pop . push True . push (Just 'X') . push 5 . push "nil" $ empty 
Push (Just 'X') (Push 5 (Push "nil" Empty)) 
*Stack> pop empty 

<interactive>:75:5: 
    Couldn't match type ‘'[]’ with ‘x0 : xs’ 
    Expected type: Stack (x0 : xs) 
     Actual type: Stack '[] 
    Relevant bindings include 
     it :: Stack xs (bound at <interactive>:75:1) 
    In the first argument of ‘pop’, namely ‘empty’ 
    In the expression: pop empty 

하는 것으로를 그 빈 스택에 pop 또는 top을 호출하는 것은 컴파일 타임 오류입니다. 하지만, 비어 있지 않은 스택으로 호출하는 것을 항상 증명해야하기 때문에 작업하기가 다소 힘듭니다. 버그를 예방하는 데는 좋지만 때로 컴파일러를 설득하기 위해 더 많은 부기가 필요할 때가 있습니다. 이 표현이 좋은 선택이라는 것은 확실하지 않습니다. 사용 사례에 따라 다릅니다.

Answer 2

빈 튜플에 pop을 정의 할 수 없어야하지만 나머지는 유형 클래스를 사용하여 스택 유형에 대한 사례를 표현할 수있을 정도로 충분히 부드럽습니다. 당신이 추상적으로

sempty :: S() 
sempty = S() 

과 함께 푸시/팝/상단과 S를 노출하는 경우

class Stack h where 
    push :: a -> h x -> h (a, x) 
    pop :: h (a, x) -> (h x, a) 
    top :: h (a, x) -> (h (a, x), a) 
    top hax = let (_, a) = pop hax in (hax, a) 

newtype S x = S x 

instance Stack S where 
    push a (S x) = S (a, x) 
    pop (S (a, x)) = (S x, a) 

당신은 아무도 병적 인 스택을 구축 할 수 없음을 보장 할 수 있습니다. GADT에 문제가 없다면 더 좋은 인코딩이 있습니다.

data S h where 
    Nil :: S() 
    Cons :: a -> S x -> S (a, x) 

이 GADT는 이미 유형 위반이 없으므로 직접 노출 할 수 있습니다.

instance Stack S where 
    push = Cons 
    pop (Cons a x) = (x, a)