O que é "levantamento" em Haskell?

138

Não entendo o que é "levantar". Devo primeiro entender mônadas antes de entender o que é um "elevador"? (Também sou completamente ignorante sobre mônadas :) Ou alguém pode me explicar com palavras simples?

GabiMe
fonte
9
Talvez útil, talvez não: haskell.org/haskellwiki/Lifting
kennytm

Respostas:

179

O levantamento é mais um padrão de design do que um conceito matemático (embora eu espere que alguém por aqui agora me refute, mostrando como os elevadores são uma categoria ou algo assim).

Normalmente você tem algum tipo de dado com um parâmetro Algo como

data Foo a = Foo { ...stuff here ...}

Suponha que você ache que muitos usos de Footipos numéricos ( Int, Doubleetc) e você precise escrever um código que desembrulhe esses números, adicione ou multiplique e depois os agrupe novamente. Você pode causar um curto-circuito, escrevendo o código de desembrulhar e embrulhar uma vez. Essa função é tradicionalmente chamada de "elevação" porque se parece com isso:

liftFoo2 :: (a -> b -> c) -> Foo a -> Foo b -> Foo c

Em outras palavras, você tem uma função que pega uma função de dois argumentos (como o (+)operador) e a transforma na função equivalente para Foos.

Então agora você pode escrever

addFoo = liftFoo2 (+)

Edit: mais informações

Você pode, é claro liftFoo3, ter ,liftFoo4 e assim por diante. No entanto, isso geralmente não é necessário.

Comece com a observação

liftFoo1 :: (a -> b) -> Foo a -> Foo b

Mas isso é exatamente o mesmo que fmap. Então, ao invés de liftFoo1escrever

instance Functor Foo where
   fmap f foo = ...

Se você realmente quer regularidade completa, pode dizer

liftFoo1 = fmap

Se você pode Footransformar um functor, talvez você possa transformá-lo em um functor aplicativo. De fato, se você pode escrever liftFoo2, a instância do aplicativo fica assim:

import Control.Applicative

instance Applicative Foo where
   pure x = Foo $ ...   -- Wrap 'x' inside a Foo.
   (<*>) = liftFoo2 ($)

O (<*>)operador para Foo tem o tipo

(<*>) :: Foo (a -> b) -> Foo a -> Foo b

Aplica a função agrupada ao valor agrupado. Portanto, se você pode implementar liftFoo2, pode escrever isso em termos disso. Ou você pode implementá-lo diretamente e não se preocupar liftFoo2, porque o Control.Applicativemódulo inclui

liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c

e da mesma forma existem liftAe liftA3. Mas você não as usa com muita frequência porque há outro operador

(<$>) = fmap

Isso permite que você escreva:

result = myFunction <$> arg1 <*> arg2 <*> arg3 <*> arg4

O termo myFunction <$> arg1retorna uma nova função envolvida no Foo. Por sua vez, isso pode ser aplicado ao próximo argumento usando (<*>), e assim por diante. Então agora, em vez de ter uma função de elevação para todas as áreas, você tem apenas uma série de aplicativos.

Paul Johnson
fonte
26
Provavelmente vale lembrar que os elevadores devem respeitar as leis lift id == ide padrões lift (f . g) == (lift f) . (lift g).
Carlos Scheidegger
13
Elevadores são de fato "uma categoria ou algo assim". Carlos acabou de listar as leis do Functor, onde ide .são a seta de identidade e a composição de setas de alguma categoria, respectivamente. Geralmente, quando se fala de Haskell, a categoria em questão é "Hask", cujas setas são funções Haskell (em outras palavras, ide .consulte as funções Haskell que você conhece e ama).
Dan Burton
3
Isso deve ler instance Functor Foo, não instance Foo Functor, certo? Eu me editaria, mas não tenho 100% de certeza.
amalloy
2
Levantar sem um Aplicante é = Functor. Quero dizer que você tem 2 opções: Functor ou Functor Aplicável. O primeiro levanta funções de parâmetro único e as funções de segundo parâmetro múltiplo. Praticamente é isso. Certo? Não é ciência do foguete :) apenas soa como isso. Obrigado pela ótima resposta btw!
jhegedus
2
@ atc: esta é uma aplicação parcial. Veja wiki.haskell.org/Partial_application
Paul Johnson
41

Paul e yairchu são boas explicações.

Gostaria de acrescentar que a função que está sendo levantada pode ter um número arbitrário de argumentos e que eles não precisam ser do mesmo tipo. Por exemplo, você também pode definir um liftFoo1:

liftFoo1 :: (a -> b) -> Foo a -> Foo b

Em geral, o levantamento de funções que recebem 1 argumento é capturado na classe type Functore a operação de levantamento é chamada fmap:

fmap :: Functor f => (a -> b) -> f a -> f b

Observe a semelhança com liftFoo1o tipo de. De fato, se você tiver liftFoo1, poderá criar Foouma instância de Functor:

instance Functor Foo where
  fmap = liftFoo1

Além disso, a generalização do levantamento para um número arbitrário de argumentos é chamada de estilo aplicativo . Não se preocupe em mergulhar nisso até entender o levantamento de funções com um número fixo de argumentos. Mas quando você faz, Learn you a Haskell tem um bom capítulo sobre isso. A Typeclassopedia é outro bom documento que descreve Functor e Applicative (assim como outras classes de tipos; role para baixo até o capítulo direito nesse documento).

Espero que isto ajude!

Martijn
fonte
25

Vamos começar com um exemplo (algum espaço em branco é adicionado para uma apresentação mais clara):

