我正在尝试使用 Wikibooks 上的 AwesomeCollections 库
https://en.wikibooks.org/wiki/F_Sharp_Programming/Advanced_Data_Structures
从该页面，我复制粘贴了标记为 .fsi 和 .fs 的 2 个单独的文件代码
我必须承认我不太了解 .fsi 和 .fs 文件如何交互，以及在 https://msdn.microsoft.com/en-us/library/dd233196.aspx 上找到的解释。对我来说很神秘。
通过一些重新格式化，如果我提出解决方案并仅使用 .fs 文件，它就可以正常工作。
但是，同时使用 .fsi 和 .fs 文件，我收到错误消息，例如
“未定义命名空间‘堆’”(在项目的主 .fs 文件中)
“没有可用于‘int BinaryHeap’类型的构造函数”(在项目的主 .fs 文件中)
“实现文件中的意外关键字‘类型’”(尝试在 .fs 文件中定义类型队列时)
(* 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 -> ()
维护.fs(尝试使用这些库的主程序)
///////////////// 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)
最后，如果在解决方案中，我决定使用以下文件
AwesomeCollections_bis.fs 单独(没有 fsi 文件)代码可以编译。
// 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 -> ()
我可以看到缩进很重要，我认为使用它可以解决问题，但对我来说却没有。
感谢任何人的慷慨帮助!
最佳答案
我认为你的代码没有编译的原因是 fsi interface文件隐藏了BinaryHeap的构造函数，因此以下内容不起作用，因为构造函数是私有(private)的:
let highheap = new BinaryHeap<int>(compare,EmptyHeap)
该类型暴露了
make静态成员，所以我认为您可以使用它:let highheap = BinaryHeap.make compare
这可能不是特别惯用的 F# 设计，但我想它主要是一个示例，而不是一个维护库。 FSharpX Collections 中可能有一些替代方案图书馆。
关于module - F# 命名空间和模块 : Awesome collections from Wikibooks，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35308322/