在haskell中定义此堆栈类型的仿函数

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) 

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

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

最简单的定义是：

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