How to avoid multiple iterations as a pattern?

Question

In functional languages (using F#), I am struggling to find a balance between the advantages of functional composition with single-responsibility and getting the performance of single iteration over sequences. Any code pattern suggestions / examples for achieving both?

I don't have a solid background in computational theory and I run into this general pattern over and over: Iterating over a collection and wanting to do side-effects while iterating to avoid further iterations over the same collection or its result set.

A typical example is a "reduce" or "filter" function: There are many times while filtering that I want to take an additional step based on the filter's result, but I'd like to avoid a second enumeration of the filtered results.

Let's take input validation as a simple problem statement:

1. Named input array
2. Piped to an "isValid" function filter
3. Side-effect: Log invalid input names
4. Pipe valid inputs to further execution

Problem Example

In F#, I might initially write:

inputs
// how to log invalid or other side-effects without messing up isValid??
|> Seq.filter isValid
|> execution

Solution Example #1

With an in-line side-effect, I need something like:

inputs
|> Seq.filter (fun (name,value) -> 
    let valid = isValid (name,value)
    // side-effect
    if not valid then
        printfn "Invalid argument %s" name
    valid
|> execution

Solution Example #2

I could use tuples to do a more pure separation of concerns, but requiring a second iteration:

let validationResults =
    inputs
    // initial iteration
    |> Seq.filter (fun (name,value) -> 
        let valid = isValid (name,value)
        (name,value,valid)
    |> execution

// one example of a 2nd iteration...
validationResults
|> Seq.filter (fun (_,_,valid) -> not valid)
|> Seq.map (fun (name,_,_) -> printfn "Invalid argument %s" name)
|> ignore

// another example of a 2nd iteration...
for validationResult in validationResults do
    if not valid then
        printfn "Invalid argument %s" name

Update 2014-07-23 per Answer

I used this as the solution per the answer. The pattern was to use an aggregate function containing the conditional. There are probably even more elegantly concise ways to express this...

open System

let inputs = [("name","my name");("number","123456");("invalid","")]

let isValidValue (name,value) =
    not (String.IsNullOrWhiteSpace(value))

let logInvalidArg (name,value) =
    printfn "Invalid argument %s" name

let execution (name,value) =
    printfn "Valid argument %s: %s" name value

let inputPipeline input =
    match isValidValue input with
    | true -> execution input
    | false -> logInvalidArg input

inputs |> Seq.iter inputPipeline

Answer 1

Following up on my other answer regarding composition of logging and other side-effects in F#, in this example, you can write a higher-level function for logging, like this:

let log f (name, value) =
    let valid = f (name, value)
    if not valid then
        printfn "Invalid argument %s" name
    valid

It has this signature:

f:(string * 'a -> bool) -> name:string * value:'a -> bool

So you can now compose it with the 'real' isValid function like this:

inputs
|> Seq.filter (log isValid)
|> execution

Since the isValid function has the signature name:'a * value:int -> bool it fits the f argument for the log function, and you can partially apply the log function as above.

Answer 2

This doesn't address your concern of iterating the sequence only once (which, for an array, is very cheap anyway), but is, I think, easier to read and clearer:

let valid, invalid = Array.partition isValid inputs
for name, _ in invalid do printfn "Invalid argument %s" name
execution valid