Existe um idioma Haskell para tentar várias funções e parar assim que alguém for bem-sucedido?

9

No Haskell, posso usar o tipo a -> Maybe bpara modelar uma função que retorna um valor do tipo bou não retorna nada (falha).

Se eu tiver tipos a1, ..., a(n+1)e funções f1, ..., fn, com fi :: ai -> Maybe a(i+1)para todos i, 1 <= i <= nposso encadear as funções usando o >>=operador da Maybemônada e escrever:

f1 x >>= f2 >>= f3 >>=... >>= fn

O >>=operador garante que cada função seja aplicada desde que seu predecessor retorne um valor significativo. Assim que uma função na cadeia falha, a cadeia inteira falha (retorna Nothing) e outras funções na cadeia não são avaliadas.

Eu tenho um padrão um pouco semelhante no qual desejo tentar várias funções na mesma entrada e retornar assim que uma função for bem-sucedida . Se todas as funções falharem (retornar Nothing), todo o cálculo falhará. Mais precisamente, tenho funções f1, ..., fn :: a -> Maybe be defino a função

tryFunctions :: [a -> Maybe b] -> a -> Maybe b
tryFunctions []       _ = Nothing
tryFunctions (f : fs) x = case f x of
                            Nothing    -> tryFunctions fs x
                            r@(Just _) -> r

Em certo sentido, isso é duplo para a Maybemônada, pois um cálculo para no primeiro sucesso, e não na primeira falha.

Obviamente, posso usar a função que escrevi acima, mas fiquei pensando se há uma maneira melhor, bem estabelecida e idiomática de expressar esse padrão em Haskell.

Giorgio
fonte
Não Haskell, mas em C #, você vai ocasionalmente ver o operador nulo coalesce (??) usado assim:return f1 ?? f2 ?? f3 ?? DefaultValue;
Telastyn
4
Sim, é verdade - isso é Alternativeque é o operador símbolo infix <|>e é definido em termos de uma Monoid
Jimmy Hoffa

Respostas:

8

Dado um conjunto fechado (número fixo de elementos) Scom elementos {a..z}e um operador binário *:

Existe um único elemento de identidade ique:

forall x in S: i * x = x = x * i

O operador é associativo de modo que:

forall a, b, c in S: a * (b * c) = (a * b) * c

Você tem um monóide.

Agora, dado qualquer monóide, você pode definir uma função binária fcomo:

f(i, x) = x
f(x, _) = x

O que isso significa é que, para o exemplo do Maybemonóide ( Nothingé o elemento de identidade indicado acima como i):

f(Nothing, Just 5) = Just 5
f(Just 5, Nothing) = Just 5
f(Just 5, Just 10) = Just 5
f(Nothing, f(Nothing, Just 5)) = Just 5
f(Nothing, f(Just 5, Nothing)) = Just 5

Surpreendentemente, não consigo encontrar essa função precisa nas bibliotecas padrão, o que provavelmente se deve à minha própria inexperiência. Se mais alguém puder oferecer isso voluntariamente, eu agradeceria sinceramente.

Aqui está a implementação que deduzi de imediato do exemplo acima:

(<||>) :: (Monoid a, Eq a) => a -> a -> a
x <||> y
     | x == mempty = y
     | True = x

Exemplo:

λ> [] <||> [1,2] <||> [3,4]
[1,2]
λ> Just "foo" <||> Nothing <||> Just "bar"
Just "foo"
λ> Nothing <||> Just "foo" <||> Just "bar"
Just "foo"
λ> 

Então, se você quiser usar uma lista de funções como entrada ...

tryFunctions x funcs = foldl1 (<||>) $ map ($ x) funcs

exemplo:

instance Monoid Bool where
         mempty = False
         mconcat = or
         mappend = (||)

