Jacek Cichoń

Katedra Podstaw Informatyki ● WIT ● PWr
Strona główna Moje zajęcia

2024/25 (lato): Programowanie Funkcyjne

Wykład przeznaczony jest dla studentów I roku I stopnia Informatyki Algorytmicznej. Odbywa się we wtorki w godz. - w sali 0.32 w budynku C-13.
Na stronie tej znajdziesz informacje o zasadach zaliczenia, literaturze, realizowanym materiale oraz listę zadań.

Literatura

Zasady zaliczania kursu

Na laboratoriach będziecie oceniani za aktywność. Rozwiązania zadań będą oceniane w skali 0-2 pkt (w zależości od stopnia trudności, ustalonego przez prowadzącego). Do zdobycia będzie 20 pkt.
Pod koniec maja będą ogłoszone tematy kilku projektów do wyboru. Będziecie mogli je ralizować samodzielnie lub w dwuosobowych grupach. Za realizację projektu będzie można dostać do 10 pkt.
Ocena dostateczna będzie od 10 punktów.
$ \def\RR{\mathbb{R}} \def\QQ{\mathbb{Q}} \def\ZZ{\mathbb{Z}} \def\CC{\mathbb{C}} \def\NN{\mathbb{N}} \def\IFF{\leftrightarrow} \newcommand{\span}[1]{\mathrm{span}(#1)} \newcommand{\IS}[2]{\langle\,#1,#2\rangle} \newcommand{\sgn}[1]{\mathrm{sgn}(#1)} $

Zagadnienia omówione na wykładzie

W1 (04.03.2025): GHCI i funkcje

Podstawowe polecenie ghci:
  • :q = wyjście
  • :t = typ
  • :i = info
  • :l = załadowanie modułu
Część kodów, które pojawiły się na tablicy.
module W1 where

-- funkcja jednej zmiennej
f x = 1 + x*(x+1)

g::Num a => a -> a -> a
g x y = 1 + x*y

-- Silnia : IF ... ELSE ...
fact1 :: Integer -> Integer
fact1 n = if n==0 then 1
          else n * fact1 (n-1)

-- Silnia : pattern matching          
fact2 :: Integer -> Integer
fact2 0 = 1
fact2 n = n * fact2 (n - 1)

-- Silnia : case expresion
fact3 n = case n of 
  0 -> 1
  n -> n * fact3 (n-1)

-- Silnia : with let expression  
fact4 :: Integer -> Integer
fact4 n  = let y = fact4 (n-1) in
           if n==0 then 1 else n * y

Ważna sprawa: zrozumienie pojęcia currying i uncurrying.

W2 (11.03.2025): Podstawowe typy

Podstawowe konstruktory typów
  • (a,b) :pary elementów typu a i b
  • [a] : ciągi elementów typu a; podstawowe funkcje (:) oraz (++)
Część kodów, które pojawiły się na tablicy.
{-
  modul: W2.hs
  info: Wykład z FP 2024/25 lato
  author: Jacek Cichoń
  date: 11.03.2025
-}

module W02 where
{- PARY -}

fst' (x,_) = x
snd' (_,y) = y

coll n | n == 1    = 1
       | even n    = coll (div n 2)
       | otherwise = coll (3*n+1)
 
collatz :: (Int,Int) -> (Int,Int)
collatz (n,s) | n==1      = (1,s)
              | even n    = collatz (div n 2,s+1)
              | otherwise = collatz (3*n+1,s+1)
lCollatz n = snd (collatz (n,0))

{- LISTY -}
length' []     = 0
length' (x:xs) = 1 + length' xs

head' [] = error "head: pusta lista"
head' (x:xs) = x

tail' [] =[]
tail' (x:xs) = xs

map' f [] = []
map' f (x:xs) = f x : map f xs

filter' p [] = []
filter' p (x:xs) = if p x then x:(filter' p xs) 
                          else filter' p xs
-- Lists comprehension

pythagorean n = [(x,y,z)| z<- [1..n],y<-[1..z], x<-[1..y], gcd x y == 1, x^2 + y^2 == z^2]

Uwagi:
  • Typ a->a jest intepretowany jako $(\lambda a: \mathrm{Type} \to (a\to a))$
  • Dummy variable : _
  • Aplikacja funkcji do zmiennej ma największy priorytet
  • Notacja infixowa: polecenie gcd x ymożna zapisać jako x `gcd` y
  • Wyrażenia listowe (list comprehension) są kosztowne.

W3 (18.03.2025): Sortowania; zip'y; foldy

Kody z wykładu:
module W03 where

import Data.List

{- SORTOWANIA -}
-- qS : lipna wersja
qS [] = []
qS (x:xs) = (qS [y| y<- xs, y<x]) ++
            [x] ++
            (qS [y| y<- xs, y>=x])
            
-- partition
{- komentuje, bo jest w Data.List
partition :: (a->Bool) -> [a] ->([a],[a])
partition _ [] = ([],[])
partition p (x:xs) = if p x then (x:l,r)
                            else (l,x:r)
                     where (l,r) = partition p xs
-}

-- sections 
p3 = (+ 3)
m4 = (4 *)

-- qSort
qSort []     = []
qSort [x]    = [x]
qSort (x:xs) = (qSort l) ++ [x] ++ (qSort r)
               where (l,r) = partition (<x) xs 
-- inSort

inSort [] = []
inSort [x] = [x]
inSort (x:xs) = left ++ [x] ++ right
                where sxs = inSort xs
                      (left,right) = partition (<x) sxs

{- ZIPY -}
-- uzywam ' bo zip i zipWith są w Prelude
zip' [] _ = []
zip' _ [] = []
zip' (x:xs) (y:ys) = (x,y): (zip' xs ys)

