haskell에서이 스택 유형에 대한 functor 정의

Question

이것은 스택 유형을 정의하는 방법입니다. 더 나은 방법이있을 수 있지만 지금은이 방법을 고집합니다.

 
data Stack' v = Stack' [v] Int deriving (Show) 

그래서 푸시 같은 '는이

push' :: (Ord v) => Stack' v -> v -> Stack' v 
push' (Stack' l m) a = if m <= length l then Stack' l m else Stack' (l ++ [a]) m 

모양을하지만 이것을 위해 펑터를 정의 할 수 없습니다입니다. 이 시도는 "패턴의 구문 분석 오류 : v"라고 말하지 않습니다.

instance Functor Stack' where 
    fmap f (v l) = (map f v) (l) 

누군가가 저에게 functor를 정의하는 데 도움을 줄 수 있습니까?

Answer 1

instance Functor Stack' where 
    fmap f (Stack' v l) = Stack' (map f v) (l) 

유형을 살펴보고 fmap :: Functor f => (a -> b) -> f a -> f b을 보면 실수를하게됩니다.

f a (여기서 f는 Stack ') 유형의 값을 제공하고 f a 값을 반환해야합니다.

마찬가지로 ++이 O(n) 인 것처럼 피하십시오. 여기서 n은 첫 번째 인수의 길이입니다.

Answer 2

가장 간단한 정의는 : 그것은 O(n)을 때문에 당신이 너무 length을 피해야한다

{-# LANGUAGE DeriveFunctor #-} 

data Stack' v = Stack' [v] Int deriving (Show, Functor) 

.

l ++ [a] 대신 a : l을 사용하십시오. 머리말에 목록을 효율적으로 추가 할 수 있으며 꼬리에 추가하면 O(n)이됩니다.

당신의 push' 내부 if를 이동하여 다시 작성할 수 있습니다 : 피할 수

push' (Stack' l m) a = Stack' (if m <= length l then l else l ++ [a]) m