f#

open System

let pow i n = i ** (float n)

let rec iter i predicate f acc =
    if (predicate acc) then
        iter (i+1) predicate f (f acc i)
    else
        acc

let smart_f (el, sum, x) i =
    let step = el * (-1. / 9.) * pow x 2
    (step, sum + step, x)

let predicate (el, sum, x) = System.Math.Abs(el:float) > System.Double.Epsilon

let tailor_sum_smart x =
    let (el, sum, x) = iter 0 predicate smart_f (-1., 0., x)
    sum

//
//let naive_f (_, sum, x) i =
//    let step = pow -1. i * pow x (2*i + 1) / pow 9. (i + 1)
//    (step, sum + step, x)
//
//let tailor_sum_naive x =
//    let (el, sum, x) = iter 0 predicate naive_f (-1., 0., x)
//    sum
//
//tailor_sum_naive -1.0

//let compute_i_element_naive i x =
//let series_sum_naive i acc x =
//    acc + compute_i_element_naive i x
//
//let series_start x = x / 9.
//
//let compute_i_element_smart prev i x = -1. * prev * 9. * pow x 2
//
//
//
//
//
//iter 0 10 series_sum_naive series_start 1.0
//
//
//

// lecture 2

// question about predicates


let rec fmin = function
| [x] -> (x, [])
| x::xs ->
    let (z, zs) = fmin xs
    if z > x then (x, xs)
    else (z, x::zs)

let rec sort = function
| [] -> []
| [x] -> [x]
| L ->
    let (x, xs) = fmin L;
    x::sort xs

sort [3;2;1]


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




let sum = fold (+) 0
sum [1..100]

let head (x::_) = x
let tail = function x::xs -> xs


let minel L = fold min (List.head L) L
//let minel = fold min (System.Int32.MaxValue)
let length L = fold (fun _ acc -> acc+1) 0 L

let minmax L = fold (fun x (mi, ma) -> (min mi x, max ma x)) (List.head L, List.head L) L

List.map ((*)2) [1;2;3]

let flip f x y = f y x

//let divisible_by number i =
//[2..100] |> List.filter ()

let rec eratosphenes = function
    | [] -> []
    | x::xs -> x::(eratosphenes (List.filter (flip (%) x >> (<) 0) xs))

eratosphenes [2..100]


// seminar 3
// permutations

let rec ins x = function
| [] -> [[x]]
| y::ys as l ->
    let L = ins x ys
    let N = List.map (fun z -> y::z) L
    (x::l)::N

//ins 0 [1;2;3]

// [1;2;3]
let rec perm = function
| [] -> [[]]
| x::xs as l -> // x = 1; xs = [2;3]
    let L = perm xs // [[2;3];[3;2]]
    let M = List.map (fun t -> ins x t) L // [ list of insertions; list of insertions ]
    List.concat M // collect all insertions into one list
    // List.mapconcat -> List.collect (f, list)

perm [1..3]


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

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]

//let rec rev = function
//| [] -> []
//| x::xs -> (rev xs)@[x]  @ - append, x::xs - concat
//
//let rec rev' acc = function
//| [] -> acc
//| x::xs -> rev' (x::acc) xs

//
let rev L = foldl (fun x acc -> x::acc) [] L



// arrays

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


// pascal triangle



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

let pascal i =
    let rec pascal' a b L =
        if (a < b) then
            let s = List.map (uncurry (+)) (List.pairwise (List.head L))
            pascal' (a+1) b ((1::s@[1])::L)
        else
            L
    pascal' 0 i [[1]]
pascal 5

type 't queue = 't list * 't list

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




let scalarProduct1 = List.reduce (+) << uncurry (List.map2 (*))


// trees

type 't tree =
    | Nil
    | Node of 't *'t tree * 't tree

let Leaf x = Node(x, Nil, Nil)
let t = Node(0, Leaf(1), Node(2,Leaf(3),Nil))

let ex = Node('+', Leaf('1'), Node('*', Leaf('1'),Leaf('2')))

//traversal
//
//type trav_order = Prefix | Infix | Postfix
//
//let rec traverse f order = function
//| Nil -> ()
//| Node(x,l,r) ->
//    match order with
//    | Prefix ->  f x; traverse f order l; traverse f order r
//    | Infix -> traverse f order l; f x; traverse f order r
//    | Postfix -> traverse f order l; f x; traverse f order r
//
//
//traverse (printf "%A ") Prefix ex

let Prefix n l r = n();l();r()
let Infix n l r = l();n();r()
let Postfix n l r = l();r();n()

let rec traverse order f = function
| Nil -> ()
| Node(x,l,r) ->
    order (fun () -> f x) (fun () -> traverse order f l) (fun () -> traverse order f r)


traverse Postfix (printf "%A ") ex

let rec treefold f acc = function
| Nil -> acc
| Node(x,l,r) ->
    let x1 = treefold f acc l
    let x2 = f x x1
    treefold f x2 r

treefold (fun a b -> string(a)+string(b)) "" ex


let rec insert x = function
| Nil -> Leaf(x)
| Node(z,l,r) as N ->
    if (x < z) then Node(z, insert x l, r)
    elif (x > z) then Node(z, l, insert x r)
    else N

let rnd = new System.Random()

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

let l = [for x in [1..10] -> rnd.Next(1,100)]

l |> List.fold (flip' insert) Nil |> treefold (curry List.Cons) []

// calculate freq dict
let rec insert' x = function
| Nil -> Leaf(x, 0)
| Node((z,n),l,r) as N ->
    if (x < z) then Node((z,n), insert' x l, r)
    elif (x > z) then Node((z,n), l, insert' x r)
    else Node((x, n+1), l, r)



open System.IO
let freq_tree =
    File.ReadAllLines(@"")
    |> Array.collect (fun s -> s.Split([|' ';'-';',';';';'!';'?';|]))
    |> Array.filter (fun x -> x.Length > 0)
    |> Array.fold (flip insert') Nil
//    |> treefold (curry List.Cons) []
//    |> List.sortBy ((~-) << snd)
//    |> List.take 5

let rec treesize = function
| Nil -> 0
| Node(_,l,r) -> 1 + treesize l + treesize r

treesize freq_tree

//continuations

5 |> (+) 1 |> (*) 2 |> printf "%d"
let plus1 x f= f(x + 1)
let times2 x f = f(x*2)

plus1 5 (fun x ->  times2 x (printf "%d"))

let rec len f = function
| [] -> f 0
| _::t -> len ((+) 1 << f) t

len id [1..10]


let rec size' f = function
| Nil -> f 0
| Node(_,l,r) ->
    l |> size' (fun x1 ->
        r |> size' (fun x2 -> f(1 + x1 + x2)))

size' id freq_tree



// closures and generators

let create_counter f x =
    let mutable c = x
    fun () ->
        c<-f c; c

let fibgen = create_counter (fun (x,y)-> (x+y, x)) (1I,1I)
fibgen()

let map' f g =
    fun () -> f(g())

let rec filter' f g =
    fun () ->
        let x = g()
        if f x then x else (filter' f g)()

let fibs = fibgen |> map' fst |> filter' (fun x -> x>1000000001I)
fibs()