Defining functor for this stack type in haskell

0
votes

This is how I have define my Stack type. There could be better ways, but as of now lets stick for this one. 

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

So something like push' will look like this

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

But I am not able to define functor for this. My this attempt is failing saying that "Parse error in pattern: v"

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

Can someone help me in defining the functor?

2
haskellfunctor

2 Answers

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

Look at type of fmap :: Functor f => (a -> b) -> f a -> f b and you will find your mistake.

You need to provide a value of type f a (here f is Stack') and also return a value of type f a.

Also you should try avoiding ++ as it is O(n) where n is the length of first argument.

2
votes

The simplest definition is:

{-# LANGUAGE DeriveFunctor #-}

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

You should avoid length too because it's O(n).

Use a : l instead of l ++ [a] - lists can be only efficiently appended at their head, appending to tail is O(n).

Your push' can be rewritten by moving if inside:

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