Back to Questions
905
views5
comments
How code sequence for algorithm using e[i-1] with e[i] for output [i]?
f#

Its easy to write sequences when each output is a function of just one value of the sequence. But I'm stumped as to how to represent an algorithm where each output is computed from two or three sequential members of the sequence. Here is an image-processing example, where a row of pixels are blurred by averaging each pixel's brightness with the neighboring pixels:

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#light
/// Algorithm for weighted average of pixel with two neighbors.
/// p'[i ] = (p[i-1] + 2*p[i ] + p[i+1])/4, i in 0..maxI
/// To get the end-conditions to work, p[-1]=p[0] & p[maxI+1]=p[maxI]

type pixel = float
type row = pixel array

/// Last index of zero-based array
let lastIndex (ar:array<'a>) :int =
  ar.Length - 1

/// C#-like version:
/// Output row has same dimensions as input row.
let avgRowC (r:row) :row =
  let r2 = Array.create (r.Length) 0.0
  // Set up for first iteration.
  let mutable p0 = r.[0]  // p[i ], i=0
  let mutable pm1 = p0  // p[-1]=p[0]
  for j in 1 to r.Length do // NOTE: j = i+1
    let p1 =
      if j = r.Length then
        r.[j]  // p[i+1]
      else
        r.[lastIndex r]  // p[maxI+1]=p[maxI]
    let v = (pm1 + 2.0*p0 + p1) * 0.25
    r2.[j-1] <- v // p'[i ]
    // Next
    pm1 <- p0 // p[j-1]=p[i ]
    p0 <- p1  // p[j]=p[i+1]
  r2

 

/// F# array/sequence NOT WORKING version:
let avgRowA (r:row) (*:row*) =
  // Make a sequence with repeated final value.
  // p[0]..p[LAST], p[LAST]
  let rr = Seq.tail_cons r r.[lastIndex r]
  // Set up for first iteration.
  let mutable p0 = r.[0]  // p[i ], i=0
  let mutable pm1 = p0  // p[-1]=p[0]
  let mutable firstP = true
  // To get the third value, we iterate one extra time,
  // outputting nothing the first time.
  Seq.to_array
    (seq{
        for p in r do
          let p1 = p  // p[i+1]
          if firstP then
            firstP <- false // *** SYNTAX ERROR ***
            // yield nothing the first iteration!
          else
            yield ((pm1 + 2.0*p0 + p1) * 0.25)
          // Next
          pm1 <- p0 // p[j-1]=p[i ]
          p0 <- p1  // p[j]=p[i+1]
     })

I have yet to come close to getting sequence code that works; I suspect that I don't understand the syntax required inside a "seq{}". Besides, I'm probably on the wrong track anyway ;]

.

If you're only interested in sequential variables (ie n, n-1, n-2) and not values which are far apart, you may use buffer variables as follow. For values which are more distant you may want to use a data structure buffer such as an array... but depending on how far you must go, you may want to use a data structure different from seq (eg transforming it into an array and then back to a seq).

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
26
27
28
29
30
31

 

#light

let x = seq {1 .. 100}

let f x = 
  { let ok, a, b, c = 
      match Seq.take 3 x with
      | a :: b :: c :: _ ->true, ref a, ref b, ref c
      | _ -> false, ref 0, ref 0, ref 0
 
    if ok then
      let flag = ref 0
      for value in x do
        if !flag >= 3 then
          
          //make up the value
          let to_yield = value * a % b + c

          //update buffer variables
          do a := b
          do b := c
          do c := value

          yield to_yield
        else
          do incr flag
          //don't yield anything
  }
By on 4/4/2008 2:46 AM ()

Thread about a similar problem [link:cs.hubfs.net]

By on 4/4/2008 8:08 AM ()

Thanks brian, julien, gneverov -- each of those responses taught me something about sequences. Here is my working version:

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

 
#light
/// Fantasy version (notation borrowed from mathematical induction):
//  Given: (f3  p @i-1  p @i  p @i+1)
//  let applyRow f3 (r:'a seq) => (r':'a seq) =
//    for i in seq_index(r)
//      // NOTE: pm1 & p1 are not independent variables --
//      // they are just shorthand for earlier & later versions of p0,
//      // combined with special cases on First / Last elements.
//      // That is why p1 can meaningfully refer to "@i+1".
//      // It is that need to look one ahead that leads to
//      // the implementation delaying output by one loop.
//      induce p0 = r.[i ]
//      and pm1 @i= p0 @i-1 except pm1 @First= p0 @First
//      and p1 @i= p0 @i+1 except p1 @Last= p0 @Last
//      do
//        out r'.[i ] = f3 pm1 p0 p1

type rowQ = pixel seq

