Recently I ran into a problem. I had to present a list of numbers that could either contain one, a limited amount or an infinite amount of numbers.
Normally, in a non functional language this would pose a big challenge. For example, the concept of an infinite list (in javascript) is something like:
function infinitelist() {
var list = [];
for (i = 0; i > 0; i++) {
list[i] = i;
}
return list;
}
Obviously, this would generate a overflow due to an infinite loop.
In F# sequences are lazy evaluated and can be constructed using computations. Meaning that a sequence can be defined by a computational expression like:
let allEvens =
let rec loop x = seq { yield x; yield! loop (x + 2) }
loop 0
as the computation in this case is recursive without a base case, this represents an infinite loop. The result will be: 0, 2, 4, 6, ... infinity.
However, this code is possible because in F# the calculation of te actual values is deferred until they are actually needed. For example when the above code is called with:
for a in allEvens |> Seq.take 10 do
printfn "%A\n" a
10 numbers will be calculated and then printed resulting in a list of [0, 2, .. 10].
Infinite sequences need some special treatment. Searching an infinite sequence is a tricky business as this can result in an infinite loop, like:
allEvens |> Seq.find(fun n -> n = 3) |> printfn "%A";;
will take forever, the fact that there is no 3 in the list of even numbers can not be determined by the normal find procedure. A procedure that checks whether the the pickings from the list diverge from the number that is to be found is an algorithm that works, the important prerequisite is that the list is ordered.
let infiniteSequenceFind f i e (s: 'a seq) =
let rec find d nth =
match (s |> Seq.nth nth, s |> Seq.nth (nth + 1)) with
| (_, _) when s |> Seq.take nth |> Seq.exists(fun n -> (n |> f i) = e) -> i |> Some
| (s1, s2) when (s1 |> f i) < (s2 |> f i) -> None
| _ -> nth + d |> find (d + 100)
match s with
|_ when s |> Seq.isEmpty -> None
|_ when s |> Seq.head = i -> Some i
|_ -> find 1 0
let findBigRationalInInfinite n s = s |> infiniteSequenceFind (fun i s -> abs(s - i)) n 0N
The above code can be used to find a big rational in a lists, the algorithm stops when it realizes that is overshooting the number to find.
Another problem I had with infinite lists was that I had to generate lists that were or were not infinite depending on whether there was a maximum (and minimum) or not.
The following code gave the solution:
seq{ for v in (s |> Seq.takeWhile(fun x -> match max with |Some m -> x <= m |None -> true)) do
if (match min with |Some m -> v >= m |None -> true) then yield v else ignore v } |> Seq.cache
The trick was to nest the infinite list in a for loop that checked with the takeWhile method if the number exceeded a maximum. If no maximum is supplied the takeWhile function always returns true, yielding all the numbers in the infinite list. Otherwise the list is truncated by the maximum.
