0

这就是我定义堆栈类型的方式。可能有更好的方法,但现在让我们坚持这个。

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

所以像 push' 这样的东西看起来像这样

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

但我无法为此定义函子。我的这次尝试失败了,说“Parse error in pattern: v”

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

有人可以帮我定义函子吗?

4

2 回答 2

3
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 是第一个参数的长度。

于 2012-09-12T13:56:26.210 回答
2

最简单的定义是:

{-# LANGUAGE DeriveFunctor #-}

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

你也应该避免length,因为它是O(n).

使用a : l而不是l ++ [a]- 列表只能有效地附加在它们的头部,附加到尾部是O(n)

push'可以通过移动来重写if

push' (Stack' l m) a = Stack' (if m <= length l then l else l ++ [a]) m
于 2012-09-12T15:12:33.820 回答