Fork me on GitHub

Code Snippet:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#load @"Utils/ListLazy.fs"

open Stermon.Research.Utils

let corruptStartPoint l =
  let rec loopStart = function
    | Cons(h1,t1),Cons(h2,t2) -> (h1 = h2) |> function
      | true -> Some h1
      | false ->
        loopStart (t1.Force(),t2.Force())
    | _,_ -> None
  let rec meetPoint = function
    | Cons(h1,t1),Cons(h2,t2) -> (h1 = h2) |> function
      | true -> loopStart (l,t2.Force())
      | false ->
        meetPoint (t1.Force(),(t2.Force() |> List.Lazy.skip 1I))
    | _,_ -> None
  meetPoint (l,(l |> List.Lazy.skip 1I))

Code output:

[Loading Utils/ListLazy.fs]

namespace FSI_0002.Stermon.Research.Utils
  type 'a ListLazy =
    | Cons of 'a * Lazy<'a ListLazy>
    | Nil
  module Lazy = begin
    val single : h:'a -> 'a ListLazy
    val cons : h:'a -> l:'a ListLazy -> 'a ListLazy
    val head : _arg1:'a ListLazy -> 'a
    val tail : _arg1:'a ListLazy -> 'a ListLazy
    val iter : f:('a -> unit) -> _arg1:'a ListLazy -> unit
    val map : f:('a -> 'b) -> _arg1:'a ListLazy -> 'b ListLazy
    val fold : f:('a -> 'b -> 'a) -> init:'a -> _arg1:'b ListLazy -> 'a
    val foldBack :
      f:('a -> Lazy<'b> -> 'b) -> init:'b -> _arg1:'a ListLazy -> 'b
    val unfold : f:('a -> ('b * 'a) option) -> init:'a -> 'b ListLazy
    val reduce : f:('a -> 'a -> 'a) -> _arg1:'a ListLazy -> 'a
    val reduceBack : f:('a -> Lazy<'a> -> 'a) -> _arg1:'a ListLazy -> 'a
    val skip :
      n:System.Numerics.BigInteger -> _arg1:'a ListLazy -> 'a ListLazy
    val take :
      n:System.Numerics.BigInteger -> _arg1:'a ListLazy -> 'a ListLazy
    val append : l1:'a ListLazy -> l2:'a ListLazy -> 'a ListLazy
    val concat : _arg1:'a ListLazy ListLazy -> 'a ListLazy
    val ofList : _arg1:'a list -> 'a ListLazy
    val toList : l:'a ListLazy -> 'a list
  end

val corruptStartPoint :
  l:'a Stermon.Research.Utils.ListLazy -> 'a option when 'a : equality

Non corrupt linked list

All

1
2
3
4
5
6
let example1 = List.Lazy.unfold(fun s -> Some(s,s+1)) 0 |> List.Lazy.take 26I

example1
|> List.Lazy.iter(printf "%i ")

corruptStartPoint example1
> val example1 : int ListLazy = Cons (0,Value is not created.)
> 0 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 val it : unit = ()
> val it : int option = None

Corrupt linked list

All

1
2
3
4
5
6
7
8
9
10
11
12
13
let corruptGenerator n =
  List.Lazy.unfold(
    fun s -> (s < n) |> function
    | false -> Some((s % n) + n,s+1)
    | true  -> Some(s,s+1)) 0

let example2 = corruptGenerator 7

example2
|> List.Lazy.take 28I
|> List.Lazy.iter(printf "%i ")

corruptStartPoint example2
> val corruptGenerator : n:int -> int ListLazy
> val example2 : int ListLazy = Cons (0,Value is not created.)
> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 8 9 10 11 12 13 7 8 9 10 11 12 13 val it : unit = ()
> val it : int option = Some 7

References:

comments powered by Disqus