Skip to content

Instantly share code, notes, and snippets.

@jackfoxy
Created November 2, 2012 21:22
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jackfoxy/4004425 to your computer and use it in GitHub Desktop.
Save jackfoxy/4004425 to your computer and use it in GitHub Desktop.
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)))
| Node(_, a, [])::tl -> loop [] (fun lacc ->
loop tl (fun racc ->
cont (nodeF a lacc racc)))
| Node(_, a, h')::tl -> loop h' (fun lacc ->
loop tl (fun racc ->
cont (nodeF a lacc racc)))
| _ -> failwith "can't get here"
loop h (fun x -> x)
static member private inOrderStep3 (h : list<BinomialTree<'a>>) = (BinomialHeap.foldHeap (fun x l r acc -> l (x :: (r acc))) (fun acc -> acc) h) []
@jackfoxy
Copy link
Author

jackfoxy commented Nov 3, 2012

This will now fail when an empty list is passed through the loop, showing we now have a "null" pattern for the continuation identity function.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment