open System;
// some aliases:
let omap = Option.map
let obind = Option.bind
let oiter = Option.iter
let is_some = Option.isSome
let is_none = Option.isNone
let get_or = Option.defaultValue
type Vec<'T> = ResizeArray<'T>;;

type Stream<'T> = unit -> Option<'T>

(* -----------------------------------------------------------------------
   A stream is a possibly infinite sequence of values.  A stream of
   values of type 'T is represented by a function of type (unit ->
   Option<'T>).  Each time the function is called, it either returns a
   next value (Some value) or None if there are no more values.  For
   example, the function (fun () -> None) represents the empty stream.
   The following infinte stream generates all even integers starting
   from zero:
*)
let mutable n = 0
let evenints() = fun () -> (n <- n+2; Some(n-2))

(* Most streams are mutable closures such as evenints.  These closures
   can be modified by a series of operations.  The first modifier
   limits the number of elements that a stream can generate:
*)

let limit n stream =
  let mutable counter = 0
  fun () ->
    if counter >= n then None
    else
      counter <- counter + 1
      stream()

// The next modifier applies a function to each generated value

let map mapfun stream =
  fun () -> stream() |> omap mapfun

(* For example, evenints |> map (fun x -> x*x) generates the sequence
   0 4 16 36 ...

   Each call to stream() returns a (Some x) or None.  If the function to
   be mapped also returns an option, we apply the following variant to
   avoid nested options:
*)
let map_oflatten mapfun stream =  fun () -> stream() |> obind mapfun

(*
   The next modifier applies a predicate ('T -> bool) to each value,
   keeping only those for which the predicate returns true
*)
let filter predicate stream =
  fun () ->
    let mutable next = stream()
    let notp = fun x -> not(predicate x)
    while (next |> omap notp |> get_or false) do
      next <- stream()
    next

(* 
  notp is the negation of the predicate.  
  The while loop keeps running if next contains a value for which notp
  holds.  Since next is an Option, we must again use Option.map to
  apply notp to the inner value.  (next |> omap notp) gives us an Option<bool>.
  We then extract the boolean value with get_or (Option.defaultValue),
  using false as default in case next is None.

  For example, if next is Some(4) and notp is fun x -> x>1 then 
  (next |> omap notp |> get_or false) produces the sequence of values

     Some(4) --> Some(true) --> true.

  However, if next is None, then the values generated are

     None --> None --> false

  The next modifier is similar to limit, but takes a predicate, and
  stops the stream when the predicate returns false:
*)

let take_while predicate stream =
  fun () -> stream()
            |> obind (fun x -> if predicate(x) then Some(x) else None)

(*
  Notice that this time we applied Option.bind (obind) instead of omap
  on the value produced because the function itself produces an Option.
  obind is applied to avoid producing a nested option (Some(Some(x)).

  A stream of streams (unit -> Option<unit -> Option<'T>>) should be
  flattened. This is a rather convoluted procedure involving options
  and streams.  Don't confuse this procedure with map_oflatten above.
  This time we're flattening a stream of streams:
*)

let flatten nested_stream =
  let mutable current_stream = nested_stream() // Option<stream>
  fun () ->
    let mutable next = current_stream |> obind (fun strm -> strm())
    while (is_none next) && (is_some current_stream) do
      current_stream <- nested_stream() 
      next <- current_stream |> obind (fun strm -> strm())
    next

(* Like Option, Stream is also a kind of "monad" because it has operations
   such as map, flatten and bind.  bind is flatten composed with map:
*)

let bind binder stream = stream |> map binder |> flatten

// Two streams can be joined to form a single stream:

let append stream1 stream2 =
  fun () -> 
    let next = stream1()
    match next with
      | Some(x) -> next
      | None -> stream2()

let (+++) a b = append a b      // defines an infix operator
// +++ has the same precedence and associativity as +


(* -------------------------------------------------------------------
   The next series of functions take streams and consume them by doing
   something with the values generated.
*)

let foreach action stream =
  let mutable next = stream()
  while (is_some next) do
    next |> oiter action // perform action on the option object
    next <- stream()     // get next value
// foreach

///// print the first 10 even numbers:
evenints() |> limit 10 |> foreach (fun x -> printfn "number %d" x)

(* Notice that we defined evenints as a function so that each call to
   evenints() re-creates the stream.  Each call to foreach consumes
   an instance of the stream (the stream would return None afterwards).

   We can define the for_all and there_exists quantifiers to streams.
*)

let for_all predicate stream =
  let mutable answer = true
  let mutable next = stream()
  while answer && (is_some next) do
    if not(next |> omap predicate |> get_or true) then answer <- false
    else next <- stream()
  answer

(* can replace omap with match:
   let mutable breakout = false
   while not(breakout) do
   match next with
     | Some(x) when not(predicate x) -> answer <- false; breakout<-true
     | Some(x) -> () // do nothing
     | None -> breakout <- true
*)
  
let there_exists predicate stream =
  not(for_all (fun x -> not(predicate x)) stream) 

(* there_exists just returns a boolean, but we probably want to find
   the actual value that exists.
*)   

let find_first predicate stream =
  let mutable next = stream()
  while not(next |> omap predicate |> get_or true) do
    next <- stream()
  next

// The following simply returns the nth value generated by the stream:

let nth n stream =
  let mutable cx = 0
  let mutable next = stream()
  while cx<n && (is_some next) do
    next <- stream()
    cx <- cx+1
  next


(*   --------------------------------------------------------------
     Operations to create streams.
     --------------------------------------------------------------

     Instead of defining a mutable closure for each stream, there are
     generalized ways to create them.
*)

let finite_stream<'T> (m:'T list) =
  let mutable index = 0
  fun () ->
    if index >= m.Length then None
    else
      index <- index + 1
      Some(m[index-1])

let empty_stream() = fun () -> None

let input_stream() = fun () ->
  let input = Console.ReadLine()
  if input="" then None else Some(input)

(* Infinite sequences are commonly defined inductively, from a base case
   and a function to generate the n+1st value from the nth value. Technically
   this is called "coinduction".  It's the inverse of induction or recursion,
   which goes backwards.  Coinduction goes forward:
*)

let coinduction base_case gen_next =  
  let mutable current = base_case
  fun () ->
    let previous = current;
    current <- gen_next current  // generates the next value
    Some(previous)

//// Fibonacci sequence, like you've never seen it before:
coinduction (0,1) (fun (a,b) -> (b,a+b))
  |> map (fun (x,y) -> y)
  |> limit 20
  |> foreach (printfn "FIB: %A")
  
//// The coinduction generates an infinite sequence of pairs (a,b)
//// starting from (0,1).  We apply map to take just the second value
//// of the pair to produce the sequence 1 1 2 3 5 8 13 21 ... 

//// The next example defines n!.  The codinduction defines pairs (n,nf)
//// with the meaning "nf is n!". 
//// 

let factorial(n) =
  coinduction (0,1) (fun (n,nf) -> (n+1, (n+1)*nf))
    |> map (fun (x,y) -> y)
    |> nth n |> Option.get

printfn "%d" (factorial 6)  // prints 720.

// We applied Option.get.  The justification is that n! always exists.

(*
   The next series of definitions will culminate in defining the infinte
   stream of all prime numbers.  First, we modify coinduction to use
   a mutable vector of values.  Each time the next value in the sequence
   is generated, it is added to the vector.  
*)

let vector_stream<'T> (m:Vec<'T>) =  // stream a vector as opposed to list
  let mutable i = 0
  fun () ->
    i <- i+1
    if i <= m.Count then Some(m[i-1]) else None

let vector_coinduction<'T> (seeds:Vec<'T>) gen_next =
  let mutable index = 0
  fun () ->
    if index < seeds.Count then
      index <- index + 1
      Some(seeds[index-1])
    else
      index <- index + 1 
      let next = gen_next seeds 
      seeds.Add(next)
      Some(next)

