Dobrando sem instância Monoid

Question

Eu tenho uma estrutura de árvore simples:

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

E um Dobrável implementação:

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 funciona mesmo que não haja implementação para Monoid e não posso usar nenhum dos dois mappend nem mempty no meu código.Então como isso Foldable trabalho de implementação?

Answer 1

Se você examinar o tipo para foldMap

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

Você verá que ele tem um tipo não vinculado m.Geralmente quando isso ocorre significa que m poderia ser qualquer coisa, mas aqui também restringe m com Monoid m.É aí que Monoid vem de.

Vale a pena notar que se não tivéssemos o Monoid Por exemplo, é muito difícil definir uma função que retorne um valor que "poderia ser qualquer coisa".Se você tentar, descobrirá que é quase impossível (sem “trapaça”).

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

Mas é muito fácil se soubermos um pouco sobre o tipo

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

---

Como outro exemplo, considere o tipo da expressão

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

já que esta expressão é construída com base em algum valor desconhecido m e usa apenas as funções no Monoid class ou seus derivados, seu tipo reflete isso.O tipo mais geral de expr é

expr :: Monoid m => m -> m

Novamente aqui, m é uma variável de tipo livre restrita a ser alguns Monoid.

---

A razão foldMap permite que você use Monoid funções é porque restringe explicitamente os tipos de coisas que o m em sua assinatura de tipo pode ser.Ao colocar restrições aí, ganhamos mais poder para manipulá-las.