1

I am looking for a type similar to sequences in F# where indices could be big integers, rather that being restricted to int. Does there exist anything like this? By "big integer indices" I mean a type which allows for something equivalent to that:

let s = Seq.initInfinite (fun i -> i + 10I)
user8171079
  • 337
  • 5
  • 16
  • 1
    Why would you ever need such big indexes? Use big integer only if numbers exceed `System.Int64.MaxValue`. If you'll use `int64` as index, then you will be able to index up to 9007199254740991 elements. If this is bytes, then you will be able to use 8_388_607 TBytes - as much as 8 millions of regular notebooks have. You don't need this – JL0PD Aug 11 '21 at 05:42

3 Answers3

2

The following will generate an infinite series of bigints:

let s = Seq.initInfinite (fun i -> bigint i + 10I)

What i suspect you actually want though is a Map<'Key, 'Value>.

This lets you efficiently use a bigint as an index to look up whatever value it is you care about:

let map = 
    seq {
        1I, "one"
        2I, "two"
        3I, "three"
    }
    |> Map.ofSeq

// val map : Map<System.Numerics.BigInteger,string> =
//   map [(1, "one"); (2, "two"); (3, "three")]

map.TryFind 1I |> (printfn "%A") // Some "one"
map.TryFind 4I |> (printfn "%A") // None
tranquillity
  • 1,619
  • 1
  • 5
  • 12
1

The equivalent of initInfinite for BigIntegers would be

let inf = Seq.unfold (fun i -> let n = i + bigint.One in Some(n, n)) bigint.Zero
let biggerThanAnInt = inf |> Seq.skip (Int32.MaxValue) |> Seq.head // 2147483648

which takes ~2 min to run on my machine.

However, I doubt this is of any practical use :-) That is unless you start at some known value > Int32.MaxValue and stop reasonably soon (generating less than Int32.MaxValue items), which then could be solved by offsetting the BigInt indexes into the Int32 domain.

Theoretically you could amend the Seq module with functions working with BigIntegers to skip / window / ... an amount of items > Int32.MaxValue (e.g. by repeatedly performing the corresponding Int32 variant)

CaringDev
  • 8,391
  • 1
  • 24
  • 43
0

Since you want to index into a sequence, I assume you want a version of Seq.item that takes a BigInteger as index. There's nothing like that built into F#, but it's easy to define your own:

open System.Numerics

module Seq =
    let itemI (index : BigInteger) source =
        source |> Seq.item (int index)

Note that no new type is needed unless you're planning to create sequences that are longer than 2,147,483,647 items, which would probably not be practical anyway.

Usage:

let items = [| "moo"; "baa"; "oink" |]

items
    |> Seq.itemI 2I
    |> printfn "%A"   // output: "oink"
Brian Berns
  • 15,499
  • 2
  • 30
  • 40
  • Actually what I need is precisely to generate sequences at indices greater than the `int` upper bound. I'll edit the question to clarify that. – user8171079 Aug 10 '21 at 21:19
  • F# sequences are lazy, which means you'd have to evaluate all the preceding values in order to get to the one you want. It sounds like you really want an array, which supports O(1) indexing? – Brian Berns Aug 10 '21 at 21:21
  • Can array indices be bigints? – user8171079 Aug 10 '21 at 21:24
  • See this SO question: [What is the maximum length of an array in .NET on 64-bit Windows](https://stackoverflow.com/questions/2338778/what-is-the-maximum-length-of-an-array-in-net-on-64-bit-windows). – Brian Berns Aug 10 '21 at 21:27