Haskell "pseudo-funtore"

Question

Ho un polinomio

data Poly a = Poly [a] 

mi piacerebbe essere in grado di fare qualcosa di simile fmap (take 3) polynomial ma non posso dato Poly non è davvero un funtore in quanto il f uso in fmap può essere solo di tipo [a] -> [b], non a -> b.

C'è un idioma o un modo in cui posso esprimere quello che voglio?

---

EDIT: qui è una funzione che fa quello che voglio

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

utilizzo:

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

Si può vedere dal tipo in ordine a che è quasi FMAP, ma non abbastanza. Sono ovviamente in grado di scrivere il codice per myMap, ma voglio solo sapere se c'è un altro idioma che dovrei usare al suo posto.

Answer 1

Poiché si consente l'applicazione di qualsiasi funzione all'elenco di coefficienti, il tipo di dati serve solo a due scopi.

• Si ottiene la sicurezza di tipo in più, dal momento che un Poly [a] è distinto da [a].
• È possibile definire diverse istanze.

Se non è necessario uno di questi, è consigliabile utilizzare un alias di tipo.

type Poly a = [a] 

Ora è possibile applicare direttamente qualsiasi funzione di elenco.

Se, al contrario, si desidera un tipo distinto, è possibile trovare utile the newtype package. Ad esempio, data questa istanza.

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

È ora possibile scrivere le cose come

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

anche se questo potrebbe essere eccessivo se il myMap è sufficiente per i vostri scopi.

---

Tutto questo a parte, penso che esporre la rappresentazione del tipo di dati in modo tale potrebbe non essere una buona idea, in primo luogo, come si può lasciare il resto del codice intimamente dipendente da questa rappresentazione .

Ciò rende più difficile modificare una rappresentazione diversa in un secondo momento. Ad esempio, si potrebbe desiderare di passare a una rappresentazione sparsa come

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

dove il Int è il potere del termine. Suggerisco di pensare a quali operazioni vuoi esporre e limitarti a quelle. Ad esempio, potrebbe avere senso avere un'istanza Functor che funzioni su una base per elemento.

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

Ora, la modifica alla rappresentazione sparsa lascia il codice client invariato. Solo l'istanza (e la manciata di altre funzioni che dipendono dalla rappresentazione) dovrà cambiare.

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

Answer 2

Questo non funziona, ma ho pensato che era abbastanza interessante da condividere in ogni caso:

{-#LANGUAGE GADTs #-} 

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

Ora abbiamo un tipo Poly che è parametrizzata su a, ma efficace a deve essere 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 

Ora possiamo provare a scrivere un'istanza di Functor per questo 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) 

Non funzionerà. È interessante notare, non possiamo ancora veramente scrivere myMap:

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

Se proviamo questo otteniamo

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) 

Naturalmente possiamo risolvere il problema con un tipo di annotazione:

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

Ma senza di esso, è un problema simile a quello che aveva fmap. Functor semplicemente non ha da nessuna parte fuori questo contesto extra di "Prometto sempre di usare le liste", e in effetti non può davvero. Ad esempio, puoi sempre dire undefined :: Poly Int. In breve, non penso che ci sia davvero un idioma che potrebbe esprimere questo (in realtà, qualcuno probabilmente verrà con abbastanza magia ghc per farlo). Certamente non uno esistente.