O que é Banana split e fusão na programação funcional?

Esses termos foram mencionados no meu curso universitário. A pesquisa rápida no Google apontou alguns documentos da universidade, mas estou procurando uma explicação simples.

Mesmo que duas respostas já tenham sido fornecidas, não acho que a "divisão da banana" tenha sido explicada aqui ainda.

É de fato definido em "Programação Funcional com Bananas, Lentes, Envelopes e Arame Farpado, Erik Meijer Maarten Fokkinga, Ross Paterson, 1991"; esse artigo é difícil de ler (para mim) devido ao uso intenso de Squiggol. No entanto, "Um tutorial sobre a universalidade e expressividade da dobra, Graham Hutton, 1999" contém uma definição que é mais fácil de analisar:

Como um primeiro exemplo simples do uso da dobra para gerar tuplas, considere a função sumlength que calcula a soma e o comprimento de uma lista de números:

sumlength :: [Int] → (Int,Int)
sumlength xs = (sum xs, length xs)

Por uma combinação simples das definições de funções a soma e comprimento utilizando dobra dada anteriormente, a função sumlength pode ser redefinida como uma única aplicação de dobrar que gera um par de números a partir de uma lista de números:

sumlength = fold (λn (x, y) → (n + x, 1 + y)) (0, 0)

Essa definição é mais eficiente do que a definição original, porque faz apenas uma travessia sobre a lista de argumentos, em vez de duas travessias separadas. Generalizando a partir deste exemplo, qualquer par de aplicações de dobra para a mesma lista sempre pode ser combinado para fornecer uma única aplicação de dobra que gera um par, apelando para a chamada propriedade de 'banana split' da dobra (Meijer, 1992) . O nome estranho dessa propriedade deriva do fato de que o operador fold às vezes é escrito usando colchetes (| |) que se assemelham a bananas, e o operador de emparelhamento às vezes é chamado de split. Portanto, a combinação deles pode ser chamada de banana split!

Portanto, na verdade, isso é referenciado por um artigo de Meijer e alguns outros chamados " Programação Funcional com Bananas, Lentes, Envelopes e Arame Farpado ", a idéia básica é que podemos usar qualquer tipo de dados recursivos, como, por exemplo,

 data List = Cons Int List | Nil

e podemos fatorar a recursão em uma variável de tipo

 data ListF a = Cons Int a | Nil

a razão pela qual eu anexei isso Fé porque agora é um functor! Também nos permite imitar listas, mas com um toque: para criar listas, precisamos aninhar o tipo de lista

type ThreeList = ListF (ListF (ListF Void)))

Para recuperar nossa lista original, precisamos continuar aninhando isso infinitamente . Isso nos dará um tipo ListFFem que

  ListF ListFF == ListFF

Para isso, defina um "tipo de ponto fixo"

  data Fix f = Fix {unfix :: f (Fix f)}
  type ListFF = Fix ListF

Como exercício, você deve verificar se isso satisfaz a equação acima. Agora podemos finalmente definir o que são bananas (catamorfismos)!

  type ListAlg a = ListF a -> a

ListAlgs são o tipo de "lista de álgebras" e podemos definir uma função específica

  cata :: ListAlg a -> ListFF -> a
  cata f = f . fmap (cata f) . unfix

Além disso

  cata :: ListAlg a -> ListFF -> a
  cata :: (Either () (Int, a) -> a) -> ListFF -> a
  cata :: (() -> a) -> ((Int, a) -> a) -> ListFF -> a
  cata :: a -> (Int -> a -> a) -> ListFF -> a
  cata :: (Int -> a -> a) -> a -> [Int] -> a

Parece familiar? cataé exatamente o mesmo que dobras à direita!

O que é realmente interessante é que podemos fazer isso mais do que apenas listas, qualquer tipo definido com esse "ponto fixo de um functor" possui um catae, para acomodá-los, basta relaxar a assinatura de tipo

  cata :: (f a -> a) -> Fix f -> a

Na verdade, isso é inspirado em uma parte da teoria das categorias sobre a qual escrevi , mas essa é a carne do lado Haskell.

Embora jozefg tenha fornecido uma resposta, não tenho certeza se ela respondeu à pergunta. A "lei de fusão" é explicada no seguinte artigo:

Um tutorial sobre a universalidade e expressividade da dobra, GRAHAM HUTTON, 1999

Basicamente, diz que, sob algumas condições, você pode combinar ("fundir") a composição de uma função e dobrar em uma única dobra, basicamente

h · dobra gw = dobra fv

As condições para essa igualdade são

hw = v
h (gxy) = fx (hy)

A "banana split" ou "lei da banana split" é do artigo

Programação funcional com bananas, lentes, envelopes e arame farpado, Erik Meijer Maarten Fokkinga, Ross Paterson, 1991

Infelizmente, o artigo é muito difícil de decifrar, pois usa o formalismo de Bird-Meertens, de modo que não pude entender o que aconteceu. Tanto quanto eu entendi a "lei da divisão das bananas", diz que se você tiver duas dobras operando no mesmo argumento, elas poderão ser mescladas em uma única dobra.