sem3

open System.Xml.Xsl

//
//let rec ins x = function
//| [] -> [[x]] // x = 0
//| y::ys as l-> // y=1  ys= 2 3
//    let L = ins x ys // list of lists
//    let N = List.map(fun z -> y::z) L
//    (x::l)::N
//
//ins 0 [1;2;3]

// constructor
let cons x y = x::y

let rec ins x = function
| [] -> [[x]] // x = 0
| y::ys as l-> // y=1  ys= 2 3
    (x::l)::(ins x ys |> List.map (cons y))
ins 0 [1;2;3]

//let rec perm = function
//| [] -> [[]]
//| x::xs -> // x = 1 xs = [2 3]
//    let L = perm xs// [[2;3];[3;2]]
//    let M = List.map (fun t -> ins x t) L // [ [[1;2;3];[2;1;3];[2;3;1]] ; [[]] ; [[]]]
//    List.concat M

let rec perm = function
| [] -> [[]]
| x::xs -> // x = 1 xs = [2 3]
    perm xs
    |> List.collect (ins x)



perm [1..3]

perm ["Hi";"there";"my";"friends"]

let fact n = [1..n] |> perm |> List.length
fact 5

//
//let rec fold f i = function
//| [] -> i
//| x::xs -> f x (fold f i xs)
//
//fold (fun x acc -> "f(" + x + "," + acc + ")") "empty" [1;2;3]



let rec foldr f i = function
| [] -> i
| x::xs -> f x (foldr f i xs)

foldr (fun x acc -> "f(" + string(x) + "," + acc + ")") "empty" [1;2;3]

// it is tail recursive for some reason...
let foldl f  i L =
    let rec fold' acc f = function
    | [] -> acc
    | x::xs -> fold' (f x acc) f xs
    fold' i f L

foldl (fun x acc -> "f(" + string(x) + "," + acc + ")") "empty" [1;2;3]

//// O(n^2)
//let rec rev = function
//| [] -> []
//| x::xs -> (rev xs)@[x]
//
//rev[1..100]


//// tail recursive
//let rev L =
//    let rec rev' acc = function
//    | [] -> acc
//    | x::xs -> rev' (x::acc) xs
//    rev' [] L
//
//rev[1..100]

let curry f x y = f(x,y)

let rev L = foldl (curry List.Cons) [] L

rev [1..100]

foldl (-) 0 [1;2;3;4]
foldr (-) 0 [1;2;3;4]

// array
let A = [|1;2;3|]
A.[0]
A.[0] <- 2
A

[1..2..10] // step 2
[for x in [1..10] -> x*2]// map
[for x in [1..10] do yield x*2]// the same

[for x in [1..10] do
 for y in [1..10] do
 if (x+y)=5 then yield (x,y)]


// my variant of pascal triangle:

let next L =
    let l1 = L |> List.pairwise |> List.map (fun (a,b) -> a + b )
    1::l1@[1]

next [1;3;3;1]

let pasc n =
    let rec pascrev (n:int): list<list<int>> =
        match n with
        | 1 -> [[1;1]]
        | _ -> match pascrev (n - 1) with
               | x::xs as prev-> (next x)::prev
    pascrev n |> List.rev

pasc 5


// functional queue is made as two stacks 1 2 3 4 = ([1;2], [4;3])

type 't queue = 't list * 't list
let put x (L,M) = (L,x::M)

let rec get = function
| ([],[]) -> failwith "Oh no!"
| ([],L) -> get (rev L, [])
| (x::xs,L) -> (x,(xs,L))


let empty = ([],[])

//    let fst (x,y) = x
//    let snd (x,y) = y

empty |> put 5 |> put 4 |> get |> snd |> put 1 |> get |> snd |> get


// zipper: ([3,4], [1,2])