// https://www.fewbutripe.com/2018/12/05/seemingly-impossible.html type Bit = | Zero = 0 | One = 1 /// An infinite sequence of bits. type BitSequence = { /// Answers the bit at the given index. Article calls this "atIndex". Item : uint32 -> Bit } [] [] module BitSequence = /// Creates a bit sequence with the given lookup function. let create f = { Item = f } /// Dumps the beginning of the given sequence to the console. let dump (seq : BitSequence) = [0u .. 10u] |> Seq.iter (fun i -> printfn "%d: %A" i seq.[i]) /// Prepends the given bit to the given lazy sequence. let (++) bit (lseq : Lazy) = create (fun i -> if i = 0u then bit else lseq.Value.[i - 1u]) // don't reify the given sequence until we have to /// Finds a sequence for which the given predicate is true. /// Warning: answers garbage sequence if no such sequence exists. let rec find (pred : BitSequence -> bool) = let zeroPred seq = pred (Bit.Zero ++ lazy seq) if exists zeroPred then Bit.Zero ++ lazy (find zeroPred) else let onePred seq = pred (Bit.One ++ lazy seq) Bit.One ++ lazy (find onePred) /// Is there a sequence for which the given predicate is true? Article calls this "anySatisfy". and exists pred = let lseq = lazy (find pred) let seq = create (fun i -> lseq.Value.[i]) pred seq /// Do all sequences satisfy the given predicate? Article calls this "allSatisfy". and forall pred = pred >> not |> exists |> not /// Equality of functions that have BitSequence as their domains. let (==) (f1 : BitSequence -> 'a) (f2 : BitSequence -> 'a) = forall (fun seq -> f1 seq = f2 seq) let oneOnFirstFiveEvens () = let seq = BitSequence.find (fun seq -> seq.[0u] = Bit.One && seq.[2u] = Bit.One && seq.[4u] = Bit.One && seq.[6u] = Bit.One && seq.[8u] = Bit.One) BitSequence.dump seq let equality () = let f (seq : BitSequence) = int seq.[1u] * int seq.[2u] let g (seq : BitSequence) = int seq.[1u] + int seq.[2u] printfn "f = f: %A" (f == f) printfn "g = g: %A" (g == g) printfn "f = g: %A" (f == g) let h (seq : BitSequence) = match seq.[1u], seq.[2u] with | Bit.One, Bit.One -> 1 | _ -> 0 printfn "f = h: %A" (f == h) printfn "g = h: %A" (g == h) let k (seq : BitSequence) = ((int seq.[1u] + int seq.[2u] + 908) % 6) / 4 printfn "f = k: %A" (f == k) printfn "g = k: %A" (g == k) printfn "h = k: %A" (h == k) [] let main argv = oneOnFirstFiveEvens () printfn "" equality () 0