6 people like it.
Like the snippet!

Generating numerical ranges

Different ways of generating numerical ranges in F#. It turns out that the built-in syntax generates fairly slow code, so the snippet shows two alternative ways that are faster. Any compiler optimizations making the built-in one faster would be nice :-)

 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: 
37: 
38: 
39: 
40: 
41: 
42:

// Using built-in sequence range
// (This takes about 3.5-4sec on my machine)
let s = seq { for i in 0L .. 10000000L -> i }
s |> Seq.length

// Using a range generated by an imperative loop
// using inline to make this more reusable
// (This takes about 0.5sec on my machine)
let inline range lo hi = 
  seq { let i = ref lo
        while i.Value < hi do
          yield i.Value
          i.Value <- i.Value + LanguagePrimitives.GenericOne }

range 0L 10000000L
|> Seq.length

// We can make this even faster if we just write the
// interface implementation directly. This is ugly, but
// it takes some 250ms on my machine...
open System.Collections
open System.Collections.Generic

let inline range2 (lo:^T) (hi:^T) = 
  let one = LanguagePrimitives.GenericOne
  { new IEnumerable< ^T > with
      member x.GetEnumerator() =
        let current = ref (lo - one)
        { new IEnumerator< ^T > with
            member x.Current = current.Value
          interface IEnumerator with
            member x.Current = box current.Value
            member x.MoveNext() = 
              if current.Value > hi then false
              else current.Value <- current.Value + one; true
            member x.Reset() = current.Value <- lo - one
          interface System.IDisposable with
            member x.Dispose() = ()  }
    interface IEnumerable with
      member x.GetEnumerator() = (x :?> IEnumerable< ^T >).GetEnumerator() :> _ }

range2 0L 10000000L |> Seq.length

val s : seq<int64>

Full name: Script.s

Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>

val i : int64

module Seq

from Microsoft.FSharp.Collections

val length : source:seq<'T> -> int

Full name: Microsoft.FSharp.Collections.Seq.length

val range : lo:'a -> hi:'a -> seq<'a> (requires member ( + ) and comparison and member get_One)

Full name: Script.range

val lo : 'a (requires member ( + ) and comparison and member get_One)

val hi : 'a (requires member ( + ) and comparison and member get_One)

val i : 'a ref (requires member ( + ) and comparison and member get_One)

Multiple items
val ref : value:'T -> 'T ref

Full name: Microsoft.FSharp.Core.Operators.ref

--------------------
type 'T ref = Ref<'T>

Full name: Microsoft.FSharp.Core.ref<_>

property Ref.Value: 'a

module LanguagePrimitives

from Microsoft.FSharp.Core

val GenericOne<'T (requires member get_One)> : 'T (requires member get_One)

Full name: Microsoft.FSharp.Core.LanguagePrimitives.GenericOne

namespace System

namespace System.Collections

namespace System.Collections.Generic

val range2 : lo:'T -> hi:'T -> IEnumerable<'T> (requires member ( - ) and comparison and member ( + ) and member get_One)

Full name: Script.range2

val lo : 'T (requires member ( - ) and comparison and member ( + ) and member get_One)

val hi : 'T (requires member ( - ) and comparison and member ( + ) and member get_One)

val one : 'a (requires member get_One and member ( - ) and member ( + ) and comparison)

Multiple items
type IEnumerable =
member GetEnumerator : unit -> IEnumerator

Full name: System.Collections.IEnumerable

--------------------
type IEnumerable<'T> =
member GetEnumerator : unit -> IEnumerator<'T>

Full name: System.Collections.Generic.IEnumerable<_>

val x : IEnumerable<'T> (requires member ( - ) and comparison and member ( + ) and member get_One)

IEnumerable.GetEnumerator() : IEnumerator<'T>

val current : 'T ref (requires member ( - ) and comparison and member ( + ) and member get_One)

Multiple items
type IEnumerator =
  member Current : obj
  member MoveNext : unit -> bool
  member Reset : unit -> unit

Full name: System.Collections.IEnumerator

--------------------
type IEnumerator<'T> =
  member Current : 'T

Full name: System.Collections.Generic.IEnumerator<_>

val x : IEnumerator<'T> (requires member ( - ) and comparison and member ( + ) and member get_One)

property IEnumerator.Current: 'T

property Ref.Value: 'T

val x : IEnumerator

property IEnumerator.Current: obj

val box : value:'T -> obj

Full name: Microsoft.FSharp.Core.Operators.box

IEnumerator.MoveNext() : bool

IEnumerator.Reset() : unit

type IDisposable =
member Dispose : unit -> unit

Full name: System.IDisposable

val x : System.IDisposable

System.IDisposable.Dispose() : unit

val x : IEnumerable

IEnumerable.GetEnumerator() : IEnumerator

Raw view Test code New version

More information

Link:	http://fssnip.net/no
Posted:	10 years ago
Author:	Tomas Petricek
Tags:	range , sequences