Haskell "pseudo-funtor"

Question

tengo un polinomio

data Poly a = Poly [a] 

Me gustaría ser capaz de hacer algo como fmap (take 3) polynomial pero no puedo ya Poly no es realmente un funtor en que el f utilizo en fmap solo puede ser de tipo [a] -> [b], no a -> b.

¿Hay algún modismo o forma de expresar lo que quiero?

---

EDIT: aquí es una función que hace lo que quiero

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

uso:

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

Se puede ver en la sig tipo que es casi fmap, pero no bastante. Obviamente soy capaz de escribir el código para myMap, pero solo quiero saber si hay otro modismo que debería usar en su lugar.

Answer 1

Dado que permite que cualquier función se aplique a la lista de coeficientes, su tipo de datos solo tiene dos propósitos.

• Usted obtiene la seguridad de tipos adicional, ya que una Poly [a] es distinta de [a].
• Puede definir instancias diferentes.

Si no necesita ninguno de estos, también podría usar un alias de tipo.

type Poly a = [a] 

Ahora puede aplicar cualquier función de lista en él directamente.

Si, por otro lado, desea un tipo distinto, puede encontrar útil the newtype package. Por ejemplo, dada esta instancia.

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

Ahora puede escribir cosas como

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

aunque esto podría ser una exageración si su myMap es suficiente para sus propósitos.

---

Todo esto a un lado, creo que la exposición de la representación de su tipo de datos de tal manera que no sea una buena idea en primer lugar, ya que puede dejar el resto de su código depende íntimamente de esta representación .

Esto hace que sea más difícil cambiar a una representación diferente en otro momento. Por ejemplo, puede que desee cambiar a una representación escasa como

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

donde el Int es el poder de la palabra. Sugiero pensar qué operaciones quieres exponer y limitarte a ellas. Por ejemplo, podría tener sentido tener una instancia de Functor que funcione por elemento.

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

Ahora, el cambio a la representación dispersa no modifica el código del cliente. Solo la instancia (y el puñado de otras funciones que dependen de la representación) tendrán que cambiar.

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

Answer 2

esto no funciona, pero pensé que era lo suficientemente interesante para compartir todos modos:

{-#LANGUAGE GADTs #-} 

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

Ahora tenemos una poli tipo que está parametrizado en a, pero con eficacia a tiene que ser una lista:

~% 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 

Ahora podemos tratar de escribir una instancia de Functor para este tipo:

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) 

Eso no va a funcionar. Curiosamente, ni siquiera podemos escribir realmente myMap:

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

Si tratamos esto obtenemos

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) 

Por supuesto que podemos fijarlo con una anotación de tipo:

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

Pero sin eso, es un problema similar al que tenía fmap. Functor simplemente no tiene ningún lugar para salir de este contexto adicional de "Prometo siempre usar listas", y de hecho no puede. Siempre puede decir undefined :: Poly Int por ejemplo. En resumen, no creo que realmente haya una expresión idiomática que pueda expresar esto (en realidad, alguien probablemente vendrá con suficiente magia de extensión ghc para hacerlo). Ciertamente no es uno existente.