Funcip e tipi non induttivi

Question

Sto lavorando alla sezione su Funcitors nel Typeclassopedia.

Una semplice intuizione è che un Functor rappresenta un "contenitore" di qualche tipo, insieme alla possibilità di applicare una funzione in modo uniforme a ogni elemento nel contenitore.

OK. Quindi, i funtori appaiono piuttosto naturali per tipi induttivi come liste o alberi.

Anche i caratteri appaiono piuttosto semplici se il numero di elementi è fissato su un numero basso. Ad esempio, con Forse devi solo preoccuparti di "Nothing" o "Just a" - due cose.

Quindi, come creere qualcosa come un grafico, che potrebbe potenzialmente avere loop, un'istanza di Functor? Penso che un modo più generalizzato per dirlo è, in che modo i tipi non-induttivi "si adattano" ai Functional?

---

Più ci penso, più mi rendo conto che l'induttivo/non induttivo non ha molta importanza. tipi induttivi sono solo più facili per definire fmap per ...

Se volevo fare un grafico un'istanza di Functor, avrei dovuto implementare un algoritmo grafico attraversamento all'interno FMAP; per esempio probabilmente dovrebbe usare una funzione di supporto che tenga traccia dei nodi visitati. A questo punto, mi chiedo ora perché preoccuparsi di definirlo come un Functor invece di scrivere solo questo come funzione stessa? Per esempio. mappa vs fmap per gli elenchi ...?

Spero che qualcuno con esperienza, storie di guerra e cicatrici possa far luce. Grazie!

Answer 1

Bene supponiamo che si definisce un grafico come questo

data Graph a = Node a [Graph a] 

Poi fmap è appena definito esattamente come ci si aspetterebbe

instance Functor Graph where 
    fmap f (Node a ns) = Node (f a) (map (fmap f) ns) 

Ora, se c'è un ciclo, allora avremmo dovuto fare qualcosa come

foo = Node 1 [bar] 
bar = Node 2 [foo] 

Ora fmap è su è faticosamente pigro che puoi valutare parte del suo risultato senza forzare il resto del calcolo, quindi funziona altrettanto bene di qualsiasi rappresentazione graficata legata al nodo!

In generale questo è il trucco: fmap è pigro in modo da poter trattare i risultati proprio come si tratterebbe qualsiasi valore non induttivo in Haskell (: attentamente).

Inoltre, è necessario definire fmap vs gli casuali altre funzioni dal

1. fmap è una buona, API ben noto con regole
2. contenitore ora mette bene con le cose aspettandosi Functor s
3. Puoi estrai altri bit del tuo programma in modo che dipendano da Functor, non dal tuo grafico

In generale quando vedo qualcosa è un funtore penso "Ah meravigliosa, so solo come utilizzare questo" e quando vedo

superAwesomeTraversal :: (a -> b) -> Foo a -> Foo b 

ho un po 'preoccupato che questo farà cose inaspettate ..