Fletxa (programació funcional)
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.[1]
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"[2][3] 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.[3]
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[modifica]
Seguint el document[2] 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".[2]
Fletxes i Parells[modifica]
A les mònades les operacions return i (>>=) són suficients per efectuar càlculs com ara la suma de resultats de computacions.[2]
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).[2]
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.[2]
-- ''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.[2]
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[modifica]
A banda de la descripció precedent que correspon a un document de l'any 1998,[2] l'actual definició a GHC de la classe Arrow[4] deriva de la classe Category[5] 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.[2]
combinació de Fletxes i sintaxi específica[modifica]
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:[6]
-- 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 tipus[7]
addA f g = (f &&& g) >>> arr (\ (y, z) -> y + z)
alternatives ArrowChoice[modifica]
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[modifica]
Ent./Sort. amb fletxes de Kleisli (mònades elevades a fletxes)[modifica]
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[modifica]
La biblioteca HXT (Haskell XML Toolbox) tracta els arbres XML amb filtres fletxa. Vegeu.[8][9][10]
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.[11]
-- 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[modifica]
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.
-- fitxer llista-llibres.hs -- Extreure el títol i l'autor dels llibres de l'XML d'entrada
{-# LANGUAGE Arrows, PackageImports, RecordWildCards #-} -- pragma amb extensions del llenguatge,
-- equivalent a -X<opcio> a línia d'ordres de compilació
module Main (main) where
import qualified Control.Monad as Monad
import System.Environment (getArgs)
import System.Exit (exitSuccess, exitWith, ExitCode(..))
import Control.Arrow
import "hxt" Text.XML.HXT.Core
import "hxt" Text.XML.HXT.DOM.XmlKeywords
import "hxt-xpath" Text.XML.HXT.XPath.Arrows (getXPathTrees)
-- per a documentació (però ja queda importat per Text.XML.HXT.Core) :
-- import "hxt" Text.XML.HXT.Arrow.ReadDocument (readDocument)
data TLlibre = Llibre { -- registre per a les dades que interessen
llibTitol :: String,
llibAutor :: String
}
deriving (Eq)
instance Show TLlibre where -- personalitzant-ne la impressió
show (Llibre {..}) =
"\nTítol: " ++ llibTitol ++ "\nAutor: " ++ llibAutor
obtenirText :: (ArrowXml efecte) => efecte XmlTree String
-- genera un filtre Arrow de XmlTree a String,
-- (la composició de filtres ArrowXml concatena (++) les sortides en una sola tira)
obtenirText = getChildren >>> getText
llibre_del_subarbreElementXml_Llibre :: (ArrowXml efecte) => efecte XmlTree TLlibre
-- genera un filtre Arrow de XmlTree a TLlibre
llibre_del_subarbreElementXml_Llibre = proc xmlTree_llibre -> do
títol <- obtenirText <<< getXPathTrees "/llibre/títol" -< xmlTree_llibre
autor <- obtenirText <<< getXPathTrees "/llibre/autor" -< xmlTree_llibre
returnA -< Llibre { llibTitol = títol,
llibAutor = autor}
processa :: String -> IO [TLlibre]
processa nomFitxerXml = do
let fletxa_Llibres = readDocument [withValidate no] nomFitxerXml
>>> getXPathTrees "//llibre"
>>> llibre_del_subarbreElementXml_Llibre
-- runX aplica sobre un XmlTree buit inicial definit internament, el filtre fletxa de l'expressió
llibres <- runX fletxa_Llibres
return llibres
main = do
args <- getArgs
case args of
[] -> do
putStrLn "afegiu el fitxer xml dels llibres"
exitWith $ ExitFailure 1
(arg:_) -> do
llibres <- processa arg
Monad.mapM_ print llibres
exitSuccess
compilació i execució (compilat amb ghc 7.6.3, hxt-9.3.1.3 i hxt-xpath-9.1.2.1):
cabal install hxt ghc --make llista-llibres.hs -package=hxt
./llista-llibres llibres.xml
resultat:
Títol: Tirant Lo Blanc Autor: Joanot Martorell
Títol: El Quixot Autor: Cervantes
Fletxes a la pràctica[modifica]
- La biblioteca Fudgets d'interaccions amb els controls gràfics (de Magnus Carlsson i Thomas Hallgren).[12][13]
- Yampa (programació reactiva funcional)[14]
- Hxt : Haskell XML Toolbox, emprada més amunt.
Vegeu també[modifica]
- Elm (llenguatge de programació): programació reactiva funcional d'interfícies d'usuari en navegadors web.
Referències[modifica]
- ↑ «Arrows: A General Interface to Computation» (en anglès). [Consulta: 8 gener 2018].
- ↑ 2,0 2,1 2,2 2,3 2,4 2,5 2,6 2,7 2,8 Generalising Monads to Arrows(anglès)
- ↑ 3,0 3,1 Understanding Arrows(anglès)
- ↑ Control.Arrow Arxivat 2012-08-04 at Archive.is(anglès)
- ↑ Control.Category Arxivat 2014-06-28 a Wayback Machine.(anglès)
- ↑ Sintaxi específica de les Arrow (anglès)
- ↑ La fletxa addA(anglès)
- ↑ HaskellWiki - Haskell XML Toolbox(anglès)
- ↑ ArrowXml de la biblioteca HXT(anglès)
- ↑ API de la biblioteca HXT (anglès)
- ↑ El tipus ListArrow[Enllaç no actiu]
- ↑ Fudgets - Purely functional processes with applications on Graphical User Interfaces(anglès)
- ↑ Programming with Fudgets(anglès)
- ↑ La biblioteca Yampa(anglès)
Enllaços externs[modifica]
- Arrows: A General Interface to Computation(anglès)
- Haskell wikibook - Understanding Arrows(anglès)
- Hughes: Generalizing Monads to Arrows(anglès)
- OPIS - Sistemes distribuïts (amb fletxes) Arxivat 2011-10-30 a Wayback Machine.(anglès) Conté implementació de Fletxes en OCaml Docum. Arxivat 2011-10-30 a Wayback Machine.(anglès)
- Paul Hudak - Arrows, robots and functional reactive programming[Enllaç no actiu] (anglès)