Skip to content

Instantly share code, notes, and snippets.

View jackfoxy's full-sized avatar

Jack Fox jackfoxy

View GitHub Profile
@jackfoxy
jackfoxy / BinomialHeap type structure.fs
Created November 2, 2012 17:10
BinomialHeap type structure
type BinomialTree<'a> = Node of (int * 'a * list<BinomialTree<'a>>)
type BinomialHeap<'a when 'a : comparison> (isMaximalist : bool, heap : list<BinomialTree<'a>>)
@jackfoxy
jackfoxy / BinomialHeap type structure.fs
Created November 2, 2012 19:04
BinomialHeap type structure
type BinomialTree<'a> = Node of (int * 'a * list<BinomialTree<'a>>)
type BinomialHeap<'a when 'a : comparison> (isMaximalist : bool, heap : list<BinomialTree<'a>>)
@jackfoxy
jackfoxy / BinomialHeap fold step 1.fs
Created November 2, 2012 19:51
Step one in creating a fold over a BinomialHeap
static member private foldHeapStep1 (h : list<BinomialTree<'a>>) =
let rec loop (h : list<BinomialTree<'a>>) cont =
match h with
| Node(_, a, [])::[] -> cont [a]
| Node(_, a, h')::[] -> loop h' (fun acc -> cont (a :: acc))
| Node(_, a, [])::tl -> loop tl (fun acc -> cont (a :: acc))
| Node(_, a, h')::tl -> loop h' (fun lacc -> loop tl (fun racc -> cont (a :: racc @ lacc)))
| _ -> failwith "can't get here"
@jackfoxy
jackfoxy / BinomialHeap fold step 2.fs
Created November 2, 2012 20:10
Step two in creating a fold over a BinomialHeap
static member private foldHeapStep2 c1 c2 c3 (t : list<BinomialTree<'a>>) =
let rec loop (h : list<BinomialTree<'a>>) cont =
match t with
| Node(_, a, [])::[] -> cont (c1 [a])
| Node(_, a, h')::[] -> loop h' (fun acc -> cont (c2 a acc))
| Node(_, a, [])::tl -> loop tl (fun acc -> cont (c2 a acc))
| Node(_, a, h')::tl -> loop h' (fun lacc ->
loop tl (fun racc ->
cont (c3 a lacc racc)))
@jackfoxy
jackfoxy / BinomialHeap fold step 3.fs
Created November 2, 2012 21:22
Step three in creating a fold over a BinomialHeap
static member private foldHeapStep3 nodeF leafV (h : list<BinomialTree<'a>>) =
let rec loop (h : list<BinomialTree<'a>>) cont =
match h with
| Node(_, a, [])::[] -> loop [] (fun lacc ->
loop [] (fun racc ->
cont (nodeF a lacc racc)))
| Node(_, a, h')::[] -> loop h' (fun lacc ->
loop [] (fun racc ->
cont (nodeF a lacc racc)))
@jackfoxy
jackfoxy / BinomialHeap fold.fs
Created November 2, 2012 22:04
fold over a BinomialHeap
static member private foldHeap nodeF leafV (h : list<BinomialTree<'a>>) =
let rec loop (h : list<BinomialTree<'a>>) cont =
match h with
| Node(_, a, h')::tl -> loop h' (fun lacc ->
loop tl (fun racc ->
cont (nodeF a lacc racc)))
| _ -> cont leafV
loop h (fun x -> x)
@jackfoxy
jackfoxy / BinomialHeap fold step 4.fs
Created November 3, 2012 17:36
Step four in creating a fold over a BinomialHeap
static member private foldHeapStep4 nodeF leafV (h : list<BinomialTree<'a>>) =
let rec loop (h : list<BinomialTree<'a>>) cont =
match h with
| Node(_, a, [])::[] -> loop [] (fun lacc ->
loop [] (fun racc ->
cont (nodeF a lacc racc)))
| Node(_, a, h')::[] -> loop h' (fun lacc ->
loop [] (fun racc ->
cont (nodeF a lacc racc)))
@jackfoxy
jackfoxy / genBinomialHeap.fs
Created November 4, 2012 18:17
generate example BinomialHeap internals in order
let f = (fun acc -> ("b" :: (acc |> (fun acc -> ("c" :: (acc |> (fun acc -> ("a" :: (acc |> (fun acc -> acc)))) |> (fun acc -> acc) |> (fun x -> x)))|> (fun acc -> acc) ))) |> (fun acc -> acc) )
f []
@jackfoxy
jackfoxy / LetsMakeADealGame.fs
Created November 13, 2012 00:30
game type for Monty Hall problem
type game(doorWithPrize: int, fstChoice: int, revealedDoor: int) =
member x.winFstChoice = (doorWithPrize = fstChoice)
member x.winSwitch = (not(doorWithPrize = fstChoice)&&(not(doorWithPrize = revealedDoor)))
member x.revealed = revealedDoor
member x.ToString = "Prize Door: " + doorWithPrize.ToString() + "; "
+ "First Choice: " + fstChoice.ToString() + "; "
+ "Revealed Door: " + revealedDoor.ToString() + "; "
+ "Wins 1st Choice: " + x.winFstChoice.ToString() + "; "
+ "Wins Switch: " + x.winSwitch.ToString()
@jackfoxy
jackfoxy / RandomReveal.fs
Created November 13, 2012 00:31
random reveal of a door for Monty Hall problem
let rndReveal doorWithPrize =
let rnd = seedRnd.Next(1,3)
match doorWithPrize with
|1 -> (rnd + 1)
|2 -> if rnd = 1 then 1
else 3
|_ -> rnd