Por que não há uma classe para funções?

17

Em um problema de aprendizado com o qual estou brincando, percebi que precisava de uma classe para funções com operações para aplicação, composição etc. Razões ...

  1. Pode ser conveniente tratar uma representação de uma função como se fosse a própria função, de modo que a aplicação implícita da função use um intérprete e a composição de funções deriva uma nova descrição.

  2. Depois de ter uma classe para funções, você pode derivar classes para tipos especiais de funções - no meu caso, eu quero funções invertíveis.

Por exemplo, funções que aplicam deslocamentos de número inteiro podem ser representadas por um ADT contendo um número inteiro. Aplicar essas funções significa apenas adicionar o número inteiro. A composição é implementada adicionando os números inteiros quebrados. A função inversa tem o número inteiro negado. A função de identidade quebra zero. A função constante não pode ser fornecida porque não há representação adequada para ela.

É claro que não é necessário escrever as coisas como se os valores fossem funções genuínas de Haskell, mas depois que tive a ideia, pensei que uma biblioteca como essa já deveria existir e talvez até usar as grafias padrão. Mas não consigo encontrar essa classe na biblioteca Haskell.

Encontrei o módulo Data.Function , mas não há classe - apenas algumas funções comuns que também estão disponíveis no Prelude.

Então - por que não há uma classe para funções? É "apenas porque não existe" ou "porque não é tão útil quanto você pensa"? Ou talvez haja um problema fundamental com a ideia?

O maior problema possível que eu pensei até agora é que a aplicação de funções em funções reais provavelmente teria que ser especificada pelo compilador para evitar um problema de loop - para aplicar esta função, preciso aplicar a função de aplicação de funções, e para fazer isso eu preciso chamar a função application application, e para fazer isso ...

Mais pistas

Exemplo de código para mostrar o que estou buscando ...

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GADTs #-}

--  In my first version, Doable only had the one argument f. This version
--  seemed to be needed to support the UndoableOffset type.
--
--  It seems to work, but it also seems strange. In particular,
--  the composition function - a and b are in the class, but c isn't,
--  yet there's nothing special about c compared with a and b.
class Doable f a b where
  fwdApply :: f a b -> a -> b
  compDoable :: f b c -> f a b -> f a c

--  In the first version, I only needed a constraint for
--  Doable f a b, but either version makes sense.
class (Doable f a b, Doable f b a) => Undoable f a b where
  bwd      :: f a b -> f b a

  bwdApply :: f a b -> b -> a
  bwdApply f b = fwdApply (bwd f) b

--  Original ADT - just making sure I could wrap a pair of functions
--  and there were no really daft mistakes.
data UndoableFn a b = UFN { getFwd :: a -> b, getBwd :: b -> a }

instance Doable UndoableFn a b where
  fwdApply = getFwd
  compDoable f g = UFN ((getFwd f) . (getFwd g)) ((getBwd g) . (getBwd f))

instance Undoable UndoableFn a b where
  bwd f    = UFN (getBwd f) (getFwd f)
  bwdApply = getBwd

--  Making this one work led to all the extensions. This representation
--  can only represent certain functions. I seem to need the typeclass
--  arguments, but also to need to restrict which cases can happen, hence
--  the GADT. A GADT with only one constructor still seems odd. Perhaps
--  surprisingly, this type isn't just a toy (except that the whole thing's
--  a toy really) - it's one real case I need for the exercise. Still a
--  simple special case though.
data UndoableOffset a b where
  UOFF :: Int -> UndoableOffset Int Int

instance Doable UndoableOffset Int Int where
  fwdApply (UOFF x) y = y+x
  compDoable (UOFF x) (UOFF y) = UOFF (x+y)

instance Undoable UndoableOffset Int Int where
  bwdApply (UOFF x) y = y-x
  bwd (UOFF x) = UOFF (-x)

--  Some value-constructing functions
--  (-x) isn't shorthand for subtraction - whoops.
undoableAdd :: Int -> UndoableFn Int Int
undoableAdd x = UFN (+x) (\y -> y-x)

