haskell - 在haskell中为这种堆栈类型定义函子

Question

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

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)

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

score 3 · Accepted Answer

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

score 2 · Accepted Answer

最简单的定义是：

{-# 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

2 回答 2