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. També el podríem anomenar "Efecte morfisme". Vegeu també Teoria de categories.

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

Generalització de la Mònada - Fletxes de Kleisli[modifica | modifica el codi]

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 (efectes morfisme), a partir de les operacions
class Arrow efecte where

  arr   :: (b -> c) -> efecte b c     -- generador elevant una funció a la categoria d'efecte morfisme

  (>>>) :: efecte b c -> efecte c d -> efecte b d         -- combinació / encadenament d'efectes morfisme

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

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

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

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 morfisme
  first :: efecte b c -> efecte (b, d) (c, d)        -- converteix un efecte morfisme 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.[1]

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

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 | 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 operacions 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 partint d'altres filtres. Exemple:[5]

 -- 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[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 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 | 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 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
 
    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:

Títol: Tirant Lo Blanc
Autor: Joanot Martorell

Títol: El Quixot
Autor: Cervantes

Fletxes a 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]