F# sequences with BigInteger indices

1
votes

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)
3
f#
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

3 Answers

2
votes

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
1
votes

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)

0
votes

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"