Fletxa (programació funcional)

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 morfismes amb efectes col·laterals. Vegeu també Teoria de categories.

Generalitza el concepte de Mònada, d'encadenament d'operacions, admetent paral·lelisme en els càlculs i no-determinisme (de la wiki anglesa). Les mònades en son 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"[1][2] 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.[2]

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ó.

Seguint el document[1] i partint de l'encadenament de resultats de les computacions mònada

class Monad m where
  return :: a -> m a 
  (>>=)  :: m a -> (a -> m b) -> m b
 ...
 
-- es poden definir computacions encadenades Fletxa a partir de les operacions
class Arrow a where
 
  arr   :: (b -> c) -> a b c     -- generador a partir d'una funció
 
  (>>>) :: a b c -> a c d -> a b d         -- combinació
 
-- 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".[1]

Fletxes i Parells

Amb les mònades les operacions return i (>>=) són suficients per efectuar càlculs com ara la suma de computacions.[1]

sumaM :: Monad m => m Int -> m Int -> m Int
sumaM x y = x >>= \u -> y >>= \v -> return (u+v)

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.[1]

classe Arrow a where
  arr :: (b -> c) -> a b c
  (>>>) :: a b c -> a c d -> a b d 
  first :: a b c -> a (b, d) -> a (c, d)
 
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, modificant-ne el primer element.[1]

  -- ''second'' 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 a => a b c -> a d e -> a (b, d) (c, e)
  f *** g = first f >>> second g
 
  -- (&&&) obté un parell de l'aplicació de dues fletxes sobre una mateixa entrada
  (&&&) :: Arrow a => a b c -> a b d -> a b (c, d)
  f &&& g = arr (\b -> (b, b)) >>> (f *** g)

Amb aquestes definicions la suma de computacions fletxa queda completament definida.[1]

sumaA :: Arrow a => a b Int -> a b Int -> a b Int
sumaA f g = (f &&& g) >>> arr (\(u, v) -> u + v)
Estalvi de recursos

Mentre que en una computació monàdica la darrera computació en un bloc do té accés a les referències lligades als resultats precedents, en una Fletxa el resultat precedent que convingui tenir a mà posteriorment caldrà aplegar-lo a la sortida en Tupla2 amb el resultat de la computació actual.

És per això que les computacions Fletxa eviten la possibilitat de les Mònades de deixar referències a objectes que han deixat d'interessar, i per tant espai ocupat inútilment.

La definició a GHC[modifica | modifica el codi]

A banda de la descripció precedent que correspon a un document de l'any 1998,[1] l'actual definició a GHC de la classe Arrow[3] deriva de la classe Category[4] que descriu els morfismes amb les operacions identitat i composició.

La definició actual de (>>>) és igual a la composició de morfismes (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 second, (***) i (&&&) corresponent a les descrites més amunt del document de John Hughes de 1998.[1]

combinació de Fletxes i sintaxi específica[modifica | modifica el codi]

La clàusula "proc" permet definir un filtre a partir d'altres filtres. Exemple:[5]

 -- combinació de dos filtres ''fletxa'' f i g resultant un altre filtre
 
 {-# LANGUAGE Arrows #-}
 import Control.Arrow
 
 addA :: Arrow a => a b Int -> a b Int -> a 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     -- aplica la ''fletxa'' f a l'entrada x, obtenint y
                    z <- g -< x     -- aplica la ''fletxa'' g a l'entrada x, obtenint z
                    returnA -< y + z      -- aplica (y + z) al filtre de sortida, 
                                          --   caracteritzant el tipus del retorn

Equivalent de la fletxa addA expressada en operacions canòniques del tipus[6]

addA f g = (f &&& g) >>> arr (\ (y, z) -> y + z)

alternatives ArrowChoice[modifica | modifica el codi]

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 a => ArrowChoice a where
  -- ''left f'' passa el contingut de les entrades etiquetades Left per f 
  --     re-etiquetant el resultat, mentre que les Right passen inalterades  
  left :: a b c -> a (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 :: a b c -> a (Either d b) (Either d c)
 
  -- ''f ||| g'' passa les Left per f i les Right per g
  (|||) :: a b d -> a c d -> a (Either b c) d
 
  -- ''f +++ g'' passa les Left per f i les Right per g
  --   , re-etiquetant el resultat amb Left o Right.
  (+++) :: a b c -> a b' c' -> a (Either b b') (Either c c')
 
-- és el cas que
left f == f +++ arr id
 
right f == arr id +++ f
 
f +++ g == left f >>> right g

Exemples[modifica | modifica el codi]

Ent./Sort. amb fletxes de Kleisli (mònades elevades a fletxes)[modifica | modifica el codi]

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 | modifica el codi]

La bilioteca HXT (Haskell XML Toolbox) tracta els arbres XML amb filtres fletxa. Vegeu.[7][8][9]

Per evitar l'ús d'excepcions, HXT dóna 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.[10]

-- 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 morfismes 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 | modifica el codi]

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 a) => a 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 {..}) =   
         "\nTitol: " ++ llibTitol ++ "\nAutor: " ++ llibAutor
 
 
obtenirText :: (ArrowXml a) => a 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 a) => a XmlTree TLlibre
  -- genera un filtre Arrow de XmlTree a TLlibre 
 
llibre_del_subarbreElementXml_Llibre = proc xmlTree_llibre -> do
 
    titol <- obtenirText <<< getXPathTrees "/llibre/titol" -< xmlTree_llibre
    autor <- obtenirText <<< getXPathTrees "/llibre/autor" -< xmlTree_llibre
    returnA -< Llibre { llibTitol = titol,     
                        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:

Titol: Tirant Lo Blanc
Autor: Joanot Martorell

Titol: El Quixot
Autor: Cervantes

Fletxes en la pràctica[modifica | modifica el codi]

  • La biblioteca Fudgets d'interaccions amb els controls gràfics (de Magnus Carlsson i Thomas Hallgren).[11][12]
  • Yampa (programació reactiva funcional)[13]
  • Hxt : Haskell XML Toolbox, emprada més amunt.

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]

  1. 1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 Generalising Monads to Arrows(anglès)
  2. 2,0 2,1 Understanding Arrows(anglès)
  3. Control.Arrow(anglès)
  4. Control.Category(anglès)
  5. Sintaxi específica de les Arrow (anglès)
  6. La fletxa addA(anglès)
  7. HaskellWiki - Haskell XML Toolbox(anglès)
  8. ArrowXml de la biblioteca HXT(anglès)
  9. API de la biblioteca HXT (anglès)
  10. El tipus ListArrow
  11. Fudgets - Purely functional processes with applications on Graphical User Interfaces(anglès)
  12. Programming with Fudgets(anglès)
  13. La biblioteca Yampa(anglès)

Enllaços externs[modifica | modifica el codi]