palladin

open System.Collections
open System.Collections.Generic

// LazyList dataType + Monoid Structure
type LazyList<'T> =   Empty
                    | Cons of 'T * (unit -> LazyList<'T>)
                    | Delay of (unit -> LazyList<'T>)
                    | Combine of LazyList<'T> * LazyList<'T> with
        interface IEnumerable<'T> with
            member self.GetEnumerator() =

palladin

let rec iterate f value = 
  seq { yield value; 
        yield! iterate f (f value) }

let fixedPoint f initial = 
    iterate f initial 
    |> Seq.pairwise 
    |> Seq.pick (fun (first, second) -> 
        if first = second then Some first else None)

palladin

type FuncList<'a> = 'a list -> 'a list
type CPSFuncList<'a> = FuncList<'a> -> FuncList<'a>
// Monoid comprehension
type CPSFuncListBuilder() =
    member self.Combine (first : CPSFuncList<'a>, second : CPSFuncList<'a>) : CPSFuncList<'a>  = 
        (fun k -> second (fun tail -> first (fun tail' -> k tail') tail))
    member self.Zero() : CPSFuncList<'a> = (fun k tail -> k tail)
    member self.Yield (value : 'a) : CPSFuncList<'a> = (fun k tail -> k (value :: tail))
    member self.YieldFrom (value : CPSFuncList<'a>) : CPSFuncList<'a> = value

palladin

// for more info http://www.cs.tufts.edu/~nr/cs257/archive/john-hughes/lists.pdf

type FuncList<'a> = 'a list -> 'a list
// Monoid comprehension
type FuncListBuilder() =
    member self.Combine (first : FuncList<'a>, second : FuncList<'a>) : FuncList<'a>  = (first << second) 
    member self.Zero() : FuncList<'a> = id
    member self.Yield (value : 'a) : FuncList<'a> = fun tail -> value :: tail
    member self.YieldFrom (value : FuncList<'a>) : FuncList<'a> = value
    member self.Delay ( f : unit -> FuncList<'a>) : FuncList<'a> = (fun tail -> f () tail)

palladin

// Based on http://blogs.msdn.com/b/chrsmith/archive/2008/02/22/regular-expressions-via-active-patterns.aspx

open System
open System.Text.RegularExpressions
  

let (|Match|_|) (pat:string) (inp:string) =
    let m = Regex.Match(inp, pat) in
    if m.Success
    then Some (List.tail [ for g in m.Groups -> g.Value ])

palladin

#r "FSharp.PowerPack.dll"


open System

// Generic container of 'T 
// Also parameterized by 'TypeClass : (new : unit -> 'TypeClass) 
// to implicit get a 'TypeClass instance (like passing the type class dictionary)
// The idea is to encode Type Classes with subtype polymorphism and OOP Classes 
type Generic<'T, 'TypeClass when 'TypeClass : (new : unit -> 'TypeClass)> = interface end

palladin

// Inspired by http://www.cs.utexas.edu/~wcook/Drafts/2006/MemoMixins.pdf

// State Monad combined with Continuation Monad (StateT Monad transformer)
type StateContMonad<'s, 'a, 'r> = StateContMonad of ('s -> ('s -> 'a -> 'r) -> 'r)

// Computation Builder
type StateContBuilder() =
    member self.Return value = 
        StateContMonad (fun state k -> k state value)
    member self.Bind(StateContMonad contStateMonad, f) = 

palladin

// Haskell-inspired infinite sequences

#r "FSharp.Powerpack"

let rec repeat n = LazyList.consDelayed n (fun () -> repeat n)
repeat 1 // seq [1; 1; 1; 1; ...]

let rec integersFrom n = LazyList.consDelayed n (fun () -> LazyList.map ((+) 1) <| integersFrom n) 
integersFrom 3 // seq [3; 4; 5; 6; ...]

palladin

let s : Printf.TextWriterFormat<_> = "let s : Printf.TextWriterFormat<_> = %c%s%c in
printf s (char 34) (s.Value) (char 34)" in printf s (char 34) (s.Value) (char 34)

palladin

// x = f(x) encoded in F#

let force (value : Lazy<_>) = value.Force()

let fix f = let rec x = lazy (f x) in x

// Examples
let fac = fix (fun f x -> if x = 0 then 1 else x * force f (x - 1) )
let nums = fix (fun v -> seq { yield 0; yield! Seq.map ((+) 1) (force v) })