undoableMul :: Int -> UndoableFn Int Int
undoableMul x = UFN (*x) (`div` x)

--  With UndoableFn, it's possible to define an invertible function
--  that isn't invertible - to break the laws. To prevent that, need
--  the UFN constructor to be private (and all public ops to preserve
--  the laws). undoableMul is already not always invertible.
validate :: Undoable f a b => Eq a => f a b -> a -> Bool
validate f x = (bwdApply f (fwdApply f x)) == x

--  Validating a multiply-by-zero invertible function shows the flaw
--  in the validate-function plan. Must try harder.
main = do putStrLn . show $ validate (undoableAdd 3) 5
          putStrLn . show $ validate (undoableMul 3) 5
          --putStrLn . show $ validate (undoableMul 0) 5
          fb1 <- return $ UOFF 5
          fb2 <- return $ UOFF 7
          fb3 <- return $ compDoable fb1 fb2
          putStrLn $ "fwdApply fb1  3 = " ++ (show $ fwdApply fb1  3)
          putStrLn $ "bwdApply fb1  8 = " ++ (show $ bwdApply fb1  8)
          putStrLn $ "fwdApply fb3  2 = " ++ (show $ fwdApply fb3  2)
          putStrLn $ "bwdApply fb3 14 = " ++ (show $ bwdApply fb3 14)

O aplicativo envolve um tipo de unificação em que os valores unificados não são iguais, mas estão relacionados por meio de funções invertíveis - lógica no estilo Prolog, mas com a = f(b)restrições em vez de a = b. A maior parte da composição resultará da otimização de uma estrutura de busca de união. A necessidade de inversos deve ser óbvia.

Se nenhum item em um conjunto unificado tiver um valor exato, um item específico poderá ser quantificado apenas em relação a outro item nesse conjunto unificado. É por isso que não quero usar funções "reais" - calculando esses valores relativos. Eu poderia abandonar todo o aspecto da função e apenas ter quantidades absolutas e relativas - provavelmente só preciso de números / vetores e (+)- mas meu astronauta de arquitetura interna quer a diversão dele.

A única maneira de separar os links novamente é através do backtracking, e tudo é puro - a busca por união será feita usando as chaves em IntMap"ponteiros". Eu tenho um trabalho simples de encontrar união, mas como ainda não adicionei as funções invertíveis, não faz sentido listá-lo aqui.

Razões pelas quais não posso usar o aplicativo, mônada, seta etc.

As principais operações que eu preciso que a classe de abstração da função forneça são aplicação e composição. Isso parece familiar - por exemplo Applicative (<*>), Monad (>>=)e Arrow (>>>)são todas funções de composição. No entanto, os tipos que implementam a abstração da função no meu caso conterão alguma estrutura de dados que representa uma função, mas que não é (e não pode conter) uma função e que pode representar apenas um conjunto limitado de funções.

Como mencionei na explicação do código, às vezes só posso quantificar um item em relação a outro porque nenhum item em um cluster "unificado" tem um valor exato. Eu quero ser capaz de derivar uma representação dessa função, que em geral será a composição de várias funções fornecidas (subindo para um ancestral comum na árvore união / localização) e de várias funções inversas (voltando para a outra item).

Caso simples - onde as "funções" originais são limitadas às "funções" de deslocamento inteiro, quero o resultado composto como uma "função" de deslocamento inteiro - adicione as compensações do componente. Essa é uma parte importante do motivo pelo qual a função de composição precisa estar na classe e também na função de aplicativo.

Isso significa que não posso fornecer as operações pure, returnou arrpara os meus tipos, então não posso usar Applicative, Monadou Arrow.

Não é uma falha desses tipos - é uma incompatibilidade de abstrações. A abstração que eu quero é de uma simples função pura. Não há efeito colateral, por exemplo, e não é necessário criar uma notação conveniente para sequenciar e compor as funções que não sejam equivalentes ao padrão (.) Que se aplica a todas as funções.

