programació funcional

Programació funcional

Haskell/Hugs

(o bé)

Un llenguatge de programació funcional pur.

Mateu Villaret (2007)

Planificació• Introducció:

– Què és programació funcional.

– Per què programació funcional.

– Context històric.

• Haskell/Hugs:– Descripció del nostre entorn. Que és un “Script”.

• El llenguatge:– Tipus/classes.

– Llistes.

– Funcions/operadors.

– Funcions d’ordre superior.

Què és la programació funcional?

• És el paradigma de programació basat en el càlcul d’expressions.

• Les expressions podran contenir les funcions que haguem definit naturalment.

• Un programa consistirà en una sèrie de definicions de funcions que ens permetran després “calcular” expressions.

Què és la prog. Funcional pura?

• El paradigma funcional consisteix en dir què fer enlloc de com fer-ho.

• El valor d’una expressió depèn només dels valors de les seves subexpressions. Evita els efectes laterals de les assignacions fent més fàcil la verificació, Programació funcional pura.

Què és la prog. Funcional pura?

• No hi ha gestió explícita de memòria, disposa de Garbage collector.

• Aporta una sèrie de característiques que fan més fàcil la modularitat i per tant la reutilització de codi.– Funcions d’ordre superior– Lazyness

Per què programació funcional?

• L’efecte “nociu” de l’assignació:

No tenim “commutativitat” enl’aplicació de la funció f, cosaque dificulta la verificació ila paral·lelització.

Per què programació funcional?

• L’avaluació “Lazy” (només alguns):– Suposem que el programa g genera una sortida

massa gran com perquè hi càpiga a memòria.– El programa f només necessita una primera part

dels càlculs de g.– Així en programació no Lazy el còmput:

f(g(entrada)) no es podria realitzar (pèrdua de modularitat).

– L’avaluació lazy només avalua fins a on li cal.

Per què programació funcional?

• Funcions d’ordre superior:– Són funcions que reben funcions com a

paràmetres; poden retornar funcions també.– Estan predefinides les més interessants: map,

foldr, foldl, zip, ...

• Gestió de llistes molt senzilla:– [el1, … , eln], cap:cua i [ ].

Per què programació funcional?

• Definir el problema és resoldre’l. Definir una funció és dir què és la solució i no com s’ha de fer:

Per què programació funcional?

• Típicament realitzen un control estricte de tipus utilitzant un sistema d’inferència de tipus:– El programador no està obligat a donar el tipus

de les expressions.– El compilador té un algorisme que l’infereix.– Si es declara un tipus, es compara amb l’inferit.

• Alguns disposen de polimorfisme. (genericitat o polimorfisme paramètric)

Per què programació funcional?

• Es diu que un programador funcional és un ordre de magnitud més eficient que un imperatiu.

• Actualment els compiladors han millorat molt i tenen ràtios d’eficiència similars al C i fins i tot millors quan s’usa la “lazyness”.– Degut a l’ús intensiu de la recursivitat, es consideraven els programes

funcionals lents.

Sobre la “ineficiència”++ :: [a] -> [a] -> [a][]++ lls = lls(x:cua) ++ lls = x:(cua ++ lls)

capgirar :: [a] -> [a]capgirar [] = []capgirar (x:cua) = (capgirar cua) ++ [x]

Aquesta funció te un cost quadràtic. Haskell disposa d’èines automàtiques que passen la definició de capgirar, a una versió lineal…MAG tool (Oxford)

Context històric.

• Està basada en el model matemàtic de còmput ideat als anys 30 per Alonzo Church anomenat: λ-calculus.

• Cap als 50, John McCarthy dissenya LISP. Actualment continuat a SCHEME.

• Al 1978, J. Backus (Fortran i Algol) aposta per la FP al llegir l’article: “Can Programming be liberated from the Von Neumann style?”. Definint també el llenguatge funcional FP.

Context històric.

• A mitjans dels 70, apareix ML (Metallenguatge), que encara fa concessions a la prog. Imp.

• A mitjans dels 80 s'estandarditza SML (eficient).• Simultàniament D. Turner crea Miranda: lazy,

pattern-matching, … (és marca registrada)• Al 1987 degut a la proliferació de FPLs és

decideix definir un Standard: HASKELL.• Al 1998 s’ha creat una versió estable Haskell98.

Haskell/Hugs (i)

• Haskell és un llenguatge de programació funcional pur que està suportat per diferents compiladors i intèrprets: GHC, Gofer, Hugs,…

• Hugs (Haskell Users’Gofer System) soporta un subconjunt del llenguatge Haskell. És un intèrpret d’expressions. Es poden carregar “scripts” definint les nostres funcions i després utilitzar-les en expressions. (calculadora)

