StackAllocatedLists.fs

type IList<'T> =
    abstract member Tail : #IListConsumer<'T,'R> -> 'R
    abstract member Head : 'T
    abstract member IsEmpty : bool

and IListConsumer<'T,'R> =
    abstract member Consume : #IList<'T> -> 'R

[<Struct>]
type Nil<'T> =
    interface IList<'T> with
        member this.Head = failwith "Empty"
        member this.IsEmpty = true
        member this.Tail k = failwith "Empty"

[<Struct>]
type Cons<'T,'L when 'L :> IList<'T>>(head: 'T, tail: 'L) =
    interface IList<'T> with
        member this.Head = head
        member this.IsEmpty = false
        member this.Tail k = k.Consume tail

let reverse list =
    let rec rev acc list =
        match list with
        | [] -> acc
        | x :: xs -> rev (x :: acc) xs
    rev [] list

[<Struct>]
type ListSum(sum: int) =
    member this.Consume(list: #IList<int>) =
        if list.IsEmpty then sum else
            list.Tail (ListSum(sum + list.Head))
    interface IListConsumer<int,int> with
        member this.Consume list = this.Consume list

[<Struct>]
type ListPrinter<'T> =
    interface IListConsumer<'T,int> with
        member this.Consume list =
            if list.IsEmpty then 0 else
                stdout.WriteLine list.Head
                list.Tail this
          
type Lists =  
    static member Reverse<'R,'T,'L1,'L2,'K when 'L1 :> IList<'T>
                                            and 'L2 :> IList<'T>
                                            and 'K :> IListConsumer<'T,'R>>
        (acc: 'L1) (list: 'L2) (k: 'K) =
        if list.IsEmpty
        then k.Consume acc
        else list.Tail (ListReverser(list.Head, acc, k))

    static member Sum (list: #IList<int>) =
        ListSum(0).Consume(list)

    static member ReverseSum (list: #IList<int>) =
        Lists.Reverse (Nil ()) list (ListSum(0))

    static member ReversePrint list =
        Lists.Reverse (Nil ()) list (ListPrinter())

and [<Struct>] ListReverser<'T,'R,'L,'K when 'L :> IList<'T>
                                         and 'K :> IListConsumer<'T,'R>>
    (head: 'T, acc: 'L, k: 'K) =
    interface IListConsumer<'T,'R> with
        member this.Consume tail = Lists.Reverse (Cons (head, acc)) tail k
    
#time
let r = ref 0

!r
for i in 1 .. 10000000 do
    let list = Cons(1, Cons(2, Cons(3, Cons (4, Cons (5, Nil())))))
    r := !r + Lists.ReverseSum list

for i in 1 .. 10000000 do
    let list = [1; 2; 3; 4; 5]
    r := !r + List.sum (List.rev list)