Lei do tipo [[a]] -> ([a], [a])

8

Estou tentando fazer esta pergunta do meu dever de casa:

Dado arbitrário foo :: [[a]] -> ([a], [a]), escreva uma lei que a função foosatisfaça, envolvendo maplistas e pares.

Algum contexto: Eu sou o primeiro ano de graduação fazendo um curso de programação funcional. Embora o curso seja bastante introdutório, o palestrante mencionou muitas coisas dos conteúdos programáticos, entre as quais os teoremas livres. Então, depois de tentar ler o artigo de Wadler, deduzi que, concat :: [[a]] -> [a]com a lei, map f . concat = concat . map (map f)parece relevante para o meu problema, já que precisamos ter foo xss = (concat xss, concat' xss)onde concate onde concat'houver funções do tipo [[a]] -> [a]. Então foosatisfaz bimap (map f, map g) . foo = \xss -> ((fst . foo . map (map f)) xss, (snd . foo . map (map g)) xss).

Essa "lei" já parece longa demais para ser correta, e também não tenho certeza da minha lógica. Então, pensei em usar um gerador de teoremas gratuitos on-line , mas não entendi o que lift{(,)}significa:

forall t1,t2 in TYPES, g :: t1 -> t2.
 forall x :: [[t1]].
  (f x, f (map (map g) x)) in lift{(,)}(map g,map g)

lift{(,)}(map g,map g)
  = {((x1, x2), (y1, y2)) | (map g x1 = y1) && (map g x2 = y2)}

Como devo entender essa saída? E como devo derivar a lei para a função foocorretamente?

haskell free-theorem Jingjie YANG
fonte
5
Eu acredito que isto está dizendo o seguinte:(\(a,b) -> (map f a, map f b)) . foo = foo . map (map f)
AJFarmar 15/12/19

Respostas:

4

Se R1e R2são relações (digamos, R_ientre A_ie B_icom i in {1,2}), então lift{(,)}(R1,R2)são os pares de relações "elevados", entre A1 * A2e B1 * B2com a *designação do produto (escrito (,)em Haskell).

Na relação levantada, dois pares (x1,x2) :: A1*A2e (y1,y2) :: B1*B2são relacionados se e somente se x1 R1 y1e x2 R2 y2. No seu caso, R1e R2são funções map g, map g, de modo que o levantamento se torna uma função, bem como: y1 = map g x1 && y2 = map g x2.

Portanto, o gerado

(f x, f (map (map g) x)) in lift{(,)}(map g,map g)

significa:

fst (f (map (map g) x)) = map g (fst (f x))
AND
snd (f (map (map g) x)) = map g (snd (f x))

ou, em outras palavras:

f (map (map g) x) = (map g (fst (f x)), map g (snd (f x)))

que eu escreveria como, usando Control.Arrow:

f (map (map g) x) = (map g *** map g) (f x)

ou mesmo, no estilo pointfree:

f . map (map g) = (map g *** map g) . f

Isso não é surpresa, pois você fpode ser escrito como

f :: F a -> G a
where F a = [[a]]
      G a = ([a], [a])

e F, Gsão functors (em Haskell seria preciso usar um newtypepara definir uma instância functor, mas vou omitir que, uma vez que é irrelevante). Nesse caso comum, o teorema livre tem uma forma muito agradável: para cada g,

f . fmap_of_F g = fmap_of_G g . f

Essa é uma forma muito agradável, chamada naturalidade ( fpode ser interpretada como uma transformação natural em uma categoria adequada). Observe que os dois fs acima são realmente instanciados em tipos separados, para fazer com que os tipos concordem com o restante.

No seu caso específico, uma vez F a = [[a]]que é a composição do []functor , ele é o que obtemos (sem surpresa) fmap_of_F g = fmap_of_[] (fmap_of_[] g) = map (map g).

Em vez disso, G a = ([a],[a])é a composição dos functores []e H a = (a,a)(tecnicamente, o diagonal é composto com o produto). Nós temos fmap_of_H h = (h *** h) = (\x -> (h x, h x)), a partir do qual fmap_of_G g = fmap_of_H (fmap_of_[] g) = (map g *** map g).

chi
fonte
Boa explicação! Apenas uma pergunta: quando você diz "para cada g", g precisa ser total ou estrito ou não há restrições?
Jingjie YANG
1
@JingjieYANG Sim, existem algumas restrições se usarmos o Haskell. A maioria dos resultados como esse é realmente feita em um sistema de tipo puro, onde todos terminam (portanto, é total). Em Haskell, se bem me lembro, uma vez que não temos rescisão, precisamos exigir gtotal. Da mesma forma, como temos seq, precisamos exigir gque seja rigoroso. Não tenho 100% de certeza sobre as restrições exatas, mas acho que devem ser essas. Mas não me lembro onde li sobre isso - provavelmente na página do gerador de teoremas livres, há algumas informações.
21719 chi
Control.Arrow (***) não é um pouco fora de moda, em favor de Data.Bifunctor (bimap)? Alguma objeção a uma edição para mudar para a última?
Joseph Sible-Reinstate Monica
2
@ JosephSible-ReinstateMonica Não faço ideia. Eu acho que é um pouco como mapvs fmap. As pessoas continuam usando, mappois torna óbvio que estamos lidando com listas (e não com outro functor). Da mesma forma, (***)só funciona em pares (e não em outros bifuncionais). Provavelmente o estou usando principalmente para o seu infix-ness, já que em matemática tendemos a escrever f \times gpara aplicar o bifunctor do produto. Talvez bimapdeva ter sua variante infix também, como <$>é uma variante para fmap.
chi
1
Embora seja verdade que (***)seja mais específico do bimapque apenas trabalhando em pares, em vez de bifuncionais arbitrários, também é verdade que bimapé mais específico do (***)que apenas trabalhando em funções e não em setas arbitrárias. Re infix, isso não seria o mesmo bimape fmap, já que bimapleva 3 parâmetros e fmapleva apenas 2. #
9788 Joseph Sible-Reinstate Monica
2

A mesma coisa que a resposta de @ chi com menos cerimônia:

Não importa se você muda as para bs antes ou depois da função, você obtém a mesma coisa (desde que use uma fmapcoisa parecida para fazer isso).

Para qualquer f: a -> b,

    [[a]] -------------> [[b]]
      | (map.map) f |
      | |
     foo foo
      | |
      vv
    ([a], [a]) ---------> ([b], [b])
              bimap ff

comuta.
luqui
fonte