LP 2017-10-16

p0.md

Tipus

Int

Enters 32/64 bits amb complement a 2.

Exemples: 0, 3, 28, (- 55).

Operacions:

• +
• -
• *
• div
• mod
• ==, /=, <, <=, >, >=

Integer

Com els Int però amb llargada ilimitada.

Float

Reals amb coma flotant.

Exemples: 2.0, 4.45e2.

Operacions:

• +
• -
• *
• /
• ==, /=, <, <=, >, >=

Bool

Booleans.

Valors: False, True.

Operacions:

• not
• &&
• ||

Char

Caràcters

Exemples: 'a', 'A', `'\n``.

Tuples

Permetem agregar diferents tipus.

Exemples (3, 5), ('a', True, "Jordi")

Operacions:

• fst
• snd

Llistes

Son seqüències homogenees d'elements.

Exemples: [], [3, 2, 8], [1..10], [1,3..10].

Constructors:  - Llista buida:  []  - Cons:  : (posa un element davant d'una llista)

Operacions:  - null  - head  - tail  - init  - last  - ++ (concatenació)  

String

Els textos són llistes de caràcters.

Exemples: "Jordi", "".

p1.hs

-- amb definicions

factorial :: Integer -> Integer

factorial 0 = 1
factorial n = n * factorial (n-1)


-- amb guardes (més lleig):

factorial :: Integer -> Integer

factorial n
    | n == 0    = 1
    | otherwise = n * factorial (n-1)


-- amb if-then-else (més lleig):

factorial :: Integer -> Integer

factorial n = if n == 0 then 1 else n * factorial (n-1)

p2.hs

-- lineal, cost O(n)

potencia :: Integer -> Integer -> Integer

potencia x 0 = 1
potencia x n = x * potencia (n-1)

-- exponenciació ràpida, cost O(log n)

potencia :: Integer -> Integer -> Integer

potencia x n 
    | n == 0        = 1
    | even n        = y * y
    | otherwise     = y * y * x
    where
        y = potencia x (div n 2)

p3.hs

-- algorisme exponencial

fibonacci :: Integer -> Integer

fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibonacci (n-1) + fibonacci (n-2)


-- algorisme lineal

fibonacci :: Integer -> Integer

fibonacci n = fst (fibonacci' n)

fibonacci' :: Integer -> (Integer, Integer)
    -- retorna (F(n),F(n+1))

fibonacci' 0 = (0, 1)
fibonacci' 1 = (1, 1)
fibonacci' n = (seg, seg + res)
    where (res, seg) = fibonacci' (n-1)


-- amagant la funció auxiliar

fibonacci :: Integer -> Integer

fibonacci n = fst (fibonacci' n)
    where
        fibonacci' 0 = (0, 1)
        fibonacci' 1 = (1, 1)
        fibonacci' n = (seg, seg + res)
            where (res, seg) = fibonacci' (n-1)

p4.hs

-- llargada d'un text

llargada :: [Char] -> Int

llargada [] = 0
llargada (x:xs) = 1 + llargada xs


-- llargada d'un text amb variable anònima

llargada :: [Char] -> Int

llargada [] = 0
llargada (_:xs) = 1 + llargada xs


-- llargada d'una llista genèrica

llargada :: [a] -> Int

llargada [] = 0
llargada (_:xs) = 1 + llargada xs

p5.hs

maxim :: [a] -> Int
maxim [x] = x
maxim (x:xs) 
    | x > m     = x
    | otherwise = m
    where m = maxim xs

p6.hs

isPrime :: Int -> Bool

isPrime 0 = False
isPrime 1 = False
isPrime n = not (hasDivisors n 2)

hasDivisors :: Int -> Int -> Bool
hasDivisors n c 
    | c * c > n     = False
    | mod n c == 0  = True
    | otherwise     = hasDivisors n (c + 1)


-- amagant la funció auxiliar i eliminant el seu primer paràmetre    

isPrime :: Int -> Bool

isPrime 0 = False
isPrime 1 = False
isPrime n = not (hasDivisors 2)
    where
        hasDivisors :: Int -> Bool
        hasDivisors c 
            | c * c > n     = False
            | mod n c == 0  = True
            | otherwise     = hasDivisors (c + 1)

p7.hs

-- ordena una llista (sense repetits)

-- El (Ord a) serveix per dir que el tipus a ha de tenir suport per ordenar
-- parelles d'elements. Ho podeu ignorar per ara (treient la capçalera, per exemple).

qsort :: (Ord a) => [a] -> [a]

qsort [] = []
qsort [x] = [x]
qsort (x:xs) = qsort lt ++ [x] ++ qsort gt
    where
        lt = filtra (< x) xs
        gt = filtra (> x) xs


filtra :: (a -> Bool) -> [a] -> [a]

filtra _ [] = []
filtra p (x:xs) 
    | p x       = x : filtra p xs
    | otherwise =     filtra p xs

-- (filtra ja és una funció estàndard que es diu filter.)