Хаскель "псевдо-функтор"

Question

У меня есть многочлен

data Poly a = Poly [a]

Я хотел бы иметь возможность сделать что-то вроде fmap (take 3) polynomial, но я не могу, поскольку Poly на самом деле не является функтором в этом fЯ использую в fmap может быть только тип [a] -> [b], а не a -> b.

Есть ли идиома или способ, которым я могу выразить то, что я хочу?

---

РЕДАКТИРОВАТЬ:вот функция, которая делает то, что я хочу

myMap :: ([a] ->[b]) -> P a -> P b
myMap f (P x) = P (f x)

использование:

*Main> myMap (take 3) (P [1..])
P [1,2,3]

Вы можете увидеть из типа sig, что это почти fmap, но не совсем,Я, очевидно, способен написать код для myMap, но я просто хочу знать, есть ли другой вариант, который я должен использовать вместо этого.

Answer 1

Поскольку вы разрешаете применять любую функцию к списку коэффициентов, ваш тип данных действительно служит только двум целям.

• Вы получаете дополнительную безопасность типов, поскольку Poly [a] отличается от [a].
• Вы можете определить разные экземпляры.

Если вам не нужен ни один из них, вы можете также использовать псевдоним типа.

type Poly a = [a]

Теперь вы можете применить к нему любую функцию списка напрямую.

Если, с другой стороны, вам нужен отдельный тип, вы можете найти пакет newtype полезным.Например, для данного экземпляра.

instance Newtype (Poly a) [a] where
  pack = Poly
  unpack (Poly x) = x

Теперь вы можете писать такие вещи, как

foo :: Poly a -> Poly a
foo = over Poly (take 3)

, хотя это может быть излишним, если ваш myMap достаточен для ваших целей.

---

Помимо всего этого, я думаю, что представление представления вашего типа данных таким образом, возможно, не было бы хорошей идеей, так как это может оставить остальную часть вашего кода в тесной зависимости от этого представления.

Это затрудняет переход к другому представлению в более позднее время.Например, вы можете захотеть перейти к разреженному представлению, например

data Poly a = Poly [(a, Int)]

, где Int - это сила термина.Я предлагаю подумать о том, какие операции вы хотите раскрыть, и ограничиться ими.Например, может иметь смысл иметь экземпляр Functor, который работает для каждого элемента.

instance Functor Poly where
    fmap f (Poly x) = Poly $ map f x

Теперь изменение разреженного представления оставляет код клиента неизменным.Только экземпляр (и несколько других функций, которые зависят от представления) должны будут измениться.

instance Functor Poly where
    fmap f (Poly x) = Poly $ map (first f) x

Answer 2

Это не работает, но я подумал, что все равно было достаточно интересно поделиться:

{-#LANGUAGE GADTs #-}

data Poly a where
   Poly :: [b] -> Poly [b]

Теперь у нас есть тип Poly, который параметризован на a, но фактически a должен бытьlist:

~% ghci Poly.hs
GHCi, version 6.8.2: http://www.haskell.org/ghc/  :? for help
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( Poly.hs, interpreted )
Ok, modules loaded: Main.
*Main> :k Poly
Poly :: * -> *
*Main> :t Poly
Poly :: [b] -> Poly [b]
*Main> case Poly [1,2,3] of _ -> 0
0
*Main> case Poly 4 of _ -> 0

<interactive>:1:10:
    No instance for (Num [b])
      arising from the literal `4' at <interactive>:1:10
    Possible fix: add an instance declaration for (Num [b])
    In the first argument of `Poly', namely `4'
    In the scrutinee of a case expression: Poly 4
    In the expression: case Poly 4 of _ -> 0
*Main> case Poly True of _ -> 0

<interactive>:1:10:
    Couldn't match expected type `[b]' against inferred type `Bool'
    In the first argument of `Poly', namely `True'
    In the scrutinee of a case expression: Poly True
    In the expression: case Poly True of _ -> 0

Теперь мы можем попытаться написать экземпляр Functor для этого типа:

instance Functor Poly where
  fmap f (Poly x) = Poly (f x)

Couldn't match expected type `[b1]' against inferred type `b2'
  `b2' is a rigid type variable bound by
       the type signature for `fmap' at <no location info>
In the first argument of `Poly', namely `(f x)'
In the expression: Poly (f x)
In the definition of `fmap': fmap f (Poly x) = Poly (f x)

Это не сработает.Интересно, что мы даже не можем написать myMap:

polymap f (Poly x) = Poly (f x)

Если мы попробуем это, мы получим

GADT pattern match in non-rigid context for `Poly'
  Tell GHC HQ if you'd like this to unify the context
In the pattern: Poly x
In the definition of `polymap': polymap f (Poly x) = Poly (f x)

Конечно, мы можем исправить это с помощью аннотации типа:

 polymap :: ([a] -> [b]) -> Poly [a] -> Poly [b]

Но без него это та же проблема, что и у fmap.У Functor просто нет места для этого дополнительного контекста «я обещаю всегда использовать списки», и это действительно невозможно.Вы всегда можете сказать undefined :: Poly Int например.Короче говоря, я не думаю, что на самом деле есть идиома, которая могла бы выразить это (на самом деле, кто-то, вероятно, придет с достаточным количеством магии расширения ghc, чтобы сделать это).Конечно, не существующий.