let seeded_coinduction<'T> (m:'T list) gen =  // use list to initialize vector
  let vec = Vec<'T>()
  for x in m do vec.Add(x)
  vector_coinduction vec gen

//// function to generate the next prime number given vector of known primes:
let next_prime (known_primes:Vec<int>) =
  if known_primes.Count < 2 then known_primes.Count + 2  //returns 2 or 3
  else
    let last_prime = known_primes.[known_primes.Count - 1]
    let candidates = coinduction (last_prime+2) (fun c -> c+2)
    candidates
      |> find_first(fun candidate ->
            vector_stream known_primes
              |> take_while(fun p -> float(p)<=1.0+Math.Sqrt(float(candidate)))
              |> for_all(fun p -> candidate % p <> 0))
      |> Option.get  // know it will exist (there are infinitely many primes)

let primes() = seeded_coinduction [2;3;5;7;11] next_prime

primes() |> limit 100 |> foreach (printf "%d ")
printfn ""


(* -------------------------------------------------------------------
   YOUR ASSIGNMENT:

   1. The first exercise just asks you to practice creating a mutable
      closure.  A "toggle" is a function that alternates between returning
      true and false.  Write a function maketoggle() that has the following
      behavior:

      let toggle1 = maketoggle()
      let toggle2 = maketoggle()
      printfn "%A" (toggle1())   // prints true
      printfn "%A" (toggle1())   // prints false
      printfn "%A" (toggle1())   // prints true
      printfn "%A" (toggle2())   // prints true

   Follow the example of "makea_ccumulator" in
   https://cs.hofstra.edu/~cscccl/csc123/closures.fsx

   ---------------------------------------------


   Add the following functions for streams

   1. until predicate stream   (let until predicate stream = ... )   

    This operation is similar to take_while but will INCLUDE the
    first value for which the predicate returns true.  For example,

    primes() |> until (fun p -> p > 10) should stop at 11, the first
    prime greater than 10.  Notice that

    primes() |> take_while (fun p -> p<=10) will stop at 7

    So until is not just the inverse of take_while.

   2. skip n stream

      This operation should take a stream and skip the first n values,
      returning the modified stream.

   3. find_last predicate stream

      This operation works like find_first but returns the last value
      for which the predicate holds.  This function should return Some(value)
      or None.

   3b. get_last predicate stream

      This operation should return the last value generated by a stream.
      This should be easy given find_last.  Think of what predicate to
      pass to find_last

   4. reduce operation id stream

   This operation should apply the binary operation to values generated
   by the stream, returning id on None.  This operation should consume the
   stream.

   for example, finite_stream [3;2;7]; |> reduce (+) 0  // should return 12

   5.  Use coinduction to define all powers of two: 1 2 4 8 16 31 64 128 ...

   6.  Using the stream of primes, write a procedure that prints all
       prime factors of a number n.  (a prime factor of n is a prime p
       such that n%p==0).  Use a combination of take_while, filter,
       etc...

       For example:  primefactors 10001 should print 73 and 137

   7. The binary factors of a number, such as 45, can be computed with
      the following sequence of pairs

      (1,45) -> (2,22) -> (4,11) -> (8,5) -> (16,2) -> (32,1)

      The binary factors are extracted from those pairs (factor,m)
      where m is odd.  Thus the binary factors of 45 are 1+4+8+32.
      Given n, we can define the sequence with

        coinduction (1,n) (fun (f,m) -> (f*2, m/2))

      Use this sequence to write a function that prints all the binary
      factors of n.  You will need a combination of take_while, filter
      and map.
*)