let depth = 1000000

module Test =
    let check basis createItem =
        let rec createList n l  =
            if n = 0 then l
            else createList (n-1) (createItem (int64 n, int64 n) l)

        let a0 = createList depth basis
        let a1 = createList depth basis

        (a0 = a1)
        && (a0 <= a1)
        && (a0 >= a1)
        && not (a0 < a1)
        && not (a0 > a1)
        && not (a0 <> a1)

    let inline run basis createItem =
        let createItemType = string (createItem.GetType ())
        let sw = System.Diagnostics.Stopwatch.StartNew ()
        if not (check basis createItem) then
            failwith (sprintf "failed. (%A)" createItemType)
        printf "%d\t\t%s\n" sw.ElapsedMilliseconds createItemType

module UnionViaTuple =
    type XList<'T> = Nil | Cons of 'T * XList<'T>
    let createItem n l = (Cons (n, l))

module UnionViaRecord =
    type xListData<'T> = { N : 'T;  L : xList<'T> }
    and xList<'T> = Nil | Cons of xListData<'T>
    let createItem n l = (Cons { N = n; L = l })

module UnionViaUnion =
    type xListData<'T> = Data of 'T * XList<'T>
    and XList<'T> = Nil | Cons of xListData<'T>
    let createItem n l = (Cons (Data (n, l)))

module UnionViaGeneicType =
    type Pair<'T,'U> = Pair of 'T * 'U
    type XList<'T> = Nil | Cons of Pair<'T, XList<'T>>
    let createItem n l = (Cons (Pair(n, l)))

module UnionViaStruct =
    [<Struct>]
    type xListData<'T>(n:'T,l:XList<'T>) =
        member __.N = n
        member __.L = l
    and XList<'T> = Nil | Cons of xListData<'T>
    let createItem n l = (Cons (xListData (n, l)))

module UnionViaGenericTypeStruct =
    [<Struct>]
    type xListData<'T, 'U>(n:'T,l:'U) =
        member __.N = n
        member __.L = l
    type XList<'T> = Nil | Cons of xListData<'T, XList<'T>>
    let createItem n l = (Cons (xListData (n, l)))

module RecordViaOption =
    type XList<'T> = { N : 'T; L : option<XList<'T>> }
    let createItem n l = Some { N = n; L = l }

Test.run UnionViaTuple.Nil             UnionViaTuple.createItem
Test.run UnionViaRecord.Nil            UnionViaRecord.createItem
Test.run UnionViaUnion.Nil             UnionViaUnion.createItem
Test.run UnionViaGeneicType.Nil        UnionViaGeneicType.createItem
#if DOESNT_WORK_ANYWHERE
Test.run UnionViaStruct.Nil            UnionViaStruct.createItem
Test.run UnionViaGenericTypeStruct.Nil UnionViaGenericTypeStruct.createItem
#endif
Test.run None                          RecordViaOption.createItem