Haskell/Hugs (ii)

• S’invoca amb: hugs <opcions><nomscr.hs> i es carrega automàticament un script que es diu prelude.hs, on hi ha la definició d’una sèrie de funcions i relacions entre tipus bàsiques.

• Una vegada carregat tenim el prompt esperant o bé una expressió a avaluar o bé una comanda per a l’intèrpret.

Haskell/Hugs (iii)

• Les comandes s’invoquen mitjançant “:comanda” d’entre les que hi ha:– :? ,per invocar el Help.

– :l nomf ,per carregar un script.

– :r ,per repetir l’ultima acció.

– :type expr ,per consultar el tipus d’una expressió.

– :quit ,per sortir.

– :names ,mostra tots els noms.

– :set ,per activar variables d’entorn. (+Eemacs)– ...

Haskell/Hugs (iv)

• Un Script principalment contindrà definicions de funcions que comencen amb minúscula.

• Les funcions es podran definir: per casos, per “pattern matching”, per recursivitat o directament.

• Poden tenir un descriptor de tipus associat:nomf:: t1->t2->…->tn

• L’avaluació d’una expressió es podrà descriure com un procés de reescriptura fins a no poder reescriure més (representació canònica).

El llenguatge.(1)• Com ja hem dit als Scripts hi posarem les definicions de

les funcions:– quadrat:: Int -> Int quadrat x = x * x

• La notació: -> significa “retorn” és a dir: quadrat és quelcom que “rep un enter i torna un enter”.

• L’avaluació la veurem com a reescriptura:– quadrat 3 {la x val 3. Es reescriu a la def. de quadrat} 3 * 3

{el producte està definit} 9 {representació

canònica}

El llenguatge.(2)

• Haskell té tots els tipus comuns: Bool, Int, Char i Float.

• A més de tuples que es representen amb:(camp_1,…, camp_n)

• També té el tipus llista polimòrfica:[],(cap:cua), l1++l2.

• Ens permetrà definir TAD’s.

• També disposa de classes i un cert tipus de derivació.

El llenguatge.(3)

• Podem provar de definir una funció que ens doni els n primers parells …– funció parell– llista infinita de naturals– funció que ens doni els parells…(comph. Lists), pars.– funció que ens doni els n primers elements d’una

llista, nelems.

Els booleans: (Bool)

• Les constants són: True i False.

• Els operadors són:

– &&

– ||

– not• Una possible definició de la funció xOr:

– xOr :: Bool -> Bool -> BoolxOr x y = ( x || y ) && not ( x

&& y )

Els enters: (Int)

• Els valors que pot pendre estan acotats per maxBound que sol ser: 2147483647.

• Per valors més grans fer servir el tipus Integer.• Té els operadors típics: + , - , * , ^.

• Funcions: div, mod, abs i negate. En general les funcions es poden usar com a operadors infixes i els hi posem entre accent obert: `f`. Pel procés invers, posar operador entre: ( op ).

• Podem passar a Float amb: fromInt.

Els “reals”: (Float)

• Els valors representen números reals però amb precisió limitada. Permeten notació científica.

• Hi ha altres tipus amb més precisió: Double per a tenir doble precisió i Rational per a fracions d’Integers amb precisió total.

• Té les funcions i operadors típics però cal notar que:– ^:: Float ->Int -> Float i **:: Float ->Float -> Float.

• Conversió: ceiling, floor i round :: Float -> Int.

Els caràcters: (Char)

• Els valors els tancarem entre cometes simples: ’ ’.• Uns quants caràcters especials són:

– ’\t’, ’\n’, ’\\’, ’\’’ i ’\”’.

• Disposem de funcions de conversió:– ord :: char -> Int – chr :: Int -> char.

• Exemple per a saber si és un dígit:– isDigit :: Char -> Bool

isDigit c = ( ‘0’ <= c) && ( c <= ‘9’ )

Definició de funcions• Hi ha varies maneres de definir funcions, però tota

definició de funció queda delimitada per un Layout:

– fun pf1 pf2 … pfn| g1 = e1

| g2 = e2…

otherwhise = en

– f2 pf1 … = e2…

Paràmetres formalsNom de la funcióen minúscules

“Guards”

Definició d’operadors• Els ops. es poden definir dels següent símbols:

– ! ,# ,$ ,% ,& ,* ,+ , . ,/ ,< ,> ,= ,? ,\ ,^ , | ,: ,- ,~.

– (&&&) :: Int -> Int -> Int x &&& y | x > y = y

| otherwise = x