/// F# sequence version (hand-translation of fantasy notation):
/// Given: (f3 r[i-1] r[i ] r[i+1])
/// Values on either end are considered repeated past the limits.
let applyRowQ f3 (r:rowQ) :rowQ =
  seq{
      let pm1 = ref 999. // Initial value not used in computation.
      let p0 = ref 999.  // Initial value not used in computation.
      let p1 = ref 999.  // Initial value not used in computation.
      let firstP = ref true
      for p in r do
        do p1 := p  // r[i ] but acts as r[i+1] given out delay
        if !firstP then
          // NOTE: "Next" logic will transfer this to pm1.
          do p0 := !p1 // r[-1]=r[0], one iter before use
          do firstP := false
          // yield nothing the first iteration
        else
          yield (f3 !pm1 !p0 !p1) // out r'[i-1]; one loop delay
        // Next index i'=i+1
        do pm1 := !p0 // r[i'-1]==r[i ]
        do p0 := !p1  // r[i']==r[i+1]
        
      if not !firstP then // Non-empty sequence.
        // Relies on final "Next" to slide values into pm1 & p0.
        yield (f3 !pm1 !p0 !p1) // Final value (p1 is repeated)
  }

/// blur3 r[i-1] r[i ] r[i+1]
let blur3 pm1 p0 p1 = (pm1 + 2.0 * p0 + p1) * 0.25

let avgRowQ (r:rowQ) :rowQ = applyRowQ blur3 r

/// Usage: anything |> pam "msg"
let pam msg a = printfn "%A <-- %s" a msg

// -> [2.; 5.; 5.5; 6.; 7.5]
seq[ 0.; 8.; 4.; 6.; 8. ] |> avgRowQ |> pam "avgRowQ [ 0.; 8.; 4.; 6.; 8. ]"
seq[ 1.; 1.; 1.; 1. ] |> avgRowQ |> pam "avgRowQ [ 1.; 1.; 1.; 1. ]"  // identity x4
seq[ 1.; 2.; 3. ] |> avgRowQ |> pam "avgRowQ [ 1.; 2.; 3. ]"  // [1.25; 2.0; 2.75]
seq[ -50.; -54. ] |> avgRowQ |> pam "avgRowQ [ -50.; -54. ]"  // [-51.; -53.]
seq[ 50. ] |> avgRowQ |> pam "avgRowQ [ 50. ]"  // [50.]
seq[] |> avgRowQ |> pam "avgRowQ []"  // []

printf "----- Press any key. -----"
System.Console.ReadKey(false) |> ignore
By on 4/4/2008 10:56 AM ()

The fantasy pseudo-logic shows what I am thinking.

The seq implementation in "applyRowQ" shows what I would manually translate that into. The fundamental principle is that in each iteration, the "induction variables" be set based solely on values from the previous iteration; e.g. the mathematical induction model.
(the particular example here isn't inductive; p[i+1] is independent of p[i ]. However, the notation would work even if there were feedback (induction) in generating the sequence of p's.)

A functional purist might recoil at the use of ref variables in that version.
Specifically, there is a potential for error in three places:
A. p1 is set inside the do loop. It isn't immediately obvious that this is essentially a functional "let" -- its a ref so that the final value can be used outside the loop. Ideally, the ref variables would not be set inside the loop at all, as the intent is that the interior be demonstrably functional.
B. p0 is set to !p1 under one condition. If this were done prior to p1 being set, the value of p1 prior to the loop would be used, which is not part of the induction model.
C. In the "Next index" portion, if the order of pm1 and p0 ":=" lines were switched, pm1 would get the wrong version of p0, breaking the induction abstraction.

Two observations about that use of refs:

1. If I have correctly hand-translated my inductive logic, then in theory a prover could prove that this is equivalent to that inductive logic, hence is functional. It would be wonderful to have such a prover; even better would be to have a language compiler that performed the translation from the safe induction form to the ref-using form, as an implementation optimization.

2. Use of local mutables that aren't passed outside of scope is relatively safe (w.r.t. not breaking design models); the real problem with mutable values in current mainstream programming is the contamination of code/state in one place by code/state in another place: the difficulty of composing many simple algorithms into a complex system without introducing unexpected inconsistencies. Use of local mutables can be demonstrated to be sound via unit tests; as long as an entity behaves functionally (viewed from outside) under all circumstances, composition is unharmed.

By on 4/4/2008 4:16 PM ()

I don't know that this is exactly what you're looking for, but here's one thing that springs to mind...

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
26
27
28
29
30
31
32
33

let window3 (f : option<'a> -> option<'a> -> option<'a> -> 'b) (s : #seq<'a>) =
    let x, y, z = ref None, ref None, ref None
    seq { for e in s do
              do x := !y
              do y := !z
              do z := Some e
              yield f !x !y !z
          do x := !y
          do y := !z
          do z := None
          yield f !x !y !z
          do x := !y
          do y := !z
          do z := None
          yield f !x !y !z
        }

let smooth x y z =
    match x, y, z with
    | None, None, Some z -> z
    | None, Some y, Some z -> (y + z) / 2.0
    | Some x, Some y, Some z -> (x + 2.0 * y + z) / 4.0
    | Some x, Some y, None -> (x + y) / 2.0
    | Some x, None, None -> x
    | _ -> failwith "bad call"

let a = [4.0; 8.0; 12.0; 8.0; 12.0; 8.0; 12.0; 8.0; 4.0]
let ans = window3 smooth a
for x in ans do
   printf "%A  " x
printfn ""
By on 4/4/2008 12:45 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