Back to Questions
893
views3
comments
List Processing - Find a repeating/recurring set of values in a list/sequence
f#

Just started with F#/Functional Programming and would like some ideas in searching for repeating patterns in a list.

Use Case:

Given a list/array/sequence of dates and max temperatures for each date I'd like to extract out the dates on which them temp is greater than a given threshold for n consecutive days.

(I'm trying to think of a non procedural approach to solving this).

Any suggestions/guidance would be helpful. Pointers to other resources (books; forums etc) on this would also be appreciated.

TIA,

Brencam

.

Hi,

can you please explain what exactly you like to see?

For example: lets say (I strip the days - just think of them sorting and ascending) you have something like 20,21,18,22,23,20,19,20,21,20,20,...

And you set the threshold at 19 for 2 days - so do you want to see output days of (0,3,4,7,8,9,...) or (0,3,7,...) ?

Anyhow: you can just take your imperative aproach and convert it to a recursive function (just push the local variables you change into the parameter list) and then go on from there (make it tail recursive, etc.)

This is the result of a quick try using this technique:

1
2
3
4
5
6
7
8
9
10
11
12

 

    let findConsecutiveIndizesAboveThreshold threshold nrDays values =
        let rec inner index ls cur acc =
            let i0,days = cur
            let nextAcc() = if days >= nrDays then i0::acc else acc
            match ls with
            | [] -> nextAcc()
            | l::ls' -> if l > threshold 
                        then (inner (index + 1) ls' (i0,days+1) acc) 
                        else (inner (index + 1) ls' (index + 1, 0) (nextAcc()))
        List.rev <| inner 0 (List.ofSeq values) (0,0) []

It will create the second option mentioned by me

By on 3/9/2011 10:55 PM ()

Thx for the response - just to clarify - I was primarily interested in identifying the initial date/event/occurence in each sequence (everything else can the be easily derived from that). So your response (0,3,7) is exactly what I'm after.

I'll need to mull over the code you posted for a while so that I can grasp the FP approach here. But thanks a lot for getting me started.

(FWW/FYI - Some time ago in a previous job I managed to extract this type of result from db tables using SQL queries - but that's another story <g>!)

By on 3/10/2011 12:23 AM ()

Ok,

I guess I should have made some more comments on the code.

First the name is somewhat ... well it happens if you rename something without looking twice - sorry.

The "inner" function is a technique you see a lot - it's just to hide some implementation-details with the parameters, so the last line is just a call to this inner function with the right parameters.

The parameters of "inner" are

  • index: just the current index - it's just incremented and passed with each step
  • ls: the (remaining) list of values to be processed
  • cur: the current state - it's a tuple with the first entry beeing the index of the begining of the current "run" and the second entry is the length of the run (run meaning consec. values greater than the threshold)
  • acc: is the obligatory accumulator where I pass in the found results - as I pass those in front of the list I have to reverse this list in the last line - this is more or less standard for recursive functions and you will see this a lot

The next lines are rather easy:

  • parse the cur value
  • nextAcc is just a helper function to create a new accumulator if we've got enogh values in cur

  • the match is standard for lists too

    • empty list just yields the "new" accumulator

    • if the list is not empty look at the current value and

      • pass on one more day in cur if the value is bigger than the threshold
      • create a new "run" if not and refresh the accumulator if the last run was "good"
By on 3/10/2011 12:47 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper