let map przetwarzacz lista=
    match with lista
     | []->[]
     | hd::tl->przetwarzacz
let rec fold_right (operator : 'b'->"a"->'b')(zarodek: "b")(lista : "a list") =
    match with lista
     | []->zarodek
     | hd::tl ->  fold_right (operator)(operator(zarodek,hd))(tl)

let rec fold_left (operator : 'b'->"a"->'b')(zarodek: "b")(lista : "a list") =
    match with lista
     | []->zarodek
     | hd::tl -> operator (fold_left operator zarodek tl)hd

let odwroc_liste lista =
    fold_right (fun acc el -> el::acc) [] lista

module type STOS = sig
    type 'a kolejka;;
    val dodaj : 'a kolejka -> 'a ->
(* PRZYKLADY *)

let mnoz a b = a * b;;
let dwanascie = mnoz 4 3;;
(*robimy z infixowego operatora * funkcje *)
let mnoz2 a b = ( * ) a b;;
(* funckje sa dobrymi obiektami - mozna je zwracac, przypisywac itp. *)
let mnoz3 = ( * ) ;;
let mnoz4 a = ( * ) a;;
(* wszystkie mnoz robią dokładnie to samo *)


(* dane dwe liczby jako para, nie jako dwa argumenty *)
let mnoz4 (a,  b) = a * b;;

(* mozna opisac typ argumentow *)
let zloz (f : int -> bool) (g : char -> int) (x : char) = f (g x);;
(* ale mozna tez nie opiswyac i wyjdzie funkcja ogolniejsza *)
let zloz2 f g x = f (g x);;
(* i jeszcze wersja bardziej czytlena lecz calkowicie identyczna z powyzsza *)
let zloz3 f g = (fun x -> f (g x));;
(* mozna pominac nawias i samemu napisac ogolny typ *)
let zloz3 : 'a 'b 'c. ('b -> 'c) -> ('a -> 'b) -> ('a -> 'c) = fun  f g -> fun x -> f (g x);;

(*przyklad uzycia *)
let mnozPrzezTrzy n = 3*n;;
let dodawajJeden n = n+1;;
let trzPlusJeden n = zloz2 dodawajJeden mnozPrzezTrzy n;;
(* powyzsze nie zdziala ze zloz (zamiast zloz2) bo zloz na zly typ *)

(* tak dzialaja bool-e i if-y *)
let wiekszaNizZero n = (n > 0);;
let negacja (b : bool) =
  if b then
    false
  else
    true;;

(* funkcja rekurencyjna - liczby filbonacciego w czasie wykladniczym *)
(* zwrc uwage na slowko rec *)
let rec fib n =
  if n = 0 then 0 else
  if n = 1 then 1 else
   fib (n-1) + fib (n-2);;
(* zwroc uwage ze fib n-1 t oznaczalby (fib n)-1. *)
(* Funkcja na poczatku wyrazenia lyka argument jak leci - np. *)
(* mnozPrzezTrzy mnozPrzezTrzy 7 - sie nie otypuje bo pierwsze mnozPrzezTrzy wezmie drugie mnozPrzezTrzy za argument i nie zgodzi sie typ *)
(* trzeba pisac: *)
let dziwiec = mnozPrzezTrzy (mnozPrzezTrzy 1);;

(* mozna etykietwac rozne rzecy w srodku funckucji przez konstrukcje let a = ... in ... *)
(* mozna w ten sposob tworzyc funkcje pomocnicze *)
let mnozymyPrzezSidem n =
  let razyN t = t * n in
  let siedem = 7 in
  razyN siedem;;



(* ZADANIA *)
(* Napisz funckje ktora: *)


(* liczby liczby filbonacciego w czasie liniowym *)
let fib (n : int) =
  raise (Failure "foo");;

(* liczy maksymalna potege dwojki ktora dzili daną liczbę *)
let maksPotegaDwojki n =
  raise (Failure "foo");;
(* assert (maksPotegaDwojki 12 == 2) *)

(* poteguje binarnie modulo p *)
let poteguj a b p =
 raise (Failure "foo");;
(* assert (poteguj 2 3 3 == 2);; *)



