Zadanie 1 (4p.)

• wyrażenia arytmetyczne: a := n | x | plus a a | mult a a
• wyrażenia logiczne: b := tt | ff | and b b | or b b | not b | equal a a
• instrukcje: c := assign x a | skip | seq c c | if b then c else c | for x from a to a do c | while b do c

1. zdefiniuj typy danych: aexp dla wyrażeń arytmetycznych, bexp dla wyrażeń logicznych i cmd dla instrukcji
2. zdefiniuj typ zmiennych jako string: type var = string
3. niech mem będzie typem stanów pamięci; interpreter może odwoływać się do pamięci wyłącznie za pomocą funkcji lookup : mem -> var -> int (do wyszukiwania wartości zmiennej w pamięci) oraz update : mem -> var -> int -> mem (do zmiany wartości zmiennej w pamięci)
4. zaimplementuj powyższe funkcje dostępu do pamięci przyjmując mem = var -> int (pamięć jest funkcją przyporządkowującą zmiennym ich wartości) oraz zdefiniuj pustą pamięć empty_mem : mem jako funkcję rzucającą wyjątek dla dowolnego argumentu
5. napisz funkcję aeval ewaluacji wyrażeń arytmetycznych
6. napisz funkcję beval ewaluacji wyrażeń logicznych
7. napisz funkcję exec interpretującą instrukcje według semantyki podanej poniżej
8. napisz funkcję run interpretującą program
9. po zrealizowaniu powyższych punktów napisz w języku IMP program obliczania silni i przetestuj na nim swój interpreter

Zadanie 2 (8p.)

  type term = 
      Var of string 
    | Abs of string * term 
    | App of term * term 

Zadanie 1 (4p.)

type 'a btree = Leaf of 'a | Node of 'a btree * 'a btree

Node (Node (Leaf 1, Leaf 2), Leaf 3)

Node (Leaf 1, Node (Leaf 2, Leaf 3))

1. (1p.) Napisz funkcję rozstrzygającą czy dwa drzewa mają jednakowe korony, bazując bezpośrednio na definicji i nie dbając o efektywność rozwiązania.
2. (3p.) Wykorzystując pojęcie odroczonego obliczenia, napisz efektywną i czysto funkcyjną wersję funkcji samefringe, tj. taką, która przerywa obliczenia w momencie napotkania pierwszej różnicy między koronami drzew. Podpowiedź: należy odraczać trawersowanie prawego poddrzewa.

Zadanie 2 (4p.)

