3 people like it.

# Abstraction of the "tail-recursive loop" pattern

A novel, due to performance inadequacy, abstraction of the "tail-recursive loop" pattern. Approaching what a built-in language feature might look like.

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: ``` ``````type loop<'a,'b> = | Return of 'a | Loop of 'b let rec loop vars f = match f vars with | Return result -> result | Loop vars -> loop vars f //Examples: //input lists let xl, yl = List.init (2000000) id, List.init (2000000) (~-) //merge xl and yl using loop abstraction //fastest run: Real: 00:00:00.921, CPU: 00:00:00.921, GC gen0: 21, gen1: 12, gen2: 0 let merge = loop (xl, yl, []) (fun (xl,yl,acc) -> match xl, yl with | [], _ | _, [] -> Return acc //ommitting reversal of acc to keep time stats pure | x::xl, y::yl -> Loop(xl,yl,(x,y)::acc)) //merge xl and yl using traditional pattern. //fastest run: Real: 00:00:00.434, CPU: 00:00:00.437, GC gen0: 11, gen1: 7, gen2: 0 let merge_traditional = let rec loop xl yl acc = match xl, yl with | [], _ | _, [] -> acc //ommitting reversal of acc to keep time stats pure | x::xl, y::yl -> loop xl yl ((x,y)::acc) loop xl yl [] //merge using a possible built-in language feature: //let merge = // loop xl=xl yl=yl acc=[] with // match xl, yl with // | [], _ | _, [] -> acc // | x::xl, y::yl -> loop xl yl ((x,y)::acc) ``````
union case loop.Return: 'a -> loop<'a,'b>
union case loop.Loop: 'b -> loop<'a,'b>
Multiple items
val loop : vars:'a -> f:('a -> loop<'b,'a>) -> 'b

Full name: Script.loop

--------------------
type loop<'a,'b> =
| Return of 'a
| Loop of 'b

Full name: Script.loop<_,_>
val vars : 'a
val f : ('a -> loop<'b,'a>)
val result : 'b
val xl : int list

Full name: Script.xl
val yl : int list

Full name: Script.yl
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val init : length:int -> initializer:(int -> 'T) -> 'T list

Full name: Microsoft.FSharp.Collections.List.init
val id : x:'T -> 'T

Full name: Microsoft.FSharp.Core.Operators.id
val merge : (int * int) list

Full name: Script.merge
val xl : int list
val yl : int list
val acc : (int * int) list
val x : int
val y : int
val merge_traditional : (int * int) list

Multiple items
val loop : ('a list -> 'b list -> ('a * 'b) list -> ('a * 'b) list)

--------------------
type loop<'a,'b> =
| Return of 'a
| Loop of 'b

Full name: Script.loop<_,_>
val xl : 'a list
val yl : 'b list
val acc : ('a * 'b) list
val x : 'a
val y : 'b