(* odwraca zapis dziesietny danej liczby *)
let odrocZapis (n : int) =
  raise (Failure "foo");;
(* assert (odwrocZapis 1234 = 4321);; *)



(* dopiosuje jedynke na poczatku zapisu dziesitnego danej liczby *)
let dopiszJedne (n : int) =
  raise (Failure "foo");;
(* assert (dopiszJeden 45 == 145);; *)



(* LISTY *)
let l1 : int list = [1;24;3;7;8];;
let l2 : int list = 3::2::[];;
assert (l2 = [3;2]);;
let ogonekListy : 'a list = [];;

(*lista list *)
let l3 : int list list = [7;3;45]::[3;4]::[1;2]::[];;

(* aby uzyc list nalezy korzystac z konstrukcji match *)

let czyPusta l =
  match l with
  | [] -> "pusta"
  | glowa::ogon -> "nie pusta lsita o glowie"^(string_of_int glowa)
  | _ -> "to nigdy nie zajdzie bo przypadki sa sprawdzane z gory na dol - i kompilator slusznie pluje warningiem" (* podkreslnik zawsze lapie - oznacza on dowolny przypadek *)
;;

(* ZADANIA 2 *)


(* dostrales liste liczb. Policz ich sume *)
let sumuj lista =
raise (Failure "foo");;
(* assert (sumuj [1;2;3;4] = 10) *)

(* odwroc liste *)
let odwroc lista =
  raise (Failure "foo");;
(* assert (odroc [1;2;3;4] = [4;3;2;1]) *)

(* dostales dwie listy, przetasuj je za soba. Jesli jedna z nich podczas tasowanie sie skonczyla to wchodza kolejne elemntu drugiej *)
let tasuj l k =
  raise (Failure "foo");;
