3 people like it.
Like the snippet!

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:

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=[] do
//    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

Previous Version Next Version Raw view Test code New version

More information

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