zipWith' _ [] _ = [] 
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = (f x y): zipWith' f xs ys

-- zagadka 
addMat = zipWith (zipWith (+)) 

{-- FOLDY --}
-- uzywam myfold* bo foldy sa w Prelude
add [] = 0
add (x:xs) = x + add xs

prod [] = 1
prod (x:xs) = x * prod xs

myfoldr f e [] = e
myfoldr f e (x:xs) = f x (myfoldr f e xs)

myfoldl f e [] = e
myfoldl f e (x:xs) = foldl f (f e x) xs

-- reverse jest Data.List, flip jest w Prelude
myreverse :: [a] -> [a]
myreverse  = foldl (flip (:)) []

W4 (25.03.2025): Foldy, strumienie, wstęp do typów

Zastosowania foldów i strumienie

module W04a where

import Data.List

sum'       xs  = foldl (+) 0 xs
product'   xs  = foldl (*) 1 xs 
minimum'   xs  = foldl1 min xs

-- fold1 f (x:xs) = foldl f x xs
and'       xs  = foldl (&&) True xs
or'        xs  = foldl (||) False xs
concat'    xxs = foldl (++) [] xxs
concatMap' f   = foldl ((++).f) []

{-- Automaty skonczone --}

-- AUTOMAT DETERMINISTYCZNY 
runDFA :: (s -> c -> s) -> s -> [c] -> s
--runDFA delta start cs = foldl delta start cs
runDFA = foldl

acceptDFA :: (s -> c -> s) -> s -> (s -> Bool) -> [c] -> Bool
acceptDFA delta start accept cs = accept (runDFA delta start cs)
 
-- przyklad: parzysta liczba jedynek

delta 1 '1' = 2
delta 1 _   = 1
delta 2 '1' = 1
delta 2 _   = 2
delta _ _   = 1  

-- AUTOMAT NIEDETRMINISTYCZNY 
-- procedure przekonwertowania automatu niedeterministyczngo
-- na automat deterministyczny
convertDelta :: (Eq s)=>(s->c->[s]) -> ([s]->c->[s]) 
convertDelta delta ss c  = nub (concat(map (\s -> delta s c) ss))
        
runNFA :: (Eq s) => (s->c->[s]) -> s -> [c] -> [s]
runNFA delta start cs = 
  runDFA deltaS [start] cs 
  where deltaS = convertDelta delta

convertAcc :: (s->Bool) -> ([s]->Bool)
convertAcc acc ss = or (map acc ss)

acceptNFA :: (Eq s) => (s->c->[s]) -> s -> (s->Bool) -> [c]->Bool
acceptNFA delta start acc cs = 
  accS (runNFA delta start cs)
  where accS = convertAcc acc
   
-- ciagi konczace sie jedynka
rho :: Int -> Char ->[Int]
rho 1 '1' = [1,2]
rho 1  _  = [1]
rho 2 '1' = [2]
rho 2   _ = [1]
           
{-- "Infinite streams" --}

myrepeat x = x:myrepeat x

myrepeat' x = xs where xs = x : xs

cycle' []  = error "cycle: emptyList"
cycle' xs  = xs' where xs' = xs ++ xs'

iterate' :: (a -> a) -> a -> [a]
iterate' f x =  x : iterate f (f x)

approSqrt:: Double->[Double]
approSqrt a = iterate (\x->(x+a/x)/2) a

-- liczby fibonacciego
fibb = 0:1: zipWith (+) fibb (tail fibb)

-- liczby pierwsze
sieve (p:xs) = p : sieve (filter (\n -> mod n p /= 0) xs)
primes = sieve [2..]

better_sieve (p:xs) = p: sieve (filter(\n -> n<p*p ||(mod n p /= 0)) xs)

addGF xs ys = zipWith (+) xs ys

Konstrukcja "type"

module Fizyka(Point,Vector,Time,
              move, translate, moveInGF) where

type Point = (Double,Double)
type Vector = (Double,Double)
type Time = Double

constG = 9.80655

-- lokalna funkcje
generalMove :: Point -> Vector -> Time -> Double -> Point
generalMove (x,y) (vx,vy) t acc = (x+vx*t, y + vy*t + acc*t*t/2)

-- upublicznione 
move :: Point -> Vector -> Time -> Point
move p v t = generalMove p v t 0 