(* assert (tasuj [12;13;14;15;16] [23;24] = [12;23;13;24;14;15;16] *)

(* sklej diwe listy. Czas dzialanie ma byc proporcjonalny do dlugosci pierwszej listy *)
let sklej l1 l2 =
raise (Failure "foo");;
(* assert (sklej [1;2;3;4] [7;8;9] = [1;2;3;4;7;8;9]) *)

(* dana jest lista list. Sklej kolejne elementy ze sobą *)
(* Czy Twoj czas dzialania zalezy od dlugosci ostatniego elementu ?*)
let rozpakuj l =
raise (Failure "foo");;
(* assert (rozpakuj [[2;3];[4;5];[];[4;5;5;5;5;5]] = [2;3;4;5;4;5;5;5;5;5] ) *)


(* napisz funkcje ktra wyfiltruje z listy elementy spelniajace dany warunek *)
let filtruj (type a) (warunek : a -> bool) (lista : a list) =
raise (Failure "foo");;
(* assert ( filtruj (fun x -> (x mod 2) = 0) [1;2;3;4;5;6] = [2;4;6] ) *)


(* FUNKCJE WYŻSZYCH RZEDOW - ZADANIA *)

(* dostajesz przetwarzacz - funkcje f typu a' -> 'b - oraz liste elementow typu 'a. *)
(* twoim zadaniem jest zastosowac ptrzetwarzacz do wszystkich elementow na liscie i wyniki posklejac w liste *)
let map przetwarzacz lista =
raise (Failure "foo");;
(* assert ( przetwarzacz (fun x -> 2*x) [1;2;3] = [2;4;6] ) *)

(* zaimplementuj fold_left, fold_right. Który da się zrobić ogonowo? *)



(* ZABAWY Z TYPOWANIEM *)

(* zwykle typowanie polimorficzne *)
let idi : 'a. 'a -> 'a = fun x -> x;;
(* psuedo-jawny polimorfizm - czasami jest uzyteczny by opisac skomplikowany typ*)
let idi (type a) : a -> a = fun x -> x;;

let f0 = fun (id : 'a -> 'a) x -> id x;;
let d = f0 idi;;

let f1 : 'a. ('a -> 'a) -> int -> int = fun id x -> x;;
let f2 id (x : int) = x;;

open List;;

(* Zadanie 0: przy pomocy fold-a:
 - policzyć długość listy
 - odrócić listę *)

(* 'a option jest z biblioteki standardowej i działa tak:
type 'a option = None | Some of 'a *)


(*tak dziłają moduły w Ocaml-u *)
module type STOS = sig
  type 'a stos;;
  val dodaj : 'a stos -> 'a -> 'a stos
  val zdejmij : 'a stos -> 'a option * 'a stos
  val pusty : 'a stos
end;;

module Stos : STOS = struct
  type 'a stos = 'a list;;

  let dodaj stos element =
    element::stos;;

  let zdejmij stos =
    match stos with
    | [] -> (None, [])
    | hd::tl -> (Some hd, tl);;

  let pusty = [];;
end

let stosik = Stos.pusty;;
let stosik = Stos.dodaj stosik 5;;
let stosik = Stos.dodaj stosik 3;;
let (Some a, stosik) = Stos.zdejmij stosik;;


(* ZADANIE 1 - implementujemy kolejke*)


module type STOS = sig
  type 'a kolejka;;
  val dodaj : 'a kolejka -> 'a -> 'a kolejka
  val zdejmij : 'a kolejka -> 'a option * 'a kolejka
  val pusty : 'a kolejka
end;;

module Kolejka : Kolejka = struct
  type 'a kolejka = 'a list * 'a list

  let dodaj stos element =
    raise (Failure "foo")

  let zdejmij (lewa,prawa)=
    let(nlewa,nprawa) as kolejka=
    match nprawa with
    | [] -> ([],rev lewa)
    | - ->(lewa,prawa)
    in
    match nprawa with
    | [] -> (None,([],[]))
    | hd::tl ->(Some hd,(nlewa,tl))

  let pusty = ([], []);;
end


(* ZADANIE 3 implementujemy kolejke dwustronną *)

(* Zadania o drzewach *)

type 'a tree =
 | Nil
 | Node of 'a tree* 'a * 'a tree;;

let m = Node(Nil,4,Nil);;
let m2 = Node (m,4,Nil);;
let p = Node(Nil, 2, Nil);;
let cale= Node(m2,8,p);;

let mapuj_drzewo operator drzewo=
    match drzewo with
     | Nil -> Nil
     | Node(lewe,wezel,prawe)=Node(mapuj_drzewo operator lewe,wezel*2,mapuj_drzewo operator prawe)
let rec fold_tree (operator:'b'->'b'->'a'->'b')(zarodek:'b')(tree: "a list")
    match lista with
     | Nil -> zarodek
     | Node(lewe,wezel,prawe)->
        let fo=fold_tree operator zarodek in
        operator (fo lewe)(fo prawe) wezel;;

let dfs_wolny drzewo=
    fold_tree (fun lewe prawe wezel-> lewe@[wezel]@prawe)
let rec DFSfromTree(operator:'b list'->'b list'->'a'->'b list')(zarodek: "b list")(tree?? )
    match tree with
     | Nil -> zarodek
     | Node(lewe,wezel,prawe)->
        let l1 =wezel::(dfs2 prawe lista) in
        dfs2 lewa l1
let dfs drzewo=
    let rec loop

let najwieksze_fold drzewo=
    fold_tree(fun lewo prawo wezel ->max (max lewe prawe) wezel)

type 'a sklejLista = ' a list -> 'a list;;
let sklej dziwlista1 dziwlista2 =
    (fun ogon-> dziwlista1(dziwlista2 ogon));;

let iloscNieDominowanych drzewo =
    let rec loop drzewo
(* Wprowadzenie do drzew: typ, fold, przyklady *)

(* 4: wylistuj obiekty w drzewie w kolejności DFS *)
(* 5: ilosc takich liczb, ze na sciezce do korzenia sa same mniejsze *)
(* 6: wylistuj obiekty w drzewie w kolejnosc BFS *)
(* 7: zaimplementuj BST. wspólnie ustalamy sygnaturę *)
(* 8: utkaj z drzewa siatkę z kwadratów *)


(* Zadania off-topic, ale za to fajne:
  - podać dwa obiekty różnych typów, że są równe:
let (a : ??) = ??;;
let (b : ??) = ??;;
let c = (a=b);; *)


(* Rzeczy na jutro:
- drzewo przedziałowe
- fixpoint combinator
- koguty i logika (Coq and logic) *)