Zadanie 3 (6p.)

  type regexp = 
  | Atom of char
  | And of regexp * regexp  (*  r1r2     *)
  | Or of regexp * regexp   (*  r1 | r2  *)
  | Star of regexp          (*  r*  *)

  match_regexp : regexp -> char list -> (char list -> (unit -> 'a) -> 'a) -> (unit -> 'a) -> 'a

  run : regexp -> char list -> bool

Zadanie 1 (5p.)

Zadanie 2 (2p.)

  type 'a list_mutable = LMnil | LMcons of 'a * 'a list_mutable ref

1. funkcja concat_copy buduje listę wynikową kopiując pierwszy argument;
2. funkcja concat_share buduje listę wynikową bez kopiowania argumentów.

Zadanie 3 (4p.)

• zdefiniuj typ polimorficzny ('a, 'b) memo służący jako tablica wartości wywołań dowolnej funkcji
• napisz funkcję tworzenia pustej tablicy create_memo : unit -> ('a, 'b) memo
• napisz funkcję wyszukiwania w tablicy wartości funkcji dla zadanego argumentu memo_find : ('a, 'b) memo -> 'a -> 'b option
• napisz funkcję dopisującą do tablicy nową wartość wywołania funkcji memo_add : ('a, 'b) memo -> 'a -> 'b -> unit
• napisz funkcję memo_f : ('a -> 'b) -> 'a -> 'b, która dla zadanej jako argument funkcji f : 'a -> 'b zwraca funkcję, która działa tak samo jak f, ale wykorzystuje tablicę memoizacji, więc jest potencjalnie bardziej efektywna

Zadanie 4 (4p.)

module type PQUEUE =
sig

  type priority
  type 'a t
  
  exception EmptyPQueue
  
  val empty : 'a t
  val insert : 'a t -> priority -> 'a -> 'a t
  val remove : 'a t -> priority * 'a * 'a t
    
end

1. (1p.) Zdefiniuj moduł PQueue : PQUEUE, przyjmując typ priority = int. Reprezentacja kolejki może być dowolna.
2. (1p.) Wykorzystaj moduł PQueue do napisania funkcji sortowania list liczb typu int.
3. (2p.) Uogólnij rozwiązanie punktów 1 i 2 definiując funktor, który dla zadanego modułu OrdType : ORDTYPE zwraca moduł o sygnaturze PQUEUE, gdzie

   module type ORDTYPE =
   sig
     type t
     val compare : t -> t -> int
   end
   

   Zmodyfikuj odpowiednio funkcję sortowania list z p. 2 i przetestuj ją.

Zadanie 1 (2p.)

# next();;
- : int = 1
# next();;
- : int = 2
# next();;
- : int = 6
# next();;
- : int = 24

# next();;
- : int = 120
# reset();;
- : unit = ()
# next();;
- : int = 1
# next();;
- : int = 2

Zadanie 2 (4p.)

	type 'a computation = 
	| Value of 'a
	| Delayed of (unit -> 'a)

	type 'a comp = 'a computation ref
      

	let compute c =
	match !c with 
	| Value a -> a
	| Delayed t -> let a = t() in c := Value a; a
      

type 'a stream = Cons of 'a * 'a stream computation ref

• map : ('a -> 'b) -> 'a stream -> 'b stream
• take : int -> 'a stream -> 'a list

• ones złożony z samych jedynek,
• oraz nats złożony z kolejnych liczb naturalnych.

Zadanie 3 (4p.)

type 'a btree = Leaf of 'a | Node of 'a btree * 'a * 'a btree

1. Napisz funkcję numerującą węzły i liście drzewa binarnego w kolejności przechodzenia go w głąb (preorder). Na przykład, tak ponumerowaną wersją drzewa

   Node (Node (Leaf 'a', 'b', Leaf 'c'), 'd', Leaf 'e')

   jest

   Node (Node (Leaf 3, 2, Leaf 4), 1, Leaf 5).

2. Napisz funkcję numerującą węzły i liście drzewa binarnego w kolejności przechodzenia go wszerz. Na przykład, tak ponumerowaną wersją drzewa

   Node (Node (Leaf 'a', 'b', Leaf 'c'), 'd', Leaf 'e')

   jest

   Node (Node (Leaf 4, 2, Leaf 5), 1, Leaf 3).

Zadanie 4 (4p.)

Zadanie 1 (2p.)

1. Zdefiniuj funkcję generującą nieskończony strumień o okresie zadanym jako zwykła lista skończona, np. dla okresu [0;1] ma powstać strumień o elementach 0,1,0,1,...
2. Zdefiniuj funkcję, która dla zadanej listy leniwej ll generuje listę leniwą, w której element stojący na i-tym miejscu w liście ll jest powtórzony i razy, np. dla listy leniwej o elementach 1,2,3,4, powinna powstać lista o elementach 1,2,2,3,3,3,4,4,4,4.

Zadanie 2 (4p.)

1. Zdefiniuj strumień obliczający wartość liczby pi z rosnącą dokładnością, korzystając ze wzoru Leibniza: π/4 = 1 - 1/3 + 1/5 - 1/7 + ...
2. Napisz funkcję przekształcającą dowolny strumień x₁,x₂,x₃,... w strumień postaci f x₁ x₂ x₃, f x₂ x₃ x₄, f x₃ x₄ x₅,..., dla dowolnej funkcji f.
3. Korzystając z powyższych definicji i transformacji Eulera:
   F x y z = z - (y-z)²/(x-2y+z)
   utwórz nowy strumień, szybciej zdążający do liczby π.
4. Znajdź inny wzór przybliżający liczbę π, zdefiniuj odpowiedni strumień i porównaj z wcześniej zdefiniowanymi strumieniami.

Zadanie 3 (4p.)

Zadanie 4 (2p.)

Zadanie 1 (2p.)

Zadanie 2 (4p.)

1. [1p.] Napisz funkcję, która dla zadanej listy etykiet tworzy zbalansowane drzewo, dla którego tę listę można otrzymać przechodząc je w porządku preorder.
2. [1p.] Napisz funkcję, która dla zadanej listy etykiet tworzy zbalansowane drzewo, dla którego tę listę można otrzymać przechodząc je w porządku inorder.
3. [2p.] Napisz funkcję, która dla zadanej listy etykiet konstruuje wszystkie drzewa, których przejście w porządku preorder daje tę listę.

Zadanie 3 (6p., dla chętnych)

Zadanie 4 (6p.)

• Napisz (pierwszą) funkcję sprawdzającą, czy dana formuła jest tautologią. W tym celu należy generować kolejne wartościowania zmiennych zdaniowych występujących w danej formule i sprawdzać dla nich wartość formuły. W przypadku, gdy formuła nie jest tautologią, funkcja powinna - oprócz tej informacji - podać jedno z wartościowań, dla których formuła nie jest prawdziwa.
• W podobny sposób napisz funkcje sprawdzające, czy formuła jest sprzeczna i czy jest spełnialna.
• Napisz funkcję, która przekształca zadaną formułę w formułę jej równoważną w koniunkcyjnej postaci normalnej.
• Napisz (drugą) funkcję sprawdzającą (czysto syntaktycznie!), czy zadana formuła jest tautologią, korzystając z faktu, że każdą formułę można przedstawić w koniunkcyjnej postaci normalnej.
• Napisz funkcję, która przekształca zadaną formułę w formułę jej równoważną w dyzjunkcyjnej postaci normalnej.
• Napisz (trzecią) funkcję sprawdzającą (czysto syntaktycznie!), czy zadana formuła jest sprzeczna, korzystając z faktu, że każdą formułę można przedstawić w dyzjunkcyjnej postaci normalnej.
• Zadbaj, by wyświetlanie formuł i wartościowań było czytelne - napisz odpowiednie funkcje konwersji i uźywaj ich do wyświetlania wyników.
• Przygotuj 5 różnych przykładów formuł (z 1,2,3 zmiennymi zdaniowymi) i przetestuj funkcje.

Zadanie 1 (5p.)

1. Napisz funkcję, która dla zadanej macierzy kwadratowej i liczby naturalnej n wyznacza n-tą kolumnę macierzy.
2. Napisz funkcję transpozycji macierzy; transpozycja macierzy l jest reprezentowana jako lista [[1.;4.;7.];[2.;5.;8.];[3.;6.;9.]].
3. Napisz funkcję zipf, która dla danych dwóch list typów 'a list i 'b list i funkcji dwuargumentowej f typu 'a -> 'b -> 'c tworzy listę złożoną z wartości funkcji f na argumentach z obu list położonych na tych samych pozycjach, np. zipf ( +. ) [1.;2.;3.] [4.;5.;6.] = [5.;7.;9.].
4. Wykorzystując funkcję zipf napisz funkcję mult_vec, która oblicza iloczyn zadanego wektora i zadanej macierzy, np. mult_vec [1.;2.] [[2.;0.];[4.;5.]] = [10.;10.].
5. Korzystając z funkcji mult_vec napisz funkcję mnożenia dwóch macierzy kwadratowych tego samego rozmiaru.

Zadanie 2 (2p.)

Zadanie 3 (3p.)

Zadanie 4 (3p.)

Zadanie 1 (2p.)

Zadanie 2 (2p.)

Zadanie 3 (2p.)

• a₀ = 1
• a₁ = 2
• a_n = 2 * a_n-2 - a_n-1 + 1 dla n>1

Zadanie 4 (3p.)

• Napisz funkcję merge, która łączy dwie listy posortowane rosnąco w pewnym porządku <= tak, by wynik działania funkcji był także listą posortowaną rosnąco w tym samym porządku. Argumentami funkcji merge powinny być: funkcja cmp typu 'a -> 'a -> bool (zakładamy, że cmp a b = true, gdy a<=b), i dwie listy elementów typu 'a.
  Przykład: merge (<=) [1;2;5] [3;4;5] utworzy listę [1;2;3;4;5;5].
• Zapisz tę funkcję używając rekursji ogonowej i skonstruuj przykład pokazujący różnicę w efektywności tych dwóch definicji.
• Wykorzystaj funkcję merge do napisania funkcji sortowania przez scalanie.

Zadanie 5 (3p.)

Zadanie 1 (0p.)

• Dla każdego z typów int, float, char, string, bool oraz unit napisz wyrażenie tego typu i wykorzystaj interpreter OCamla (program ocaml, z linii poleceń lub zintegrowany z emacsem) do obliczenia jego wartości.
• Skompiluj i wykonaj przykładowy program za pomocą kompilatorów ocamlc i ocamlopt (por. Ocaml Manual, Part III).

Zadanie 2 (0p.)

• if false then 1 else 3.5
• false || "ab">"cd"
• x = 5
• if true then ()
• let z = 3 and y = z + 4 in y * z
• let x = 2 in x ^ "aa"
• let y = "abc" in y ^ y
• (fun x -> x.[1]) "abcdef"
• (fun x -> x) true
• let x = [1;2] in x @ x
• let rec f f = f + f in f 42

Zadanie 3 (0p.)

• let x = x in x ^ x
• let x = 10. in let y = x ** 2. in y *. x
• let x = 1 and y = x in x + y
• let x = 1 in fun y z -> x * y * z

Zadanie 4 (0p.)

Zadanie 5 (3p.)

Zadanie 6 (3p.)

Zadanie 7 (6p.)

• hd, tl - funkcje zwracające odpowiednio głowę (pierwszy element) i ogon strumienia (strumień zaczynający się od drugiego elementu)
• add - funkcja dodawania zadanej stałej do każdego elementu strumienia i zwracająca powstały w ten sposób strumień
• map - funkcja, która dla zadanej operacji 1-argumentowej przetwarza elementy zadanego strumienia za pomocą tej operacji i zwraca powstały w ten sposób nowy strumień (tak, jak map na listach skończonych)
• map2 - jak wyżej, ale dla zadanych: funkcji 2-argumentowej i 2 strumieni
• replace - funkcja, która dla zadanego indeksu n, wartości a i strumienia s zastępuje co n-ty element strumienia s przez wartość a i zwraca powstały w ten sposób strumień
• take - funkcja, która dla zadanego indeksu n i strumienia s tworzy nowy strumień złożony z co n-tego elementu strumienia s
• fold - funkcja, która dla zadanej funkcji f:'a->'b->'a, wartości początkowej a:'a i strumienia s elementów typu 'b tworzy nowy strumień, którego każdy element jest wynikiem "zwinięcia" początkowego segmentu strumienia s aż do bieżącego elementu włącznie za pomocą funkcji f, tj. w strumieniu wynikowym element o indeksie n ma wartość (... (f (f a s_0) s_1)... s_n)
• tabulate - funkcja tablicowania strumienia, której wartością powinna być lista elementów strumienia leżąca w zadanym zakresie indeksów