Eu poderia instância Category. Estou confiante de que todas as minhas coisas funcionais serão capazes de fornecer uma identidade, embora eu provavelmente não precise dela. Mas como Categoryele não suporta aplicativos, ainda assim eu precisaria de uma classe derivada para adicionar essa operação.

Steve314
fonte
2
Me chame de maluca, mas quando penso em uma classe de tipo como você está descrevendo para aplicar e compor etc, penso em functores aplicativos, quais são as funções. Talvez seja dessa classe de tipo que você está pensando?
Jimmy Hoffa
1
Eu não acho que Applicativeesteja certo - ele exige que os valores sejam agrupados, assim como as funções, enquanto eu só quero agrupar as funções, e as funções agrupadas são realmente funções, enquanto minhas funções agrupadas normalmente não serão (em o caso mais geral, são ASTs que descrevem funções). Onde <*>tem tipo f (a -> b) -> f a -> f b, quero um operador de aplicativo com o tipo g a b -> a -> bonde ae bespecifique o domínio e o código da função agrupada, mas o que está dentro do wrapper não é (necessariamente) uma função real. No Arrows - possivelmente, vou dar uma olhada.
Steve314
3
se você quiser inverso, isso não implicaria um grupo?
jk.
1
@jk. excelente ponto, perceber que há muitas coisas para ler sobre inversões de funções que podem levar o OP a encontrar o que está procurando. Aqui estão algumas leituras interessantes sobre o assunto. Mas uma função inversa do google for haskell fornece bastante conteúdo curioso de leitura. Talvez ele só quer Data.Group
Jimmy Hoffa
2
@ Steve314 Pensei que funções com composição são uma categoria monoidal. Eles são monóides se o domínio e o codomain são sempre os mesmos.
Tim Seguine 24/10

Respostas:

14

Bem, não conheço nenhuma ideia assada que se comercialize como representando coisas "funcionais e". Mas há vários que se aproximam

Categorias

Se você tem um conceito de função simples que possui identidades e composição, então você tem uma categoria.

class Category c where
  id :: c a a
  (.) :: c b c -> c a b -> c a c

A desvantagem é que você não pode criar uma instância de categoria legal com um conjunto de objetos (a , b, e c). Você pode criar uma classe de categoria personalizada, suponho.

Setas; flechas

Se suas funções tiverem noção de produtos e puderem injetar funções arbitrárias, as setas são para você

 class Arrow a where
   arr :: (b -> c) -> a b c
   first :: a b c -> a (b, d) (c, d)
   second :: a b c -> a (d, b) (d, c)

ArrowApply tem uma noção de aplicação que parece importante para o que você deseja.

Requerentes

Os candidatos têm sua noção de aplicação, eu os usei em um AST para representar aplicativo de função.

class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f b -> f c

Existem muitas outras idéias. Mas um tema comum é criar alguma estrutura de dados representando sua função e passá-la para uma função de interpretação.

Isso também funciona com quantas mônadas gratuitas. Eu sugiro cutucar neles se você estiver se sentindo corajoso, eles são uma ferramenta poderosa para as coisas que você está sugerindo e, essencialmente, permitem que você construa uma estrutura de dados usando a donotação e depois a recolha em uma computação de efeito colateral com funções diferentes . Mas o mais interessante é que essas funções funcionam apenas na estrutura de dados e não estão realmente conscientes de como você fez tudo isso. Isso é o que eu sugeriria para o seu exemplo de intérprete.

