CODEWITHSUNDEEP
f#ienumerablesequence
Jesse Carter
Jesse Carter

Reputation: 21147

patterns for sequence "reverse-engineering"

Was wondering if there are any established patterns for this or even functions available in the core or 3rd party libraries that support this?

I've written a complex sequence using the seq expression that takes a start time and a list of rules dictating when certain events are allowed to occur on the time line going forward to create an infinite sequence. It's easy to supply any starting DateTime value and just begin stepping forward. The resulting sequence is seq <DateTime> corresponding to the timestamped events.

What I would like to do is be able to go backwards on this theoretical timeline of events. I want to be able to say "go back ten steps and give me that DateTime" so that I know if I were to apply the result to the original sequence as input I would end up back where I started.

Will I have to just reverse the complex logic in order to make that work? Or would there be a way that I can efficiently "brute force" my forward logic such that I could keep supplying inputs until I get a result that correctly gives me 10 steps till a specified DateTime?

I realize I'm doing a poor job of explaning this so maybe a simplified example to help visualize what I'm after. Suppose I have generated a sequence of ints using some logic pattern. Let's just say multiples of 2 to keep it simple:

let seq = [ 2; 4; 6; 8; 10; 12; 14; 16; 18; 20; ]

(It's a lazily generated sequence using my predefined logic though)

I can start generating this sequence from any of the values inside it easily, so given 12 I can keep going forward

let seqFrom12 = [ 12; 14; 16; 18; 20; ]

I want to be able to, for any possible value of the sequence calculate the value I would need to supply so that X steps would take me to another value in the sequence.

So I want all the values of the sequence so that X = 3 more steps will take me to the value 12 in the sequence. So I would need to count back to 10, then 8, then 6. Only in the real scenario it's much harder to apply the reverse logic

Upvotes: 2

Views: 588

Answers (2)

Dom
Dom

Reputation: 329

I wondered if a more simple solution to the problem would be to keep a dictionary of history along side your sequence of dates and actions. The key could be the date and the value could be the value passed in through the pipeline at the time. Then you don't need to reverse back you can just go back based on the date.

Upvotes: 0

Tomas Petricek
Tomas Petricek

Reputation: 243041

This is not really a question for SO. Not even for a blog post, but realistically, for an interesting academic paper. But one important piece of information is missing - are you writing the sequence expressions yourself, or do you just get a sequence of dates (without knowing how it was constructed)?

In the second case, you really cannot do much. You'll have to use some AI or machine learning techniques to basically implement a prediction algorithm that'll try to guess the previous number from the ones you sampled.

In the first case, you might be able to do something by moving away from seq<'T> and instead using your own data type that supports going both forward and backward. For example, something like this:

type BiSeq<'T> =
  { Next : unit -> BiSeq<'T> 
    Prev : unit -> BiSeq<'T> 
    Current : 'T }

Given a BiSeq<'T> value, we can get the current one, next sequence and also sequence starting from the previous point. Basic implementation always returns the same value:

let rec always n = 
  { Current = n
    Prev = fun () -> always n
    Next = fun () -> always n }

Or, you can write a function that takes BiSeq<'T> and does something to it. For example, we can increment the current value by 0, previous by -2 and next by +2. More generally:

let rec add by start c = 
  { Current = c.Current + start
    Next = fun () -> add by (start+by) (c.Next())
    Prev = fun () -> add by (start-by) (c.Next()) }

This lets you compose bidirectional sequences like a sequence of even numbers:

let evens = add 2 0 (always 0)
evens.Next()                        // 2
evens.Next().Next()                 // 4
evens.Next().Next().Next()          // 6
evens.Next().Next().Next().Prev()   // 4
evens.Prev()                        // -2

Now you have a sequence that lets you move in both directions! To implement anything realistic based on this idea, you'll probably need to add some form of caching and a lot of other primitives. But it might be an interesting direction!

Upvotes: 8

Related Questions