Haskell "pseudo-functor"

Question

I have a polynomial

data Poly a = Poly [a]

I would like to be able to do something like fmap (take 3) polynomial but I can't since Poly isn't really a functor in that the f I use in fmap can only be of type [a] -> [b], not a -> b.

Is there an idiom or way I can express what I want?

---

EDIT: here is a function which does what I want

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

usage:

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

You can see from the type sig that it's almost fmap, but not quite. I'm obviously capable of writing the code for myMap, but I just want to know if there's another idiom I should be using instead.

Answer 1

Since you allow any function to be applied to the list of coefficients, your data type only really serves two purposes.

• You get extra type safety, since a Poly [a] is distinct from [a].
• You can define different instances.

If you don't need either of these, you might as well use a type alias.

type Poly a = [a]

Now you can apply any list function on it directly.

If, on the other hand, you want a distinct type, you might find the newtype package useful. For example, given this instance.

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

You can now write things like

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

although this might be overkill if your myMap is sufficient for your purposes.

---

All this aside, I think that exposing the representation of your data type in such a way might not be a good idea in the first place, as it can leave the rest of your code intimately dependent on this representation.

This makes it harder to change to a different representation at a later time. For example, you might want to change to a sparse representation like

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

where the Int is the power of the term. I suggest thinking about what operations you want to expose, and limiting yourself to those. For example, it might make sense to have a Functor instance that works on a per-element basis.

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

Now, the change to the sparse representation leaves client code unchanged. Only the instance (and the handful of other functions that depend on the representation) will have to change.

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

Answer 2

This doesn't work but I thought it was interesting enough to share anyway:

{-#LANGUAGE GADTs #-}

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

We now have a type Poly that's parameterized on a, but effectively a has to be 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

Now we can try and write an instance of Functor for this type:

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)

That's not going to work. Interestingly enough, we can't even really write myMap:

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

If we try this we get

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)

Of course we can fix it with a type annotation:

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

But without it, it's a similar problem to what fmap had. Functor just doesn't have anywhere to out this extra context of "I promise always to use lists", and indeed it can't really. You can always say undefined :: Poly Int for example. In short, I don't think there's really an idiom that could express this (actually, someone will probably come along with enough ghc extension magic to do it). Certainly not an existing one.