CODEWITHSUNDEEP
f#tuplesimmutability
knocte
knocte

Reputation: 17939

Process a stream of Tuples without mutability?

So I want a function that receives an array of Tuple<int,int> and returns the same type but with different values.

What I want to do is a function that returns this kind of values:

f( [1,10; 2,20; 3,40; 4,70] ) = [2,10; 3,20; 4,30]

So as you can see, the first number is basically unchanged (except the 1st item is not picked), but the last number is the substraction of the current number with the previous number (20 - 10 = 10, 40 - 20 = 20, ...).

I've tried to come up with an algorithm in F# that doesn't involve mutability (using an accumulator for the previous value would mean I need a mutable variable), but I can't figure out. Is this possible?

Upvotes: 2

Views: 376

Answers (4)

S&#248;ren Debois
S&#248;ren Debois

Reputation: 5688

Mark and Tomas have given really good solutions for the specific problem. Your question had a statement I think warrants a third answer, though:

(using an accumulator for the previous value would mean I need a mutable variable)

But this is actually not true! List.fold exists exactly to help you process lists with accumulators in a functional way. Here is how it looks:

let f xs = List.fold (fun (y, ys) (d, x) -> x, (d, x-y) :: ys)
                      (snd (List.head xs), [])
                      (List.tail xs)
           |> snd |> List.rev

The accumulator here is the argument (y, ys) to the fun ... in the first line. We can see how the accumulator updates to the right of the ->: we accumulate both the previous element of the list x, as well as the new list we're constructing (d, x-y)::xs. We'll get that list in reverse order, so we reverse it in the end with List.rev.

Incidentally, List.fold is tail-recursive.

Of course, Tomas and Mark's solutions using Seq.pairwise are much neater for your particular problem, and you'd definitely want to use one of those in practice.

Upvotes: 2

Mau
Mau

Reputation: 14468

Whenever we need to create a sequence from another sequence, where one element in the output is a function of its predecessors, scan (docs) comes in handy:

[1,10; 2,20; 3,40; 4,70]
    |> List.scan (fun ((accA, accB), prevB) (elA, elB) -> ((elA, elB-prevB), elB)) ((0, 0), 0)
    |> Seq.skip 2
    |> Seq.map fst

yields:

[(2, 10); (3, 20); (4, 30)]

Upvotes: 0

Tomas Petricek
Tomas Petricek

Reputation: 243051

Using built-in functions. In this case, you can use Seq.pairwise. The function takes a sequence of inputs and produces a sequence of pairs containing the previous value and the current value. Once you have the pairs, you can use Seq.map to transform the pairs into the results - in your case, take the ID of the current value and subtract the previous value from the current value:

input 
|> Seq.pairwise 
|> Seq.map (fun ((pid, pval), (nid, nval)) -> nid, nval-pval)

Note that the result is a sequence (IEnumerable<T>) rather than a list - simply because the Seq module contains a few more (useful) functions. You could convert it back to list using List.ofSeq.

Using explicit recursion. If your task did not fit one of the common patterns that are covered by some of the built-in functions, then the answer would be to use recursion (which, in general, replaces mutation in the functional style).

For completeness, the recursive version would look like this (this is not perfect, because it is not tail-recursive so it might cause stack overflow, but it demonstrates the idea):

let rec f list = 
  match list with
  | (pid, pval)::(((nid, nval)::_) as tail) ->
      (nid, nval-pval)::(f tail)
  | _ -> []

This takes a list and looks at the first two elements of the list (pid, pval) and (nid, nval). Then it calculates the new value based on the two elements in (nid, nval-pval) and then it recursively processes the rest of the list (tail), skipping over the first element. If the list has one or fewer elements (the second case), then nothing is returned.

The tail-recursive version could be written using the "accumulator" trick. Instead of writing newValue::(recursiveCall ...) we accumulate the newly produced values in a list kept as an argument and then reverse it:

let rec f list acc = 
  match list with
  | (pid, pval)::(((nid, nval)::_) as tail) ->
      f tail ((nid, nval-pval)::acc)
  | _ -> List.rev acc

Now you just need to call the function using f input [] to initialize the accumulator.

Upvotes: 8

Mark Seemann
Mark Seemann

Reputation: 233150

> let values = [(1, 10); (2, 20); (3, 40); (4, 70)];;
val values : (int * int) list = [(1, 10); (2, 20); (3, 40); (4, 70)]

> values
  |> Seq.pairwise
  |> Seq.map (fun ((x1, y1), (x2, y2)) -> (x2, y2 - y1))
  |> Seq.toList;;
val it : (int * int) list = [(2, 10); (3, 20); (4, 30)]

Seq.pairwise gives you each element in a sequence as a pair, except the first element, which is only available as the predecessor of the second element.

For example:

> values |> Seq.pairwise |> Seq.toList;;
val it : ((int * int) * (int * int)) list =
  [((1, 10), (2, 20)); ((2, 20), (3, 40)); ((3, 40), (4, 70))]

Second, Seq.map maps each of these pairs of pairs by using the desired algorithm.

Notice that this uses lazy evaluation - I only used Seq.ToList at the end to make the output more readable.

BTW, you can alternatively write the map function like this:

Seq.map (fun ((_, y1), (x2, y2)) -> (x2, y2 - y1))

Notice that instead of x1 is replaced with _ because the value isn't used.

Upvotes: 4

Related Questions