translate :: Point -> Vector -> Point
translate p v = generalMove p v 1 0

moveInGF :: Point -> Vector -> Time -> Point
moveInGF p v t = generalMove p v t (-constG)

Konstrukcja "data" - wstęp

module W04b where

{-- Typy numerowane --}
data DOW = Po|Wt|Sr|Cz|Pi|So|Ni deriving (Eq,Ord,Enum,Bounded)

instance Show DOW where
  show Po = "Poniedziałek"
  show Wt = "Wtorek"
  show Sr = "Środa"
  show Cz = "Czwartek"
  show Pi = "Piatek"
  show So = "Sobota"
  show Ni = "Niedziela"

dniPracujace = [Po .. Pi] -- efekt Enum

Proponuję rzucić okiem na następującą stronę: The Evolution of a Haskell Programmer, na której Fritz Ruehr'er wygłupia się z różnymi sposobami zdefiniowania funkcji silnia.

W5 (01.04.2025): Typy, wstęp do funktorów

Zastosowania foldów i strumienie

module W5b where

-- prototyp
data Osoba' = Osoba' String String String Int Int Int

imie' :: Osoba' -> String
imie' (Osoba' _ x _ _ _ _) = x
-- itd 

{-- RECORD SYNTAX --}

data Osoba = Osoba
     {
      idO :: String
     ,imie :: String
     ,nazwisko :: String
     ,rokUr :: Int
     ,miesiacUr :: Int
     ,dzienUr :: Int
     } deriving (Show,Eq)
  
aaa = Osoba "001" "Anna" "Nowicka" 2005 5 12

bbb = Osoba{idO = "002", 
            imie = "Jan", 
            nazwisko="Balicki", 
            rokUr=2004, miesiacUr = 10, dzienUr = 12}

-- lekkie ulepszenie   

data Date = Date{rok::Int,miesiac::Int,dzien::Int} 
     deriving(Eq)
     
instance Show Date where
  show (Date r m d) = 
    (show r) ++"."++(show m)++"."++(show d)
  
data Person = Person
     {
      _idO :: String
     ,_imie :: String
     ,_nazwisko :: String
     , dataUr :: Date
     } deriving (Show,Eq)
  
ccc = Person "001" "Anna" "Balicka" (Date 2005 5 12)

zmienDate :: Person -> Date -> Person
zmienDate osoba nowaData = 
  osoba{dataUr = nowaData}

zmienRokUr :: Person ->Int -> Person
zmienRokUr osoba rokUr = 
  let urodziny  = dataUr osoba 
      urodziny' = urodziny{rok = rokUr} in 
   osoba{dataUr = urodziny'}

-- to samo - inny zapis
zmienRokUr' osoba rokUr = 
  osoba{dataUr = (dataUr osoba){rok = rokUr}}

--- Pozniej: lenses 

{-- TYPY PARAMETRYZOWALNE --}

-- MODEL KATEGORYJNY: PP (X) = X x X

data Para a = Para (a,a) deriving (Show,Eq)

-- MODEL :: jesli f:X->Y to (fmap f):(X x X) -> (Y x Y)

instance Functor Para  where
  fmap f (Para (x,y)) = Para (f x, f y)

--pmap :: (a->b) -> Para a -> Para b
--pmap f (Para (x,y)) = Para (f x, f y)

f x = 3.5 * x*(1-x)
-- uzycie: fmap f Para(0.25,0.75)
                  
{-- FUNKTOR MAYBE --}

-- data Maybe a = Nothing |  Just a
-- MODEL: MB(X) = ({0} x {*}) u ({1} x X) 
-- fmap f Nothing = Nothing
-- fmap f (Just x) = Just (f x)

safeHead []    = Nothing
safeHead (x:_) = Just x

safeSqrt x 
  | x>=0      = Just (sqrt x)
  | otherwise = Nothing 

safeLog  x 
  | x>0  = Just (log x)
  | otherwise = Nothing

safeDiv x 0 = Nothing 
safeDiv x y = Just (x/y)

-- zaczynamy partyzantkę;
-- pozniej zrobimy to lepiej

-- sqrt(log x)
composeMB :: (a-> Maybe b) -> (b -> Maybe c) -> (a -> Maybe c)
composeMB f g x =
  case f x of 
   Nothing -> Nothing
   Just y  -> g y
 
expr1 = composeMB safeLog safeSqrt

-- (sqrt x)/log(x +1)
composeMB2 :: (a->b->Maybe c) -> Maybe a -> Maybe b -> Maybe c
composeMB2 _ Nothing _  = Nothing
composeMB2 _ _ Nothing  = Nothing
composeMB2 op (Just x) (Just y) = op x y             

expr2 x = let sn = safeSqrt x
              sd = safeLog (x^2-4) in
          composeMB2 safeDiv sn sd

Oto skompresowany plik W5_BD.zip, z plikami którymi bawiliśmy się na wykładzie.

Strona główna Moje zajęcia