> import Control.Applicative
> replicate 3 'a'
"aaa"
> :t replicate
replicate        ::         Int -> b -> [b]
> :t liftA2
liftA2 :: (Applicative f) => (a -> b -> c) -> (f a -> f b -> f c)
> :t liftA2 replicate
liftA2 replicate :: (Applicative f) =>       f Int -> f b -> f [b]
> (liftA2 replicate) [1,2,3] ['a','b','c']
["a","b","c","aa","bb","cc","aaa","bbb","ccc"]
> ['a','b','c']
"abc"

liftA2transforma uma função de tipos simples em uma função dos mesmos tipos agrupados em umApplicative , como listas IO, etc.

Outro elevador comum é liftdeControl.Monad.Trans . Transforma uma ação monádica de uma mônada em uma ação de uma mônada transformada.

Em geral, o "elevador" eleva uma função / ação para um tipo "empacotado" (para que a função original comece a funcionar "por baixo dos panos").

A melhor maneira de entender isso, mônadas etc., e entender por que são úteis, é provavelmente codificá-lo e usá-lo. Se houver algo que você codificou anteriormente que você suspeite poder se beneficiar disso (isto é, isso tornará o código mais curto etc.), tente e você entenderá facilmente o conceito.

yairchu
fonte
13

Levantar é um conceito que permite transformar uma função em uma função correspondente dentro de outra configuração (geralmente mais geral)

dê uma olhada em http://haskell.org/haskellwiki/Lifting

Nasser Hadjloo
fonte
40
Sim, mas essa página começa "Normalmente começamos com um functor (covariável) ...". Não é exatamente um novato amigável.
Paul Johnson
3
Mas "functor" está vinculado, então o novato pode simplesmente clicar nele para ver o que é um Functor. É certo que a página vinculada não é tão boa. Preciso ter uma conta e consertar isso.
jrockway
10
É um problema que eu já vi em outros sites de programação funcional; cada conceito é explicado em termos de outros conceitos (não familiares) até que o novato faça um círculo completo (e contorne a curva). Deve ter algo a ver com gostar de recursão.
DNA
2
Vote neste link. O elevador faz conexões entre um mundo e outro mundo.
Eccstartup
3
Respostas como essa só são boas quando você já entende o tópico.
precisa saber é o seguinte
-2

De acordo com este tutorial brilhante , um functor é um contêiner (como Maybe<a>,List<a> ou Tree<a>que pode armazenar elementos de outro tipo a). Eu usei a notação genérica Java,, <a>para o tipo de elemento ae pense nos elementos como bagas na árvore Tree<a>. Há uma função fmap, que recebe uma função de conversão de elemento a->be container functor<a>. Aplica-se a->ba todos os elementos do contêiner que o convertem efetivamente functor<b>. Quando apenas o primeiro argumento é fornecido a->b, fmapaguarda o functor<a>. Ou seja, fornecer a->bsozinho transforma essa função no nível do elemento na função functor<a> -> functor<b>que opera sobre contêineres. Isso é chamado de elevaçãoda função. Como o contêiner também é chamado de functor , os Functors, e não as Mônadas, são um pré-requisito para o levantamento. Mônadas são meio "paralelas" ao levantamento. Ambos contam com a noção de Functor e o fazem f<a> -> f<b>. A diferença é que o levantamento usa a->bpara a conversão, enquanto o Monad exige que o usuário defina a -> f<b>.

Val
fonte
5
Dei uma nota para você, porque "um functor é algum contêiner" é uma isca de fogo com sabor de troll. Exemplo: funções de algumas rpara um tipo (vamos usar cpara variedade), são Functors. Eles não "contêm" nenhum c. Nesse caso, fmap é composição de funções, assumindo uma a -> bfunção e r -> aoutra, para fornecer uma nova r -> bfunção. Ainda não há contêineres. Além disso, se eu pudesse, marcaria novamente a frase final.
precisa saber é o seguinte
1
Além disso, fmapé uma função e não "espera" por nada; O "contêiner" sendo um Functor é o ponto principal do levantamento. Além disso, as mônadas são, se é que alguma coisa, uma idéia dupla para o levantamento: uma mônada permite que você use algo que foi levantado algumas vezes positivas, como se tivesse sido levantado apenas uma vez - isso é mais conhecido como achatamento .
BMeph 12/08
1
@BMeph To wait, to expect, to anticipatesão os sinônimos. Ao dizer "função espera", eu quis dizer "função antecipa".
Val
@BMeph Eu diria que, em vez de pensar em uma função como um contra-exemplo à idéia de que os functores são contêineres, você deve pensar na instância sane functor da função como um contra-exemplo à idéia de que as funções não são contêineres. Uma função é um mapeamento de um domínio para um codomain, sendo o domínio o produto cruzado de todos os parâmetros, sendo o codomain o tipo de saída da função. Da mesma forma, uma lista é um mapeamento do Naturals para o tipo interno da lista (domínio -> codomain). Eles se tornam ainda mais semelhantes se você memorizar a função ou não manter a lista.
ponto
O @BMeph, uma das únicas razões pelas quais as listas são consideradas mais como um contêiner, é que em muitos idiomas elas podem ser mutadas, enquanto as funções tradicionalmente não. Mas em Haskell, mesmo isso não é uma afirmação justa, pois nenhum dos dois pode ser mutado, e ambos podem ser mutados por cópia: b = 5 : ae f 0 = 55 f n = g nambos envolvem pseudo-mutação do "contêiner". Além disso, o fato de que as listas são tipicamente armazenadas completamente na memória, enquanto as funções são tipicamente armazenadas como um cálculo. Mas listas de memorização / monórficas que não são armazenadas entre as chamadas quebram essa porcaria.
ponto