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 Head : '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

Full name: Script.merge_traditional
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

More information

Link:http://fssnip.net/4M
Posted:12 years ago
Author:Stephen Swensen
Tags: f# , recursion