I suggest forgetting about Seq and using idiomatic OCaml. You can represent your probability distribution as a function in a functional language. If you want to cache previous results then use a generic memoize combinator.

It may be possible to perform some analysis to detect when this can be done and get O(1) Seq.nth in those cases. Have a look at the Generator module in fslib/ienumerable.fs of the 1.9.2.9 version of the compiler and Don Syme's post in this thread for some examples.

The problem I can see though is that things like map and init_infinite still need to behave in a way which works with things like this....

1
2
3
4
5

#light

let do_evil_stuff() =
    let foo = ref 0
    Seq.init_infinite (fun i -> foo := !foo + 1; !foo * i)

IEnumerable wasn't really designed for random access, but rather it puts the 'seq' in sequential access.

I don't quite understand what you want to do. Perhaps you want to draw random samples from a probability distribution represented as an infinite sequence. This would be a good use of the seq type, e.g., to generate 10 random numbers from a Gaussian distribution: Seq.take 10 gauss. However in this scenario there is no practical reason why you'd want to access the nth element.

So perhaps you want to represent a finite probability distribution as a sequence of probability densities (but then I don't know why you'd need to call init_infinite). If the computation of individual elements in the sequence is expensive then you could get around that by having a sequence of lazy values, i.e., seq<lazy<float> >. But Seq.nth is still an expensive operation because it is linear in n. For this scenario it makes sense to represent the probability distribution as an array (which were designed for random access), perhaps even an array of lazy values. Array types implement IEnumerable so you can use them wherever you use seq, e.g., in the comprehension syntax.

- Greg

Hi Jeff

You could just implement the IEnumerable and IEnumerator interface yourself, like in the following example class, which provides access to the density of a uniform discrete distribution through both the Items and the Seq interfaces. In this case the IEnumerator interface simply relays all accesses to the Items interface, but in principle you could also compute the density recursively from some additional state or do something else fancy. If your distribution was mutable you would in addition have to make sure that enumerators get invalidated on modifications to the distribution.

In case you need more inspiration for your code a look at the F# sources in fslib/ienumerable.fs might help.

Best regards,
Stephan

--

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
43
44
45
46
47
48
49
50
51
52
53

#light
open System.Collections;
open System.Collections.Generic;
 
/// uniform distribution on {1, 2, ..., n} 
type UniformDiscreteDistribution = 
    class 
        val n: int 
        val d_: float 
        new(N) = if N <= 0 then invalid_arg "n must be positive"
                 { n = N; d_ = 1./float(N) } 
        member x.Item
            with get(i) = if i < 1 || i > x.n then not_found ()
                          x.d_         
        interface IEnumerable<float> with
            member x.GetEnumerator() =
                (new UniformDiscreteDistributionIterator(x) :> IEnumerator<float>)
        end
        interface IEnumerable with
            member x.GetEnumerator() = 
                (new UniformDiscreteDistributionIterator(x) :> IEnumerator)
        end
    end

and UniformDiscreteDistributionIterator = 
    class
        val distr_: UniformDiscreteDistribution;
        val mutable idx_: int;
        new(distr) = { distr_ = distr; idx_ = 0 }
        interface IEnumerator<float> with
            member x.Current = if x.idx_ > x.distr_.n then failwith "iterator out of bounds"
                               x.distr_.[x.idx_]
        end
        interface IEnumerator with
            member x.Current = box (x :> IEnumerator<float>).Current
            member x.MoveNext() = x.idx_ <- x.idx_ + 1
                                  if x.idx_ <= x.distr_.n then true
                                  else false
            member x.Reset() = x.idx_ <- 0 
        end
        interface System.IDisposable with 
            member x.Dispose() = ()
        end
     end
 
let () = let distr = new UniformDiscreteDistribution(10)
         for i = 1 to 10 do
             printf "%f " distr.[ i ];
         printf "\n"
         for d in distr do
             printf "%f " d;
         printf "\n"