Piegamento senza istanza monoide

Question

Ho una semplice struttura dell'albero:

data Tree a = Leaf | Node a (Tree a) (Tree a)

E a Pieghevole implementazione:

import qualified Data.Foldable as F

instance F.Foldable Tree where
  foldMap f Leaf         = mempty
  foldMap f (Node x l r) = F.foldMap f l `mappend`
                           f x           `mappend`
                           F.foldMap f r

E funziona anche se non c'è implementazione per Monoid E non posso usare nessuno dei due mappend né mempty nel mio codice. Allora come fa questo Foldable lavoro di implementazione?

Answer 1

Se esamini il tipo per foldMap

class Foldable f where
  foldMap :: Monoid m => (a -> m) -> f a -> m

Vedrai che ha un tipo illimitato m. Generalmente quando ciò si verifica significa che m potrebbe essere qualsiasi cosa, ma qui si limita anche m insieme a Monoid m. È lì il Monoid viene da.

Vale la pena notare che se non avessimo il Monoid L'istanza quindi è abbastanza difficile definire una funzione che restituisce un valore che "potrebbe essere qualsiasi cosa". Se lo provi, scoprirai che è quasi impossibile (senza "imbrogliare").

impossible :: Int -> b -- no constraints on `b` at all!
impossible i = ...?

Ma è abbastanza facile se sappiamo un po 'del tipo

veryPossible  :: Num b => Int -> b
veryPossible  i = fromIntegral i
-- or
veryPossible2 i = fromIntegral (i * i) + fromIntegral i

---

Come un altro esempio, considera il tipo di espressione

expr m = mconcat [m <> m <> mempty, mempty <> m]

Poiché questa espressione è costruita in base a un valore sconosciuto m e usi solo le funzioni in Monoid Classe o loro derivati, il suo tipo lo riflette. Il tipo più generale di expr è

expr :: Monoid m => m -> m

Ancora una volta qui, m è una variabile di tipo libero vincolato per essere alcuni Monoid.

---

La ragione foldMap ti consente di usare Monoid funzioni è perché limita esplicitamente i tipi di cose che il m Nel suo tipo di firma può essere. Mettendo i vincoli lì guadagniamo più potere per manipolarli.