• Per a definir l’associativitat i prioritat de l’orperador, podem usar: infixl, infixr, i infix. (left, right i non-assoc).– infixl 7 &&&.

Maneres de definir funcions(Patrons 1)

• Per patrons simples:– f par = ex (notem que ex segurament tindrà par)

– fact n = product [1.. n]

• Els patrons permeten definir les funcions, en funció de la forma dels argument:– not :: Bool -> Bool

not true = falsenot false = true

Maneres de definir funcions(Patrons 2)

• Podem donar-los nom:– cua :: [a] -> [a]

cua (x:xs) = xs

• Per patrons n+k:– x ^ 0 = 1 x

^ (n+1) = x * (x ^ n)

• No podem usar dues vegades una variable amb el mateix nom en una definició:– f x x = exp

Maneres de definir funcions(Guardes)

• Cada una de les equacions d’una definició de funció, pot tenir guardes que en determini l’aplicació depenent del valor dels arguments:– f x1 x2 … xn | condi1 = e1

| condi1 = e2| …

| condin = en

– Per exemple:• minim :: Int -> Int -> Int

minim x y | x<= y = x| otherwise = y

Maneres de definir funcions(Definicions locals)

• Ens pot interessar definir variables o funcions amb un valor local a la definició de la funció. Per exemple, saber el número d’arrels d’una funció quadràtica de la forma ax2 + bx + c:– numarrels a b c | disc > 0 = 2

| disc == 0 = 1| disc < 0 = 0

where disc = b*b - 4*a*c

• També les podem posar enmig d’una expressió:– let <decl> in <expr>, p. ex: let p x = x in p 2

Maneres de definir funcions(Expressions recursives)

• A banda de com haguem decidit definir la funció, les expressions que la defineixin poden ser com vulguem, en particular recursives:– fun n

| n == casbase = exp0| n > casbase = … fun (pred n) …

• Per a garantir l’acabament de la definició ens cal que la crida recursiva, es faci sobre un element menor i que existeixi la definició final del casbase.

Maneres de definir funcions(Expressions recursives)

– fac :: Int -> Int fac n | n == 0 = 1 | n > 0 = fac ( n -

1 ) * n | otherwise = error “n ha de ser >= 0”

– fib :: Int -> Int fib n| n == 0 = 0 | n == 1 = 1| n > 1 = fib ( n -

2 ) + fib ( n - 1 )

La funció error enspermet “reportar” els errors d’execució.

Definicions de llistes especials (1).

