(* Zajecia 2 z programowania funkcyjnego *)


(* Nie typowe funkcje na listach *)

(* Foldl *)

let l = [1; 2; 3; 4; 5; 6];;

let rec foldl f l a =
  match l with
    [] -> a |
    h::t -> foldl f t (f h a);;

let rec foldr f l a =
  match l with
    [] -> a |
    h::t -> f h (foldr f t a);;


let fold = foldl;;

let sum l = fold (+) l 0;;

let prod l = fold ( * ) l 1;;

(* map *)

let map f l=
  foldr (fun h a -> (f h)::a) l [];;


let f = fun a -> a * a;;

map f l;;


(* filter *)

let filter p l =
  foldr (fun h t -> if (p h) then h::t else t) l [];;

let p = fun a -> if (a mod 2 = 0) then true else false;;

filter p l;;

(*
  teraz trzeba sie tym pobawic
*)

(* INTERLUDIUM A *)

(* Zmienne lokalne *)

(* zamiast *)

let square x = x *. x;;
let pi = 3.14;;

let powOld x = pi *. square x;;

let pow x =
  let pi = 3.14
  and s = x *. x
  in pi *. s;;

(* testy *)

pow 10.0;;
pow 3.0;;

powOld 10.0;;
pow 3.0;;

(* iloczyny kartezjanskie *)

(1, 2, 3);;

let para x y = (x, y);;

let rzut_x (x, _) = x;;

let rzut_y (_, y) = y;;

(42, (6.9, "Ala ma kota"));;

(* listy operacje:
  - @, append
  - nth
  - hd
  - tl
  - rev
  - length

open List;; 
    <- modul dla list
*)

(* QUICKSORT *)

(* Otwieranie modułów:

open <Nazwa_modułu>;; *)

open List;;
open Random;;

(* zlaczmy liste *)

let lista = l @ l;;

(* a teraz posortujmy *)

let rec quick_sort l =
  let split l x = (filter  (fun y -> y < x) l,
		   filter  (fun y -> y = x) l,
		   filter  (fun y -> y > x) l)
  in
    if length l < 2 then l else 
    let x = nth l (Random.int (length l)) 
    in  
      let (ll, le, lg) = split l x
      in
      (quick_sort ll) @ le @ (quick_sort lg);;

quick_sort lista;;


(* INTERLUDIUM B - typy *)

type p = int * float;;

type ('a, 'b) para = 'a * 'b;; 

type point = float * float;;
type vector = float * float;;

let (p:point) = (2.,3.);;

let shift ((x,y):point) ((xo, yo):vector) =
  ((x +. xo , y +. yo) : point);;

shift p p;;

(* rekordy *)

type ulamek = { licznik : int ; mianownik : int };;

let q = { licznik = 3; mianownik = 4 };;

let { licznik = a; mianownik = b } = q;;

a;;

b;;

q.licznik;;

q.mianownik;;

let {licznik = c} = q;;

(* Kolejka FIFO *)

type 'a fifo = { front: 'a list; back: 'a list; size : int};;

let empty_fifo = { front = []; back = []; size = 0};;

let size q = q.size;;

let is_empty_queue q = (size q = 0);;

let balance q =
  match q with
    {front=[]; back = []} -> q |
    {front=[]; back = b; size = s} -> {front = rev b; back = []; size = s} |
    _ -> q;;

let put {front = f; back = b; size = s} x = 
    balance {front = f; back = x::b; size = s};;

let first q =
    match q with
      {front = []} -> failwith "Pusta kolejka" |
      {front = x::_} -> x;;

let remove_first q =
    match q with
      {front = _::f} -> balance {front = f; back = q.back; size = q.size -1} |
      _ -> empty_fifo;;


(* opcjonalne *)

(* przyklad 
dostaje krotke list i je skleja.
I robi do samo dla krotek list *)