I'm trying to use the library AwesomeCollections on Wikibooks https://en.wikibooks.org/wiki/F_Sharp_Programming/Advanced_Data_Structures
From that page, i have copied paste in 2 separate files code marked for .fsi and .fs
I must admit i don't understand well how .fsi and .fs files interact, and that explanations such those found on https://msdn.microsoft.com/en-us/library/dd233196.aspx are cryptic to me.
with a bit of re-formating, if i make a solution and use only the .fs file, it works fine.
However, using both the .fsi and .fs file, i get Error message such as "the namespace 'Heap' is not defined" (in the main .fs file of the project) "No constructors are available for the type 'int BinaryHeap'" (in the main .fs file of the project)
"Unexpected keyword 'type' in implementation file" (when trying to define the type Queue in the .fs file)
(* AwesomeCollections.fsi *)
namespace AwesomeCollections
type 'a stack =
| EmptyStack
| StackNode of 'a * 'a stack
module Stack = begin
val hd : 'a stack -> 'a
val tl : 'a stack -> 'a stack
val cons : 'a -> 'a stack -> 'a stack
val empty : 'a stack
val rev : 'a stack -> 'a stack
end
[<Class>]
type 'a Queue =
member hd : 'a
member tl : 'a Queue
member enqueue : 'a -> 'a Queue
static member empty : 'a Queue
[<Class>]
type BinaryTree<'a when 'a : comparison> =
member hd : 'a
member left : 'a BinaryTree
member right : 'a BinaryTree
member exists : 'a -> bool
member insert : 'a -> 'a BinaryTree
member print : unit -> unit
static member empty : 'a BinaryTree
//[<Class>]
//type 'a AvlTree =
// member Height : int
// member Left : 'a AvlTree
// member Right : 'a AvlTree
// member Value : 'a
// member Insert : 'a -> 'a AvlTree
// member Contains : 'a -> bool
//
//module AvlTree =
// [<GeneralizableValue>]
// val empty<'a> : AvlTree<'a>
[<Class>]
type 'a BinaryHeap =
member hd : 'a
member tl : 'a BinaryHeap
member insert : 'a -> 'a BinaryHeap
member merge : 'a BinaryHeap -> 'a BinaryHeap
interface System.Collections.IEnumerable
interface System.Collections.Generic.IEnumerable<'a>
static member make : ('b -> 'b -> int) -> 'b BinaryHeap
AwesomeCollections.fs
(* AwesomeCollections.fs *)
namespace AwesomeCollections
type 'a stack =
| EmptyStack
| StackNode of 'a * 'a stack
module Stack =
let hd = function
| EmptyStack -> failwith "Empty stack"
| StackNode(hd, tl) -> hd
let tl = function
| EmptyStack -> failwith "Emtpy stack"
| StackNode(hd, tl) -> tl
let cons hd tl = StackNode(hd, tl)
let empty = EmptyStack
let rec rev s =
let rec loop acc = function
| EmptyStack -> acc
| StackNode(hd, tl) -> loop (StackNode(hd, acc)) tl
loop EmptyStack s
type Queue<'a>(f : stack<'a>, r : stack<'a>) =
let check = function
| EmptyStack, r -> Queue(Stack.rev r, EmptyStack)
| f, r -> Queue(f, r)
member this.hd =
match f with
| EmptyStack -> failwith "empty"
| StackNode(hd, tl) -> hd
member this.tl =
match f, r with
| EmptyStack, _ -> failwith "empty"
| StackNode(x, f), r -> check(f, r)
member this.enqueue(x) = check(f, StackNode(x, r))
static member empty = Queue<'a>(Stack.empty, Stack.empty)
type color = R | B
type 'a tree =
| E
| T of color * 'a tree * 'a * 'a tree
module Tree =
let hd = function
| E -> failwith "empty"
| T(c, l, x, r) -> x
let left = function
| E -> failwith "empty"
| T(c, l, x, r) -> l
let right = function
| E -> failwith "empty"
| T(c, l, x, r) -> r
let rec exists item = function
| E -> false
| T(c, l, x, r) ->
if item = x then true
elif item < x then exists item l
else exists item r
let balance = function (* Red nodes in relation to black root *)
| B, T(R, T(R, a, x, b), y, c), z, d (* Left, left *)
| B, T(R, a, x, T(R, b, y, c)), z, d (* Left, right *)
| B, a, x, T(R, T(R, b, y, c), z, d) (* Right, left *)
| B, a, x, T(R, b, y, T(R, c, z, d)) (* Right, right *)
-> T(R, T(B, a, x, b), y, T(B, c, z, d))
| c, l, x, r -> T(c, l, x, r)
let insert item tree =
let rec ins = function
| E -> T(R, E, item, E)
| T(c, a, y, b) as node ->
if item = y then node
elif item < y then balance(c, ins a, y, b)
else balance(c, a, y, ins b)
(* Forcing root node to be black *)
match ins tree with
| E -> failwith "Should never return empty from an insert"
| T(_, l, x, r) -> T(B, l, x, r)
let rec print (spaces : int) = function
| E -> ()
| T(c, l, x, r) ->
print (spaces + 4) r
printfn "%s %A%A" (new System.String(' ', spaces)) c x
print (spaces + 4) l
type BinaryTree<'a when 'a : comparison> (inner : 'a tree) =
member this.hd = Tree.hd inner
member this.left = BinaryTree(Tree.left inner)
member this.right = BinaryTree(Tree.right inner)
member this.exists item = Tree.exists item inner
member this.insert item = BinaryTree(Tree.insert item inner)
member this.print() = Tree.print 0 inner
static member empty = BinaryTree<'a>(E)
type 'a heap =
| EmptyHeap
| HeapNode of int * 'a * 'a heap * 'a heap
module Heap =
let height = function
| EmptyHeap -> 0
| HeapNode(h, _, _, _) -> h
(* Helper function to restore the leftist property *)
let makeT (x, a, b) =
if height a >= height b then HeapNode(height b + 1, x, a, b)
else HeapNode(height a + 1, x, b, a)
let rec merge comparer = function
| x, EmptyHeap -> x
| EmptyHeap, x -> x
| (HeapNode(_, x, l1, r1) as h1), (HeapNode(_, y, l2, r2) as h2) ->
if comparer x y <= 0 then makeT(x, l1, merge comparer (r1, h2))
else makeT (y, l2, merge comparer (h1, r2))
let hd = function
| EmptyHeap -> failwith "empty"
| HeapNode(h, x, l, r) -> x
let tl comparer = function
| EmptyHeap -> failwith "empty"
| HeapNode(h, x, l, r) -> merge comparer (l, r)
let rec to_seq comparer = function
| EmptyHeap -> Seq.empty
| HeapNode(h, x, l, r) as node -> seq { yield x; yield! to_seq comparer (tl comparer node) }
type 'a BinaryHeap(comparer : 'a -> 'a -> int, inner : 'a heap) =
(* private *)
member this.inner = inner
(* public *)
member this.hd = Heap.hd inner
member this.tl = BinaryHeap(comparer, Heap.tl comparer inner)
member this.merge (other : BinaryHeap<_>) = BinaryHeap(comparer, Heap.merge comparer (inner, other.inner))
member this.insert x = BinaryHeap(comparer, Heap.merge comparer (inner,(HeapNode(1, x, EmptyHeap, EmptyHeap))))
interface System.Collections.Generic.IEnumerable<'a> with
member this.GetEnumerator() = (Heap.to_seq comparer inner).GetEnumerator()
interface System.Collections.IEnumerable with
member this.GetEnumerator() = (Heap.to_seq comparer inner :> System.Collections.IEnumerable).GetEnumerator()
static member make(comparer) = BinaryHeap<_>(comparer, EmptyHeap)
type 'a lazyStack =
| Node of Lazy<'a * 'a lazyStack>
| EmptyStack
module LazyStack =
let (|Cons|Nil|) = function
| Node(item) ->
let hd, tl = item.Force()
Cons(hd, tl)
| EmptyStack -> Nil
let hd = function
| Cons(hd, tl) -> hd
| Nil -> failwith "empty"
let tl = function
| Cons(hd, tl) -> tl
| Nil -> failwith "empty"
let cons(hd, tl) = Node(lazy(hd, tl))
let empty = EmptyStack
let rec append x y =
match x with
| Cons(hd, tl) -> Node(lazy(printfn "appending... got %A" hd; hd, append tl y))
| Nil -> y
let rec iter f = function
| Cons(hd, tl) -> f(hd); iter f tl
| Nil -> ()
maintenance.fs (main program trying to use those libraries)
///////////////// preparing the data ////////////////////
open System
open System.Collections.Generic
open System.IO
open AwesomeCollections
open AwesomeCollections.Stack
open AwesomeCollections.Heap
let stopWatch = System.Diagnostics.Stopwatch.StartNew()
let x = File.ReadAllLines "C:\Users\Fagui\Documents\GitHub\Learning Fsharp\Algo Stanford\PA 6 - median.txt"
let lowheap = new BinaryHeap<int>(compare,EmptyHeap)
let highheap = new BinaryHeap<int>(compare,EmptyHeap)
Finally if in the solution, I decide to use the following file AwesomeCollections_bis.fs alone (no fsi file) the code will compile ok.
// this file used without the fsi file works
// but i don't know why
(* AwesomeCollections_bis.fs *)
namespace AwesomeCollections
type 'a stack =
| EmptyStack
| StackNode of 'a * 'a stack
module Stack =
let hd = function
| EmptyStack -> failwith "Empty stack"
| StackNode(hd, tl) -> hd
let tl = function
| EmptyStack -> failwith "Empty stack"
| StackNode(hd, tl) -> tl
let cons hd tl = StackNode(hd, tl)
let empty = EmptyStack
let rec rev s =
let rec loop acc = function
| EmptyStack -> acc
| StackNode(hd, tl) -> loop (StackNode(hd, acc)) tl
loop EmptyStack s
type Queue<'a>(f : stack<'a>, r : stack<'a>) =
let check = function
| EmptyStack, r -> Queue(Stack.rev r, EmptyStack)
| f, r -> Queue(f, r)
member this.hd =
match f with
| EmptyStack -> failwith "empty"
| StackNode(hd, tl) -> hd
member this.tl =
match f, r with
| EmptyStack, _ -> failwith "empty"
| StackNode(x, f), r -> check(f, r)
member this.enqueue(x) = check(f, StackNode(x, r))
static member empty = Queue<'a>(Stack.empty, Stack.empty)
type color = R | B
type 'a tree =
| E
| T of color * 'a tree * 'a * 'a tree
module Tree =
let hd = function
| E -> failwith "empty"
| T(c, l, x, r) -> x
let left = function
| E -> failwith "empty"
| T(c, l, x, r) -> l
let right = function
| E -> failwith "empty"
| T(c, l, x, r) -> r
let rec exists item = function
| E -> false
| T(c, l, x, r) ->
if item = x then true
elif item < x then exists item l
else exists item r
let balance = function (* Red nodes in relation to black root *)
| B, T(R, T(R, a, x, b), y, c), z, d (* Left, left *)
| B, T(R, a, x, T(R, b, y, c)), z, d (* Left, right *)
| B, a, x, T(R, T(R, b, y, c), z, d) (* Right, left *)
| B, a, x, T(R, b, y, T(R, c, z, d)) (* Right, right *)
-> T(R, T(B, a, x, b), y, T(B, c, z, d))
| c, l, x, r -> T(c, l, x, r)
let insert item tree =
let rec ins = function
| E -> T(R, E, item, E)
| T(c, a, y, b) as node ->
if item = y then node
elif item < y then balance(c, ins a, y, b)
else balance(c, a, y, ins b)
(* Forcing root node to be black *)
match ins tree with
| E -> failwith "Should never return empty from an insert"
| T(_, l, x, r) -> T(B, l, x, r)
let rec print (spaces : int) = function
| E -> ()
| T(c, l, x, r) ->
print (spaces + 4) r
printfn "%s %A%A" (new System.String(' ', spaces)) c x
print (spaces + 4) l
type BinaryTree<'a when 'a : comparison> (inner : 'a tree) =
member this.hd = Tree.hd inner
member this.left = BinaryTree(Tree.left inner)
member this.right = BinaryTree(Tree.right inner)
member this.exists item = Tree.exists item inner
member this.insert item = BinaryTree(Tree.insert item inner)
member this.print() = Tree.print 0 inner
static member empty = BinaryTree<'a>(E)
type 'a heap =
| EmptyHeap
| HeapNode of int * 'a * 'a heap * 'a heap
module Heap =
let height = function
| EmptyHeap -> 0
| HeapNode(h, _, _, _) -> h
(* Helper function to restore the leftist property *)
let makeT (x, a, b) =
if height a >= height b then HeapNode(height b + 1, x, a, b)
else HeapNode(height a + 1, x, b, a)
let rec merge comparer = function
| x, EmptyHeap -> x
| EmptyHeap, x -> x
| (HeapNode(_, x, l1, r1) as h1), (HeapNode(_, y, l2, r2) as h2) ->
if comparer x y <= 0 then makeT(x, l1, merge comparer (r1, h2))
else makeT (y, l2, merge comparer (h1, r2))
let hd = function
| EmptyHeap -> failwith "empty"
| HeapNode(h, x, l, r) -> x
let tl comparer = function
| EmptyHeap -> failwith "empty"
| HeapNode(h, x, l, r) -> merge comparer (l, r)
let rec to_seq comparer = function
| EmptyHeap -> Seq.empty
| HeapNode(h, x, l, r) as node -> seq { yield x; yield! to_seq comparer (tl comparer node) }
type 'a BinaryHeap(comparer : 'a -> 'a -> int, inner : 'a heap) =
(* private *)
member this.inner = inner
(* public *)
member this.hd = Heap.hd inner
member this.tl = BinaryHeap(comparer, Heap.tl comparer inner)
member this.merge (other : BinaryHeap<_>) = BinaryHeap(comparer, Heap.merge comparer (inner, other.inner))
member this.insert x = BinaryHeap(comparer, Heap.merge comparer (inner,(HeapNode(1, x, EmptyHeap, EmptyHeap))))
interface System.Collections.Generic.IEnumerable<'a> with
member this.GetEnumerator() = (Heap.to_seq comparer inner).GetEnumerator()
interface System.Collections.IEnumerable with
member this.GetEnumerator() = (Heap.to_seq comparer inner :> System.Collections.IEnumerable).GetEnumerator()
static member make(comparer) = BinaryHeap<_>(comparer, EmptyHeap)
type 'a lazyStack =
| Node of Lazy<'a * 'a lazyStack>
| EmptyStack
module LazyStack =
let (|Cons|Nil|) = function
| Node(item) ->
let hd, tl = item.Force()
Cons(hd, tl)
| EmptyStack -> Nil
let hd = function
| Cons(hd, tl) -> hd
| Nil -> failwith "empty"
let tl = function
| Cons(hd, tl) -> tl
| Nil -> failwith "empty"
let cons(hd, tl) = Node(lazy(hd, tl))
let empty = EmptyStack
let rec append x y =
match x with
| Cons(hd, tl) -> Node(lazy(printfn "appending... got %A" hd; hd, append tl y))
| Nil -> y
let rec iter f = function
| Cons(hd, tl) -> f(hd); iter f tl
| Nil -> ()
i can see indentation is important and I thought playing with it would solve the problem, but it didn't for me.
Thank you for anyone graciously helping !
I think that the reason why your code is not compiling is that the fsi interface file hides the constructor of BinaryHeap, so the following does not work because the constructor is private:
let highheap = new BinaryHeap<int>(compare,EmptyHeap)
The type exposes a make static member so I think you can use that instead:
let highheap = BinaryHeap.make compare
This is probably not particularly idiomatic F# design, but I guess it is mostly a sample rather than a maintained library. There might be some alternatives in FSharpX Collections library.