• Seqüències aritmètiques:– [1 .. ] equival a [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,....– [1..5] equival a [1, 2, 3, 4, 5]– [1,3..] equival a [1, 3, 5, 7, 9, 11, 13, 15 ,….– [‘a’,..,’z’] equival a [‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’,….

• Llistes per comprehensió:– [ <exp> | <q1>, <q2> …<qn>]– De qualificadors n’hi ha de generadors i de filtres:

• generadors: x <- [ elems]• filtres: expressió booleana que decideix si un element

generat pel generador pertany a la llista generada o no.

Definicions de llistes especials (2).

• Veiem uns quants exemples:– [ x*x | x <- [1..10], even x ]– [ ( x, y ) | x <- [ 1, 2, 3], y <- [ 9, 10, 11] ]– [ ( x, y ) | x <- [ 1, 2, 3], y <- [ 1 ..x] ]

• pot ser més eficient un canvi d’ordre:– [ ( x, y ) | x <- [ 1 .. 3 ], y <- [ 1 ..2 ], even x ]– [ ( x, y ) | x <- [ 1 .. 3 ], even x, y <- [ 1 ..2 ] ]

Una solució als parells

• parell x = x `mod` 2 == 0

• nats = [1..]

• parells = [x | x<- nats, parell x]

• nelem [] n = []

• nelem _ 0 = []

• nelem (x:xs) (n+1) = x: (nelem xs n)

• nparells n = nelem parells n

Altres expressions

• Una alternativa a definir guardes és per casos:– paritat x = case (x mod 2) of 0 -> “parell”

1 -> “senar”

• També podem usar funcions sense nom amb expressions lambda:– (\ x y -> x + y) 2 3 valdrà 5

• Composició de funcions:– ( f . g ) x = f ( g x ) ( . ) :: ( b -> c ) -

> ( a -> b) -> ( a -> c )

Funcions d’ordre superior (i)

• Direm que una funció és d’ordre superior si pren com a argument o torna, alguna funció.

• Prenem com a exemple l’aplicació sobre una llista:– dobletots llis = [ 2*x | x<- llis]– o bé:– dobletots [ ] = [ ]

dobletots (x:xs) = 2*x : dobletots xs

Funcions d’ordre superior (ii)

• Un patró d’aplicació d’una funció qualsevol a tots els element d’una llista seria:– map f [ ] = [ ]

map f (x:xs) = f x : map f xs

• que tindria el tipus:– map :: ( a -> b ) -> [ a ] -> [ b ]

Funcions d’ordre superior (iii)

• Un patró de filtratge per a un filtre qualsevol pot ser:– filter p [ ] = [ ]

filter p (x:xs)| p x = x : filter p xs

| otherwise = filter p xs

• quin tipus tindria filter?

Funcions d’ordre superior (iv)• Ajuntar llistes creant parells:

– zip :: [a] -> [b] -> [(a,b)]– exemple: – zip [1,2,3] “hey” [(1,’h’),

(2,’e’),(3,’y’)]

• Aplicació de funció sobre dues llistes:– zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys zipWith

f _ _ = [ ]

• Quin tipus te? ( a, b i c) són variables de tipus.– zipWith :: ( a -> b -> c ) -> [ a ] -> [ b ] -> [ c ]

Funcions d’ordre superior (v)• Plegament dret:

– foldr :: (a -> b -> b) -> b -> [ a ] -> b foldr f ultim [ ] = ultim foldr f ultim (x:xs) = f x (foldr f ultim xs)

• així:– foldr f a [e1, e2, ... en] f e1 ( f

e2 ( f e3 … (f en a) ...))

• exemples:– andl boleans = foldr (&&) True boleans– orl boleans = foldr (||) False boleans

Funcions d’ordre superior (vi)• Plegament esquerra:

– foldl f ult [ ] = ult foldl f ult (x:xs)= foldl f (f ult x) xs foldl :: ( a -> b -> a ) -> a -> [ b ] -> a

• així:– foldl f ul [e1, e2 , e3] foldl f

(f ul e1) [e2, e3] foldl f (f (f ul e1) e2) [e3]foldl f (f (f (f ul e1) e2) e3) [ ]

f (f (f (f ul e1) e2) e3)

• Per restar una llista com ho farieu:foldr o foldl?

Funcions d’ordre superior (vii)• Funció de recursió típica until:

– until p f x | p x = x| otherwise = until p f ( f x )

• Ordenació per inserció:– inserta x [ ] = [x]

inserta x (y:ys) | x<=y = x:( y: ys)|otherwise = y:(inserta x

ys)– ordena ll = foldr inserta [ ] ll

Funcions d’ordre superior (viii)• Ordenació per unió de llistes ordenades:

– merge [ ] ys = ys merge xs [ ]= xs merge (x:xs) (y:ys)

| x<=y = x:( merge xs (y:ys))|otherwise = y:( merge (x:xs) ys)

– mergest xs | mig <= 1 = xs | otherwise = merge (mergest pr)(mergest sc)

where pr = take mig xssc = drop mig xs

mig = tamany / 2tamany = length xs

Nous tipus de dades (i).• Renombrament de tipus:

– type Empleat = ( [Char], Int, Bool ) (“pep”, 25, True)

• Per a definir nous tipus de dades, necessitem donar-ne els constructors: – data Arbre a = Arrela a (Arbre a) (Arbre a)

| Abuit Arrela 1 (Arrela 2 Abuit Abuit) (Arrela 3 Abuit Abuit)

– data Direccio = Nord | Sud | Est | Oest– data Empleat = Empleat ( [Char], Int, Bool )

Nous tipus de dades (ii).

• Podem usar patrons per a definir funcions sobre aquests nous tipus de dades:– dim :: Arbre a -> Int

dim Abuit = 0dim Arrela n a1 a2 = 1 + (dim a1) + (dim a2)

• Una definició curiosa…– data EntOCar = Enter Int

| Car Char[ Enter 2, Enter 1, Car ‘a’, Enter 3,

Car ‘5’ ]

Exemplets

• Fer la funció primers mitjançant llistes per comprehensió i la criba d’Eratostenes.

• Fer el tipus arbre i definir els recorreguts: preordre, postordre i inordre.

• Fer la funció factoritzar; utilitzeu la funció primers.– primers = criba [2..] criba

(p:res) = p:(criba [r|r<-res, r `rem` p /=0])

Polimorfia i classes de tipus (i)

• L’operador + es pot aplicar a Int i a Float, però per exemple no es pot aplicar a Bool. No és polimòrfic, no té tipus:– (+) :: a-> a-> a

• És sobrecarregat:– (+) :: Num a => a-> a-> a– és a dir, + te tipus a-> a-> a si a és un tipus de

la classe Num.

Polimorfia i classes de tipus (ii)

• Per a sobrecarregar funcions es fan servir les classes de tipus: un grup de tipus amb característiques amb comú, p. ex. :– Num: és la classe dels tipus que tenen elements que es

poden sumar, multiplicar, restar i dividir.

– Ord: és la classe dels tipus que tenen elements que es poden ordenar.

• (<) :: Ord a => a -> a-> Bool

– Eq: és la classe dels tipus que tenen elements que es poden comparar.

Polimorfia i classes de tipus (iii)

• Podem sobrecarregar funcions nosaltres:– quadrat :: Num a => a -> a -> a

quadrat x = x * x

• Les classes que utilitzarem estan definides a Prelude.hs, p. ex.:– class Eq a where

(==), (/=) :: a->a->Bool x /= y = not (x == y)

Polimorfia i classes de tipus (iv)

• Moltes de les funcions predefinides, ho estan sota restriccions de classes de tipus:– elem :: (Eq a) => a -> [a] -> Bool

• Per tant per poder preguntar si un enter és a una llista, al Prelude.hs es fa que els enters siguin de la classe Eq.:– Instance Eq Int where

(==) = primEqInt

Polimorfia i classes de tipus (v)

• Per a poder saber si un arbre és a una llista d’arbres ens cal:– instance Eq Arbreint where Abuit

== Abuit = True Arrela n1 e1 d1 == Arrela n2 e2 d2 = (n1==n2)&&(e1==e2)&&(d1==d2) _ == _ = False

• També es poden posar condicions en les instanciacions:– instance (Eq a) => Eq (Arbre a) where ...

Uns exemplets (1)• Criba d’Eratóstenes

– primers = criba [2..] criba (pr:res) = pr:criba [r | r<-res, r `rem` pr /= 0]

• Donada una llista no-decreixent, dir quants elements diferents hi ha. (fer servir que està ordenada)– ndec [ ] = 0 ndec

[x] = 1 ndec (x:y:rll)= 1+ ndec (dropWhile (x==) (y:rll))

• Invertir paràmetres amb flip:– flip map [1,2,3] (+1)

Uns exemplets (2)• Exemple d’elem a Prelude.hs:

– and, or :: [Bool] -> Bool and = foldr (&&) True or = foldr (||) False

– any, all :: (a -> Bool) -> [a] -> Bool any p = or . map p --or ( map p l) all p = and . map p

– elem, notElem :: Eq a => a -> [a] -> Boolelem = any . (==)notElem = all . (/=) -- any.(==) e l --> any (e==) l

E/S (i)• Les operacions d’entrada/sortida no es poden

considerar funcions, doncs to “tornen” sempre el mateix:– la funció de llegir torna una cosa o una altra en funció

del que un introdueixi…

• El que fan es modificar el “mon real”, “gastant” part de l’entrada o “actualitzant” la sortida.

• Degut a aquesta naturalesa diferent, tractarem aquestes operacions com a accions dins un marc seqüencial d’accions, la Mónada IO.

E/S (ii)• Per a seqüencializar les accions usarem l’estructura do

així el clàssic HelloWorld:main = do

putStrLn “Com et dius?”nom <- getLineputStrLn (“Hola” ++ nom)

on:• getLine :: IO String és l’acció que llegeix l’entrada (per defecte

del teclat)• putStrLn :: String -> IO () donat un String, el mostra per la

sortida (per defecte la pantalla)• i nom <- getLine significa, fes l’acció getLine i

“guarda’n” el resultat a nom

E/S (iii)• Com que l’entrada sempre és d’Strings, per capturar

números els hem de “parsejar” (el let no necessita l’ in):

import Randommain = do

putStrLn "Com et dius?"nom<-getLineputStrLn ("Hola " ++ nom ++", dona'm un número:" )numero <- getLinelet num = read numerora <- randomRIO (1::Int,num)putStrLn ("Un número a l'atzar entre 1 i " ++ show (**)

num ++ " es: "++ show ra)

E/S (iv)…doGuessing ra (**)

doGuessing x = doputStrLn “Adivina:"guess <- getLinelet guessNum = read guessif guessNum < x

then do putStrLn “Massa Baix!"doGuessing x

else if read guess > xthen do putStrLn “Massa Alt!"

doGuessing xelse do putStrLn “Siii!”

E/S (v)

• Podeu trobar moltes més operacions per a gestionar l’entrada sortida al mòdul IO. Com per exemple:

…putChar :: Char -> IO ()putStr :: String -> IO ()putStrLn :: String -> IO ()readFile :: FilePath -> IO StringwriteFile :: FilePath -> String -> IO ()…