Questa inferenza di tipo Haskell è in azione o qualcos'altro?

Question

Sto lavorando attraverso il libro online LYAH (il collegamento ti porterà direttamente alla sezione che riguarda la mia domanda).

L'autore definisce un tipo di dati albero binario, e mostra come può essere fatto un'istanza del tipo pieghevole (definito in Data.Foldable) implementando la funzione foldMap:

import Data.Monoid 
import qualified Data.Foldable as F 

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) 

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

Il tipo di dichiarazione foldMap è la seguente:

F.foldMap :: (Monoid m, F.Foldable t) => (a -> m) -> t a -> m 

quindi prende una funzione che prende un'istanza di tipo "a" e restituisce un monoide.

Ora, come ad esempio, l'autore crea un'istanza albero

testTree = Node 5 
       (Node 3 
        (Node 1 Empty Empty) 
        (Node 6 Empty Empty) 
       ) 
       (Node 9 
        (Node 8 Empty Empty) 
        (Node 10 Empty Empty) 
       ) 

e svolge le seguenti piega (definito per i tipi di pieghevoli):

F.foldl (+) 0 testTree -- the answer is 42 (sum of the Node Integers) 

La mia domanda è, come fa Haskell capire quell'aggiunta al tipo Integer - l'interrogazione di Haskell per il tipo di testTree da Tree [Intero] - può essere vista come un'operazione monoid (se la mia terminologia è corretta)?

(La mia tentativo di risposta: L'autore alcuni paragrafi prima di questa sezione viene descritto come il Num tipo può essere interpretato come un Monoide tipo in due modi diversi, avvolgendoli nel Somma e prodotto tipo con (+) e (*) come mappend funzioni e 0 e 1 come elemento mempty, rispettivamente. è il tipo di "a" in (Albero a) essendo in qualche modo dedotto come appartenenti al tipo Sum (il modo in cui Hask ell variamente interpreta valori numerici in base al contesto) o è qualcos'altro interamente? ]

Answer 1

La mia domanda è, come fa Haskell capire che oltre il tipo Integer - interrogazione Haskell per il tipo di testTree dà Albero [Integer] - può essere visto come un'operazione monoidale (se la mia terminologia è corretta)?

Non può! In effetti, non esiste l'istanza Monoid per Integer.

Ora, non fraintendetemi - gli interi sono un monoide in aggiunta. Sono anche monoide sotto moltiplicazione, tuttavia, e Haskell non ha modo di sapere quale usare, da cui i wrapper newtype.

Ma ... niente di tutto ciò che sta succedendo qui. Passare a ...

(Il mio tentativo di risposta: l'autore di alcuni paragrafi prima di questa sezione descrive come il tipo di Num può essere interpretato come un tipo di Monoid in due modi diversi, avvolgendoli in Somma e Tipo di prodotto con (+) e (*) come funzioni di mappend e rispettivamente 0 e 1 come l'elemento di mempty.Il tipo di "a" in (Albero a) viene in qualche modo inferito come appartenente al tipo di Somma (il modo Haskell interpreta variamente valori numerici in base al contesto) o si tratta di qualcosa di completamente diverso?]

Non

una cattiva supposizione, ma quel genere di inferenza (trovare l'istanza utilizzando Sum sulla base delle argomentazioni voi dato) è al di là di ciò che Haskell può fare per te.

Ci sono due punti chiave qui: in primo luogo, il vincolo Monoid viene utilizzato solo per alcune funzioni, non per le piegature in generale. In particolare, lo foldl non ha realmente bisogno di un'istanza Monoid, perché si fornisce sia l'operazione binaria che il valore iniziale da utilizzare.

Il secondo punto è quello che ho il sospetto che sei veramente dopo - come si crea un generico foldl che non ha bisogno di un Monoid, quando tutto quello che è stato definito foldMap, che fa? Per rispondere a questa, possiamo semplicemente look at the default implementation di foldl:

foldl :: (a -> b -> a) -> a -> t b -> a 
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z 

Qui, Endo is another newtype wrapper, in particolare per le funzioni a -> a dando la Monoid della composizione, con id come l'identità, mentre Dual is a wrapper che inverte la direzione di un Monoid. Quindi lo Monoid che sta effettivamente utilizzando qui è quindi in grado di incollare gli usi di (+) insieme alla composizione della funzione, quindi applicare il risultato al valore di inizializzazione.

Answer 2

Il monoid non è effettivamente utilizzato qui. L'ultima riga utilizza F.foldl che ha la firma F.Foldable t => (a -> b -> a) -> a -> t b -> a. Fondamentalmente stai 'manualmente' usando un monoide fornendo (+) e 0.

Se vuoi usare un monoide 'implicitamente', puoi usare F.fold (che ha la firma (F.Foldable t, Monoid m) -> t m -> m). In questo caso, se lo provate, si otterrà:

*Main> F.fold testTree 

<interactive>:1:1: 
    No instance for (Monoid Integer) 
     arising from a use of `F.fold' 
    Possible fix: add an instance declaration for (Monoid Integer) 
    In the expression: F.fold testTree 
    In an equation for `it': it = F.fold testTree 
*Main> :t F.foldl 

Ora, GHCI si lamenta che non v'è alcuna istanza Monoide per intero, come dovrebbe. Devi selezionare Somma o Prodotto avvolgendo il numero intero. Per questo siamo in grado di utilizzare F.foldMap (firma (F.Foldable t, Monoid m) => (a -> m) -> t a -> m):

*Main> F.foldMap Sum testTree 
Sum {getSum = 42}