module FSharp.Collections.JoinList
open System.Collections
open System.Collections.Generic
open System.Diagnostics.Contracts
// [snippet: Join List]
type JoinList<'a> =
| Empty
| Unit of 'a
| Join of JoinList<'a> * JoinList<'a> * int (* the total length of the JoinList *)
with
interface IEnumerable<'a> with
member this.GetEnumerator() =
let enumerable = seq {
match this with
| Empty -> ()
| Unit x -> yield x
| Join(x,y,_) ->
yield! x :> seq<'a>
yield! y :> seq<'a> }
enumerable.GetEnumerator()
member this.GetEnumerator() =
let enumerable = seq {
match this with
| Empty -> ()
| Unit x -> yield x
| Join(x,y,_) ->
yield! x :> seq<'a>
yield! y :> seq<'a> }
enumerable.GetEnumerator() :> IEnumerator
module JoinList =
let empty<'a> : JoinList<'a> = Empty
let isEmpty l = match l with Empty -> true | _ -> false
let length l =
match l with
| Empty -> 0
| Unit _ -> 1
| Join(_,_,l) -> l
let singleton x = Unit x
let ofSeq s = Seq.fold (fun xs x ->
match xs with
| Empty -> Unit x
| Unit _ -> Join(xs, Unit x, 2)
| Join(_,_,l) -> Join(xs, Unit x, l+1)) Empty s
let toSeq (l:JoinList<_>) = l :> seq<_>
let toList (l:JoinList<_>) = List.ofSeq l // NOTE: There is likely a better conversion to the List type.
let toArray (l:JoinList<_>) = Array.ofSeq l // NOTE: There is likely a better conversion to the Array type.
let rec equal left right =
match left with
| Empty -> match right with Empty -> true | _ -> false
| Unit x -> match right with Unit y -> x = y | _ -> false
| Join(x,y,l) ->
match right with
| Join(x',y',l') -> l = l' && equal x x' && equal y y' // TODO: || iterate each and compare the values.
| _ -> false
let cons hd tl =
match tl with
| Empty -> Unit hd
| _ -> Join(Unit hd, tl, length tl + 1)
let append left right =
match left with
| Empty -> right
| _ -> match right with
| Empty -> left
| _ -> Join(left, right, length left + length right)
let rec head l =
match l with
| Unit x -> x
| Join(x,y,_) -> head x
| _ -> failwith "JoinList.head: empty list"
let tail (l:JoinList<'a>) : JoinList<'a> =
let rec step (xs:JoinList<'a>) (acc:JoinList<'a>) : JoinList<'a> =
match xs with
| Empty -> acc
| Unit _ -> acc
| Join(x,y,_) -> step x (append y acc)
if isEmpty l then Empty else step l Empty
type JoinList<'a> with
static member op_Equality(left, right) = JoinList.equal left right
static member op_Nil() = JoinList.empty
static member op_Cons(hd, tl) = JoinList.cons hd tl
static member op_Append(left, right) = JoinList.append left right
// [/snippet]
module FSharp.Collections.Tests.JoinListTest
open System
open FSharp.Collections.JoinList
open FSharp.Collections.JoinList.JoinList
open NUnit.Framework
open FsUnit
// [snippet: Tests]
[]
let ``test should verify empty is Empty``() =
empty<_> |> should equal JoinList.Empty
let expected = Join(Unit 0, Join(Unit 1, Join(Unit 2, Join(Unit 3, Unit 4, 2), 3), 4), 5)
[]
let ``test length should return 5``() =
length expected |> should equal 5
[]
let ``test ofSeq should create a JoinList from a seq``() =
let test = seq { for i in 0..4 -> i }
JoinList.ofSeq test |> should equal expected
[]
let ``test ofSeq should create a JoinList from a list``() =
let test = [ for i in 0..4 -> i ]
JoinList.ofSeq test |> should equal expected
[]
let ``test ofSeq should create a JoinList from an array``() =
let test = [| for i in 0..4 -> i |]
JoinList.ofSeq test |> should equal expected
[]
let ``test cons should prepend 10 to the front of the original list``() =
cons 10 expected |> should equal (Join(Unit 10, expected, 6))
[]
let ``test singleton should return a Unit containing the solo value``() =
singleton 1 |> should equal (Unit 1)
[]
let ``test cons should return a Unit when the tail is Empty``() =
cons 1 JoinList.empty |> should equal (Unit 1)
[]
let ``test subsequent cons should create a JoinList just as the constructor functions``() =
cons 0 (cons 1 (cons 2 (cons 3 (cons 4 empty)))) |> should equal expected
[]
let ``test append should join two JoinLists together``() =
append expected expected |> should equal (Join(expected, expected, 10))
[]
let ``test head should return the first item in the JoinList``() =
head (append expected expected) |> should equal 0
[]
let ``test tail should return all items except the head``() =
tail (append expected expected) |> should equal (Join(cons 1 (cons 2 (cons 3 (cons 4 empty))), expected, 9))
[]
let ``test JoinList should respond to Seq functions such as map``() =
let testmap x = x*x
let actual = Seq.map testmap (append expected expected)
let expected = seq { yield 0; yield 1; yield 2; yield 3; yield 4; yield 0; yield 1; yield 2; yield 3; yield 4 } |> Seq.map testmap
Assert.That(actual, Is.EquivalentTo expected)
// [/snippet]