En programació funcional una Fletxa s'utilitza en el llenguatge de programació Haskell i és un TAD que modela la precedència temporal de computacions basant-se en l'encadenament de funcions amb efectes col·laterals.
Una fletxa, concepte desenvolupat per John Hughes, és una generalització d'una funció (amb un sol tipus d'entrada i un de sortida) on el resultat pot dependre d'efectes col·laterals o bé ser independent de l'entrada.
Generalitza el concepte de Mònada, d'encadenament d'accions amb efecte col·lateral. Les mònades en són un cas particular anomenat ArrowApply. A més incorpora més informació de tipus que no el del resultat a les mònades, facilitant la composició i permetent evitar fuites d'ús de memòria.
Té aplicació en programació reactiva funcional (tractament de senyals i altres fluxos d'informació).
L'abstracció Fletxa va ser descrita per primer cop per John Hughes al seu document "Generalising Monads to Arrows"Generalising Monads to ArrowsUnderstanding Arrows com a solució als problemes d'un analitzador sintàctic. Einar Karttunen en va escriure una implementació anomenada PArrows que aproxima les prestacions de l'actual biblioteca d'anàlisi sintàctic de Haskell anomenada Parsec.
Aquí presentem un aspecte pràctic al Haskell. Per una versió amb fonaments teòrics consulteu la versió anglesa o completeu-ne, qui en sàpiga més, l'exposició.
Generalització de la Mònada - Fletxes de Kleisli Seguint el document i partint de l'encadenament de resultats de les computacions mònada
class Monad m where return :: a -> m a -- generador de la mònada (>>=) :: m a -> (a -> m b) -> m b -- encadenament amb una funció del resultat de la precedent ...
-- es poden definir computacions encadenades Fletxa, a partir de les operacions class Arrow efecte where
arr :: (b -> c) -> efecte b c -- generador elevant una funció a la categoria d'efecte Fletxa
(>>>) :: efecte b c -> efecte c d -> efecte b d -- combinació / encadenament d'efectes Fletxa
-- prenem les computacions amb encadenament de la mònada f :: (a -> m b)
-- i en definim un tipus newtype Kleisli m a b = Kleisli (a -> m b)
instance (Monad m) => Arrow (Kleisli m) where
-- genera una fletxa elevant una funció -- arr :: (b -> c) -> (Kelisli m) b c
arr f = Kleisli (\ x -> return (f x))
-- combinació de fletxes (Kleisli f) >>> (Kleisli g) = Kleisli (\ x -> (f x) >>= g) -- f,g :: (a -> m b)
Això mostra que les fletxes generalitzen les mònades. Per cada tipus mònada hi ha un tipus fletxa corresponent. (Del doc. "Generalizing Monads to Arrows".
Fletxes i Parells A les mònades les operacions return i (>>=) són suficients per efectuar càlculs com ara la suma de resultats de computacions. sumaM :: Monad efecte => efecte Int -> efecte Int -> efecte Int sumaM m_x m_y = m_x >>= (\x -> m_y >>= (\y -> return (x + y))) -- els parèntesis hi són per ressaltar
A les fletxes, arr i (>>>) no són suficients per efectuar el mateix càlcul. Cal trobar una manera de combinar el resultat de la primera computació amb el resultat de la segona per tenir-los a punt per al càlcul. Cal introduir un altre combinador (first: converteix una fletxa en una altra sobre parells, actuant sobre el primer element).
classe Arrow efecte where arr :: (b -> c) -> efecte b c -- eleva una funció a la categoria de l'efecte (>>>) :: efecte b c -> efecte c d -> efecte b d -- encadenament d'efectes Fletxa first :: efecte b c -> efecte (b, d) (c, d) -- converteix un efecte Fletxa en un sobre parells, actuant sobre el primer element.
instance (Monad m) => Arrow (Kleisli m) where -- modifica el primer del parell amb el resultat de la computació ''f x'', on "f :: b -> m c" first (Kleisli f) = Kleisli (\(x, y) -> f x >>= (\z -> return (z, y))) El nou operador first converteix una fletxa de b a c en una fletxa sobre un parell, transformant-ne el primer element. -- ''second'' transforma el segon del parell; es defineix en termes de ''first'' second f = arr swap >>> first f >>> arr swap
-- (***) combina dues fletxes en una fletxa de parells, aplicant-les als diferents elements (***) :: Arrow efecte => efecte b c -> efecte d e -> efecte (b, d) (c, e) f *** g = first f >>> second g
-- (&&&) obté un parell de l'aplicació de dues fletxes sobre una mateixa entrada (&&&) :: Arrow efecte => efecte b c -> efecte b d -> efecte b (c, d) f &&& g = arr (\b -> (b, b)) >>> (f *** g)
Amb aquestes definicions la suma de resultats de computacions fletxa queda completament definida. sumaA :: Arrow efecte => efecte b Int -> efecte b Int -> efecte b Int sumaA f g = (f &&& g) >>> arr (\(u, v) -> u + v)
La definició a GHC A banda de la descripció precedent que correspon a un document de l'any 1998, l'actual definició a GHC de la classe ArrowControl.Arrow deriva de la classe CategoryControl.Category que generalitza les funcions, amb les operacions identitat i composició.
La definició actual de (>>>), seqüenciació temporal, és igual a la composició de funcions (classe Category).
La classe Arrow (derivada de Category) requereix només la definició mínima de arr i first, incorporant a més, dins la classe, les operacions second, (***) i (&&&) corresponent a les descrites més amunt del document de John Hughes de 1998.
combinació de Fletxes i sintaxi específica Podem combinar les fletxes aparellant entrades i sortides en tipus producte Tupla2 (classe Arrow) (***): combina aparellant entrades i sortides (&&&): mateix tipus d'entrada, aparella sortides
en tipus suma Either (classe ArrowChoice) (+++): suma de tipus a l'entrada i a la sortida (|||): suma de tipus a l'entrada, mateix tipus de sortida
La clàusula "proc" permet definir un filtre partint d'altres filtres. Exemple:Sintaxi específica de les Arrow
-- combinació de dos filtres ''fletxa'' f i g resultant un altre filtre
{-# LANGUAGE Arrows #-} import Control.Arrow
addA :: Arrow efecte => efecte b Int -> efecte b Int -> efecte b Int
-- x (entrada del filtre) és del tipus 'b', segon element de la terna de la Fletxa resultant.
addA f g = proc x -> do y <- f -< x -- executa l'acció/efecte d'aplicar 'f' a 'x' obtenint el resultat 'y' z <- g -< x -- executa l'acció/efecte d'aplicar 'g' a 'x' obtenint el resultat 'z' returnA -< y + z -- aplica (y + z) al filtre de sortida ('returnA'), com a resultat del bloc 'proc'
Equivalent de la fletxa addA expressada en operacions canòniques del tipusLa fletxa addA addA f g = (f &&& g) >>> arr (\ (y, z) -> y + z)
alternatives ArrowChoice La classe ArrowChoice ofereix un tractament d'entrades de tipus Either a b permetent tractaments alternatius segons siguin Left o Right.
Millorant els comentaris del mòdul Control.Arrow: class Arrow efecte => ArrowChoice efecte where -- ''left f'' passa el contingut de les entrades etiquetades Left per f -- re-etiquetant el resultat, mentre que les Right passen inalterades left :: efecte b c -> efecte (Either b d) (Either c d)
-- ''right f'' passa el contingut de les entrades etiquetades Right per f -- re-etiquetant el resultat, mentre que les Left passen inalterades right :: efecte b c -> efecte (Either d b) (Either d c)
-- ''f ||| g'' passa les Left per f i les Right per g (|||) :: efecte b d -> efecte c d -> efecte (Either b c) d
-- ''f +++ g'' passa les Left per f i les Right per g --, re-etiquetant el resultat amb Left o Right. (+++) :: efecte b c -> efecte b' c' -> efecte (Either b b') (Either c c')
-- és el cas que
f +++ g ≡ left f >>> right g
left f ≡ f +++ arr id
right f ≡ arr id +++ f
Exemples Ent./Sort. amb fletxes de Kleisli (mònades elevades a fletxes) Partint de la definició esmentada més amunt, lectura d'any, mes i dia amb comprovació. {-# LANGUAGE Arrows #-}
import Control.Arrow import System.IO (hFlush, stdout) import Data.List (intercalate) import Data.Char (toLower) import Data.Bits ((.&.)) -- bits And
-- llegeix un valor enter llegeixDia, llegeixAny :: () -> IO Int llegeixDia () = putStrLn "Entreu dia (dd):" >> hFlush stdout >> getLine >>= (return. read) llegeixAny () = putStrLn "Entreu any (aaaa):" >> hFlush stdout >> getLine >>= (return. read)
-- retorna mes en minúscules, limitat a 3 lletres llegeixMes () = putStrLn "Entreu mes (mmm):" >> hFlush stdout >> getLine >>= (return. (map toLower). take 3) -- :: IO String
fletxaLlegirDia = Kleisli {runKleisli = llegeixDia} -- inicialització per camps, :: Kleisli IO () Int fletxaLlegirMes = Kleisli llegeixMes -- inicialització posicional, :: Kleisli IO () String fletxaLlegirAny = Kleisli llegeixAny -- :: Kleisli IO () Int
-- fletxaLlegeixIComprovaDia :: Kleisli IO (Int, String) (Either IOError (Int, String, Int)) fletxaLlegeixIComprovaDia = proc (iAny, strMes) -> do
iDia <- fletxaLlegirDia -< ()
let ésAnyDeTraspàs = let (iSegle, iAnyDelSegle) = iAny `divMod` 100 in if iAnyDelSegle == 0 -- comprova bits menors then iSegle .&. 0x03 == 0 -- segle és múltiple de 4 else iAnyDelSegle .&. 0x03 == 0 -- any del segle és múltiple de 4 i (/= 0)
let ésDiaIŀlegal = (iDia <= 0) || (strMes == "feb" && ((ésAnyDeTraspàs && iDia > 29) || (not ésAnyDeTraspàs && iDia > 28)) ) || ((strMes `elem` [ "abr", "jun", "set", "nov"]) && (iDia > 30)) || iDia > 31
if ésDiaIŀlegal then returnA -< Left $ userError "dia iŀlegal" else returnA -< Right (iAny, strMes, iDia)
fletxaComposaData = proc (iAny, strMes, iDia) -> do returnA -< intercalate "/" [show iDia, strMes, show iAny]
main = do -- ''f &&& g'' aplica la mateixa entrada a ''f'' i a ''g'', i n'aparella els resultats let fletxa = (fletxaLlegirAny &&& fletxaLlegirMes) >>> fletxaLlegeixIComprovaDia >>> right fletxaComposaData -- processa els x tals que Right x (vegeu ArrowChoice)
eitherData <- runKleisli fletxa () case eitherData of Left err -> ioError err -- dispara excep. Right strData -> putStrLn $ "correcte: " ++ strData runhaskell provaFletxa
Entreu any (aaaa): 1904 Entreu mes (mmm): feb Entreu dia (dd): 29 correcte: 29/feb/1904
Fletxes amb resultats múltiples - La biblioteca HXT La biblioteca HXT (Haskell XML Toolbox) tracta els arbres XML amb filtres fletxa. Vegeu.HaskellWiki - Haskell XML ToolboxArrowXml de la biblioteca HXTAPI de la biblioteca HXT
Per evitar l'ús d'excepcions, HXT dona sempre els múltiples resultats (subarbres) dels filtres en una llista, amb zero o més elements, segons l'èxit i el nombre dels elements resultants.
Extracte del codi del tipus ListArrow.El tipus ListArrow -- tipus de la fletxa ListArrow de HXT
newtype LA a b = LA { runLA :: a -> [b] }
-- generador de fletxes partint d'un filtre d'un sol resultat embolcallant-lo en una llista. instance Arrow LA where arr f = LA $ \ x -> [f x] -- cas de f :: a -> b ...
-- generador de fletxes partint d'un filtre que ja ofereix els resultats en una llista. instance ArrowList LA where arrL f = LA f -- cas de f :: a -> [b]
-- composició de fletxes hxt -- aplica el filtre de la fletxa subseqüent a cadascun dels elements -- de la llista de resultats de la primera i en concatena les llistes de resultats
instance Category LA where ... LA g. LA f = LA $ concatMap g. f
-- Definició de (>>>) a Control.Arrow de la biblioteca de GHC basada en (.) de Category (>>>) :: Category cat => cat a b -> cat b c -> cat a c f >>> g = g. f
Exemple - Extreure informació d'un document XML Fitxer xml de dades llibres.xml per a l'exemple.
<?xml version='1.0' ?> <doc> <llibres> <llibre> <titol>Tirant Lo Blanc</titol> <autor>Joanot Martorell</autor> <biblioteca>A</biblioteca> </llibre> <llibre> <titol>El Quixot</titol> <autor>Cervantes</autor> <biblioteca>B</biblioteca> </llibre> </llibres> </doc>
Aquí la majoria dels filtres Fletxa que es veuen són del de tipus :: (ArrowXML efecte) => efecte XmlTree c -- i la sortida és de tipus c (si c és llista) o, altrament, [c]
, el resultat de la seva aplicació serà, excepte al darrer pas, la llista dels subArbres resultants del filtre, i a cadascun dels quals s'aplicarà el filtre següent.