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 (encadenament) basant-se en filtres.

Generalitza el concepte de Mònada, d'encadenament d'operacions, admetent paral·lelisme en els càlculs i no-determinisme. 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" com a sol·lució 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ó.

Seguint el document 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 f = Kleisli (\ x -> return (f x))          -- f :: (b -> c)
 
  -- combinació de filtres
  (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".

La definició a GHC és una mica diferent com es mostra més avall, incorporant operacions de generació de Tuples2 partint de dos filtres i encadenament de les fletxes amb origen Tupla2.

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.

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

abstracció d'un tipus de filtre

La clàusula newtype a Haskell també s'utilitza per definir un tipus com a abstracció d'un tipus de funció. Això permet definir operacions de combinació de funcions del tipus específic.

 -- sigui, per exemple, f :: a -> [b]    -- el tipus de funció sobre el que volem definir operacions
 --                     x :: a
 
 newtype TFiltre a b = Filtre { runFiltre :: a -> [b] }
 
 --    Filtre    :: (a -> [b]) -> TFiltre     -- ''constructor''
 --    runFiltre :: TFiltre -> (a -> [b])     -- ''inversa_del_constructor''
 
 filtre_f = Filtre f             -- element del nou tipus aplicant el constructor a la funció
 
 runFiltre filtre_f              -- retorna la funció f original, aplicant la ''inversa_del_constructor''
 
 runFiltre filtre_f x            -- aplica la funció original a x

operacions de les fletxes

La classe Arrow descriu entre d'altres, operacions de combinació de filtres com les descrites a continuació per expressar comportaments en el procés de corrents de dades (ang:Streams), generació de Tuples2 per arrosegar informacions, i aplicacions de filtres a les tuples. Vegeu

El tipus de filtre fletxa més habitual és una terna

(Arrow a => a b c) 

• on b és el tipus de l'entrada al filtre
• i el tipus de la sortida és funció de c

 -- creem el tipus de filtre que implementarà la classe Arrow a partir
 --               d'un tipus de funció que ens interessi. Vegeu apartat "abstracció d'un tipus de filtre".
 
 -- per a un tipus de fletxa :: b -> T c
 
 newtype TFiltre b c = Filtre { runFiltre :: b -> T c }   
 
 -- Els filtres han d'implementar la classe Category
{- 
 class Category cat where
    -- id and (.) must form a monoid.
 
    --the identity morphism
    id :: cat a a
 
    -- morphism composition 
    (.) :: cat b c -> cat a b -> cat a c
-}
 
 -- class Category a => Arrow a where ...
 
 instance Arrow TFiltre where
 
   -- generador crea un filtre Fletxa a partir d'una funció (f::b->c) i el constructor del ''newtype''
   -- primer cal elevar la funció (f::b->c) al tipus de funció del filtre, aquí (:: b -> T c)
 
   arr :: (b -> c) -> TFiltre b c
   arr f = Filtre (pure f)  -- eleva la funció a la categoria del filtre
 
   -- en el cas del Kleisli    
   arr f = Kleisli (\ x -> return (f x))
 
   -- injecta la mateixa entrada a cadascun de dos filtres resultant una tupla2
   --   permet arrossegar una dada d'entrada a la sortida aparellant-la amb la transformada
   --     si un dels filtres és l' identitat
   f &&& g  = arr (\x     -> (runFiltre f x, runFiltre g x))
 
   -- aplica dos filtres als components d'una tupla2 d'entrada
   --
   f *** g  = arr (\(x,y) -> (runFiltre f x, runFiltre g y))
 
   -- aplica un filtre a una de les parts d'una tupla2, passant l'altra directament al resultat
   --                                   
   first  f = f *** arr id
 
   second f = arr id *** f
 
 
 -- Combinadors:
 
   -- returnA: filtre identitat -- rol equivalent al ''return'' de la Mònada
   returnA = arr id
 
   -- en una clàusula ''proc'', 
   --    returnA -< expressió -- caracteritza el tipus de la fletxa final amb el tipus de l'expressió
 
    -- (-<) aplica una fletxa a una entrada
   f -< x
 
   -- composició de filtres, passant la sortida del primer a l'entrada del segon.
   -- visualitza el sentit del corrent de dades. (ang: ''stream'')
 
   f >>> g  = g . f        -- aplica primer f i després g
 
   -- composició mostrant sentit invers del corrent.
   f <<< g  = f . g                
   ...

Vegeu i l'exemple sobre XML en aquesta pàgina.

Compiladors que suporten Fletxes: GHC, Hugs

combinació de Fletxes i sintaxi específica

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

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

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 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
  --      , oferint el resultat tal cual.
  (|||) :: 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

Ent./Sort. amb fletxes de Kleisli (mònades elevades a fletxes)

Partint de la definició esmentada més amunt, lectura de 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 ésDiaIlegal = (iDia <= 0)
                || (strMes == "feb" && ((ésAnyDeTraspàs && iDia > 29)
                                        || (not ésAnyDeTraspàs && iDia > 28))
                                        )
                || ((strMes `elem` [ "abr", "jun", "set", "nov"]) && (iDia > 30))
                || iDia > 31
 
        if ésDiaIlegal
           then returnA -< Left $ userError "dia ilegal"
           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

Exemple - Extreure informació d'un document XML

La bilioteca HXT (Haskell XML Toolbox) tracta els arbres XML amb filtres fletxa. Vegeu. Cal la versió GHC >= 6.10

Per evitar l'ús d'excepcions, HXT dóna sempre la sortida dels filtres en una llista, amb zero o més elements, segons l'èxit i el nombre dels elements resultants.

Si la sortida d'un filtre és un sol element, serà convertit en llista, si la sortida ja és una llista es deixarà com a tal. Hi ha funcions constructores de Fletxes per a cada cas (arr, arrl).

-- instal·lació -- l'exemple actual és per a la versió hxt-8.5.* i GHC >= 6.10 i GHC < 7.0
-- cal especificar la versió i compilar amb GHC < 7.0
cabal install hxt-8.5.4 

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, NoMonomorphismRestriction #-}  -- pragma amb extensions del llenguatge,
 --                            equivalent a -X<opcio> a línia de comandes 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 (returnA, (>>>), (<<<))
 
-- importacions del paquet HXT (versió 8..) per mostrar d'on provenen els ident.
 
import Text.XML.HXT.Arrow.XmlArrow (ArrowXml, isElem, hasName, getText)
 
import Control.Arrow.ArrowTree (deep, getChildren)
 
import Text.XML.HXT.Arrow.XmlIOStateArrow (runX)
import Text.XML.HXT.Arrow.ReadDocument (readDocument)
import Text.XML.HXT.DOM.XmlKeywords ( a_validate, v_0)
import Text.XML.HXT.DOM.TypeDefs (XmlTree)
 
import Text.XML.HXT.Arrow    -- exporta tots els identificadors del paquet          
 
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 { llibTitol = titol,         -- encaixa patró Llibre obtenint-ne els valors dels camps
                   llibAutor = autor }) =
         "\nTitol: " ++ titol ++ "\nAutor: " ++ autor
 