λ> tryFunctions 8 [odd, even]
True
λ> tryFunctions 8 [odd, odd]
False
λ> tryFunctions 8 [odd, odd, even]
True
λ> 
Jimmy Hoffa
fonte
Não entendo por que <|>trata a identidade de um monóide de uma maneira especial. Não se pode escolher um elemento arbitrário de um conjunto arbitrário para desempenhar esse papel especial? Por que o conjunto precisa ser um monóide e o elemento especial cria <|>sua identidade?
Giorgio
1
@Giorgio talvez seja por isso <|>que não confie no monóide e eu tenho tudo isso misturado? Baseia-se na Alternativeclasse. Para ter certeza - eu estou olhando para a minha própria resposta e perceber que não é muito bem como [1,2] <|> [3]dá o inesperado [1,2,3]então tudo sobre como utilizar a classe tipo monoid para identificar uma identidade é certo - e a outra chave é associatividade é necessário para obter o comportamento esperado , talvez Alternativenão lhe dá o comportamento que eu pensava fora da mão ...
Jimmy Hoffa
@JimmyHoffa isso vai depender da classe Talvez <|> seja diferente da Lista <|> não?
jk.
@Giorgio veja meus últimos 2 exemplos de fpara ver por que associatividade é uma necessidade.
Jimmy Hoffa
ou seja, monóide para listas é a lista vazia e concat
jk.
5
import Data.Monoid

tryFunctions :: a -> [a -> Maybe b] -> Maybe b
tryFunctions x = getFirst . mconcat . map (First . ($ x))
Thomas Eding
fonte
Este é limpo e simples, mas fixo para Maybe... Minha solução é limitada por Eq, de alguma forma eu sinto que nós dois estamos perdendo algo disponível por meio de Monoidgeral ...
Jimmy Hoffa
@ JimmyHoffa: Você quer generalizar esta solução para que ela possa funcionar com outros tipos de dados, por exemplo either?
Giorgio
@Giorgio exatamente. Desejo que a única restrição seja Monoida de que qualquer coisa com um elemento de identidade possa ter um conjunto de 2 funções (acho que esse é um tipo de campo binário), onde uma das funções escolhe a identidade sobre todas as outras, e a outra função sempre escolhe o elemento não identitário. Eu simplesmente não sei como fazer isso sem Eqsaber qual é o valor identityou não .. obviamente, em monoides aditivos ou multiplicativos, você obtém a função ladder por padrão (sempre escolha elementos não identitários usando a função binária de monoides)
Jimmy Hoffa
foldMappode ser usado no lugar demconcat . map
4castle
4

Isso parece muito com a substituição de falhas por uma lista de sucessos

Você está falando mais Maybe ado que [a], mas na verdade eles são muito parecidos: podemos pensar Maybe acomo sendo [a], exceto que pode conter no máximo um elemento (ie. Nothing ~= []E Just x ~= [x]).

No caso de listas, você tryFunctionsseria muito simples: aplique todas as funções ao argumento fornecido e concatene todos os resultados juntos. concatMapfará isso muito bem:

tryFunctions :: [a -> [b]] -> a -> [b]
tryFunctions fs x = concatMap ($ x) fs

Dessa maneira, podemos ver que o <|>operador Maybeatua como concatenação para 'listas com no máximo um elemento'.

Warbo
fonte
1

No espírito de Conal, divida-o em operações menores e mais simples.

Neste caso, asumde Data.Foldablefaz a parte principal.

tryFunction fs x = asum (map ($ x) fs)

Como alternativa, na resposta de Jimmy Hoffa, você pode usar a Monoidinstância, (->)mas precisa de uma Monoidinstância Maybee a padrão não faz o que você deseja. Você quer Firstde Data.Monoid.

tryFunction = fmap getFirst . fold . map (fmap First)

(Ou mconcatpara uma versão mais antiga e especializada de fold.)

Derek Elkins deixou o SE
fonte
Soluções interessantes (+1). Acho o primeiro mais intuitivo.
Giorgio