Esiste un idioma Haskell per provare diverse funzioni e fermarsi non appena ce n'è riuscito?

8

In Haskell, posso usare il tipo a -> Maybe b per modellare una funzione che restituisce un valore di tipo b , o restituisce nulla (non riesce).

Se ho tipi a1, ..., a(n+1) e funzioni f1, ..., fn , con fi :: ai -> Maybe a(i+1) per tutto i , 1 <= i <= n , posso concatenare le funzioni utilizzando l'operatore >>= di Maybe monad e scrivi :

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

L'operatore >>= garantisce che ciascuna funzione venga applicata finché il suo predecessore ha restituito un valore significativo. Non appena una funzione nella catena fallisce, l'intera catena fallisce (restituisce Nothing ) e non vengono valutate ulteriori funzioni nella catena.

Ho uno schema un po 'simile nel quale voglio provare diverse funzioni sullo stesso input, e tornare non appena una funzione riesce . Se tutte le funzioni falliscono (return Nothing ), l'intera computazione dovrebbe fallire. Più precisamente, ho funzioni f1, ..., fn :: a -> Maybe b e definisco la funzione

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

In un certo senso questo è duale al Maybe monad in quanto un calcolo si arresta al primo successo invece che al primo errore.

Ovviamente, posso usare la funzione che ho scritto sopra, ma mi chiedevo se c'è un modo migliore, consolidato e idiomatico di esprimere questo modello in Haskell.

    
posta Giorgio 27.07.2015 - 19:01
fonte

4 risposte

8

Dato un insieme chiuso (numero fisso di elementi) S con elementi {a..z} e un operatore binario * :

Esiste un singolo elemento di identità i tale che:

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

L'operatore è associativo in modo tale che:

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

Hai un monoid.

Ora dato un qualsiasi monoide puoi definire una funzione binaria f come:

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

Ciò significa che per l'esempio di Maybe monoid ( Nothing è l'elemento identità indicato sopra come 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

Sorprendentemente, non riesco a trovare questa funzione precisa nelle librerie predefinite, probabilmente a causa della mia inesperienza. Se qualcun altro può offrirlo volontariamente, lo apprezzerei sinceramente.

Ecco l'implementazione che ho dedotto dall'esempio precedente:

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

Esempio:

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

Quindi se si desidera utilizzare un elenco di funzioni come input ...

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

Esempio:

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
λ> 
    
risposta data 27.07.2015 - 19:33
fonte
5
import Data.Monoid

tryFunctions :: a -> [a -> Maybe b] -> Maybe b
tryFunctions x = getFirst . mconcat . map (First . ($ x))
    
risposta data 27.07.2015 - 19:34
fonte
4

Questo suona molto simile a sostituendo l'errore con un elenco di successi

Parli di Maybe a piuttosto che [a] , ma in realtà sono molto simili: possiamo pensare a Maybe a come [a] , eccetto che può contenere al massimo un elemento (es. . Nothing ~= [] e Just x ~= [x] ).

Nel caso delle liste, il tuo tryFunctions sarebbe molto semplice: applica tutte le funzioni all'argomento dato e concatena tutti i risultati insieme. concatMap lo farà bene:

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

In questo modo, possiamo vedere che l'operatore <|> per Maybe agisce come una concatenazione per "elenchi con al massimo un elemento".

    
risposta data 29.07.2015 - 18:35
fonte
1

Nello spirito di Conal, suddividilo in operazioni più semplici e più semplici.

In questo caso, asum da Data.Foldable fa la parte principale.

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

In alternativa, a la risposta di Jimmy Hoffa puoi usare l'istanza Monoid per (->) ma poi hai bisogno di un'istanza Monoid per Maybe e quella standard non fa quello che vuoi. Vuoi First da Data.Monoid .

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

(oppure mconcat per una versione più vecchia e più specializzata di fold .)

    
risposta data 17.01.2016 - 08:05
fonte