subarbres_elementsXml_AmbEtiqueta :: (ArrowXml a) => String -> a XmlTree XmlTree
  -- genera un filtre Arrow de XmlTree a XmlTree, 
  --                  quin resultat és la llista de subarbres que compleixen
 
subarbres_elementsXml_AmbEtiqueta etiq = deep (isElem >>> hasName etiq)
 
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 <<< subarbres_elementsXml_AmbEtiqueta "titol" -< xmlTree_llibre
    autor <- obtenirText <<< subarbres_elementsXml_AmbEtiqueta "autor" -< xmlTree_llibre
    returnA -< Llibre { llibTitol = titol,     
                        llibAutor = autor}
 
processa :: String -> IO [TLlibre]
 
processa nomFitxerXml = do
    let fletxa_Llibres = readDocument [(a_validate, v_0)] nomFitxerXml
                    >>> subarbres_elementsXml_AmbEtiqueta "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ó (desenvolupat amb ghc 6.10, per a ghc 7.x cal actualitzar l'exemple), cal especificar la versió de hxt, perquè la nova ha modificat la interfície):

cabal install hxt-8.5.4
ghc --make llista-llibres.hs -package=hxt-8.5.4

./llista-llibres llibres.xml

resultat:

Titol: Tirant Lo Blanc
Autor: Joanot Martorell

Titol: El Quixot
Autor: Cervantes

Fletxes en la pràctica

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

Enllaços externs

• 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)(anglès) Conté implementació de Fletxes en OCaml Docum.(anglès)
• Paul Hudak - Arrows, robots and functional reactive programming (anglès)