haskell - Haskell でこのスタックタイプのファンクターを定義する

Question

これが私の Stack タイプを定義した方法です。もっと良い方法があるかもしれませんが、今のところこれに固執しましょう。

data Stack' v = Stack' [v] Int の導出 (表示)

したがって、プッシュのようなものは次のようになります

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)

誰かがファンクターの定義を手伝ってくれますか?

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、間違いを見つけてください。

type の値 (ここでは f は Stack') を提供し、 typef aの値を返す必要がありますf a。

また、 n が最初の引数の長さであるため、避けてみてください++。O(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

haskell - Haskell でこのスタック タイプのファンクターを定義する