Daniel Gratzer
fonte
Categoria parece não ter aplicação - ($). As setas parecem um enorme exagero à primeira vista, mas ainda ArrowApplyparecem promissoras - desde que eu não precise fornecer nada que não possa, pode estar tudo bem. +1 no momento, com mais verificação a fazer.
Steve314
3
@ Steve314 Categorias de fazer aplicação falta, mas mônadas não têm uma maneira universal para executá-los, não significa que eles não são úteis
Daniel Gratzer
Há um motivo comum para não poder usar Applicativeou Arrow(ou Monad) - não consigo agrupar uma função normal (em geral) porque os valores do meu tipo representam uma função, mas são representados por dados e não suportam funções arbitrárias, se havia uma maneira de traduzir. Isso significa que não posso fornecer pure, arrou returnpor exemplo. BTW - essas classes são úteis, mas não posso usá-las para esse fim específico. Arrownão é um "exagero maciço" - foi uma falsa impressão desde a última vez que tentei ler o jornal, quando não estava pronto para entendê-lo.
Steve314
@ Steve314 A idéia de fornecer uma interface mônada para construir dados é o que monads livres são usados para, vê-los
Daniel Gratzer
Eu assisti o vídeo do Haskell Exchange 2013 - Andres Löh definitivamente explica bem, embora eu provavelmente ainda precise assisti-lo novamente, brincar com a técnica etc. Mas não tenho certeza de que é necessário aqui. Meu objetivo é ter a abstração de uma função usando uma representação que não é uma função (mas que possui uma função de intérprete). Não preciso de uma abstração de efeitos colaterais e não preciso de uma notação limpa para operações de seqüenciamento. Uma vez que essa abstração de função esteja em uso, aplicativos e composições serão feitos um de cada vez dentro de um algoritmo em outra biblioteca.
Steve314
2

Como você ressalta, o principal problema com o uso do Applicative aqui é que não há uma definição sensata para pure. Por isso, Applyfoi inventado. Pelo menos, esse é o meu entendimento.

Infelizmente, não tenho exemplos disponíveis de instâncias Applyque também não são Applicative. Alega-se que isso é verdade IntMap, mas não tenho idéia do porquê. Da mesma forma, não sei se o seu exemplo - deslocamento inteiro - admite uma Applyinstância.

user185657
fonte
este lê mais como um comentário, consulte Como responder
mosquito
Desculpe. Esta é mais ou menos a minha primeira resposta de sempre.
user185657
Como você sugere que eu melhore a resposta?
user185657
considere a edição para ajudar os leitores a ver como sua resposta aborda a pergunta: "por que não existe uma classe para funções? É" apenas porque não existe "ou" porque não é tão útil quanto você pensa "? Ou talvez há um problema fundamental com a ideia? "
Gnat
1
Eu espero que isso seja melhor #
187657
1

Além do referido Category, ArroweApplicative :

Eu também descobri Data.Lambdapor Conal Elliott:

Algumas classes funcionais, com construção semelhante a lambda

Parece interessante, é claro, mas difícil de entender sem exemplos ...

Exemplos

Exemplos podem ser encontrados na página wiki sobre valores tangíveis (TV) que parecem ser uma das coisas que causaram a criação da TypeComposebiblioteca; consulte Entradas e saídas com valor de função .

A idéia da biblioteca de TV é exibir valores Haskell (incluindo funções) de maneira tangível.

Para seguir a regra StackOverflow sobre não postar vazios, copio alguns bits abaixo, que devem dar a idéia do seguinte:

O primeiro exemplo diz:

apples, bananas :: CInput Int
apples  = iTitle "apples"  defaultIn
bananas = iTitle "bananas" defaultIn

shoppingO :: COutput (Int -> Int -> Int)
shoppingO = oTitle "shopping list" $
            oLambda apples (oLambda bananas total)

shopping :: CTV (Int -> Int -> Int)
shopping = tv shoppingO (+)

que fornece quando executado como runIO shopping(veja mais comentários, GUIs e mais exemplos):

shopping list: apples: 8
bananas: 5
total: 13
imz - Ivan Zakharyaschev
fonte
como isso resolve a questão? veja Como responder
gnat
@gnat Eu pensei que as definições em Data.Lambdadar classes para coisas como funções (que foi solicitado) ... eu não tinha certeza de como essas coisas devem ser usadas. Eu explorei isso um pouco. Provavelmente, eles não fornecem uma abstração para a aplicação de funções.
imz - Ivan Zakharyaschev