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.

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" 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 Arrow deriva de la classe 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:

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

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.

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.

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

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

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

Vegeu també

• Elm (llenguatge de programació): programació reactiva funcional d'interfícies d'usuari en navegadors web.

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

Viccionari