CODEWITHSUNDEEP
recursionf#functional-programming
Aidan
Aidan

Reputation: 4891

When building list recursively, how to use created elements of list at the head?

I am trying to write a bootstrap algorithm in F# that takes a collection of inputs and creates a list of outputs. If I only need to use the previous element it is straightforward to use recursion :

let buildElement head previous =
    // do something to create new float 
    1.0

let buildList inputs =
    let rec bootstrap elements previous = 

        let addElement head tail =
            let newElement = buildElement head previous
            newElement :: bootstrap tail newElement   

        match inputs with
            | []    -> []
            | h::t  -> addElement h t
    bootstrap inputs 1.0

However, if I want to use the previously created elements (eg say I wanted to pass in an average of the new values as the previous value), how do I access them in the inner functions? Do I create a collection in the outer function and fill it up in the inner function? If so, do I need to make it mutable?

Upvotes: 1

Views: 172

Answers (3)

Don Stewart
Don Stewart

Reputation: 137947

if I want to use the previously created elements (eg say I wanted to pass in an average of the new values as the previous value), how do I access them in the inner functions?

This is a fold or scan (prefix fold). You're both mapping or collapsing a list into a new value, and accumulating a value that influences the result.

Upvotes: 0

Tomas Petricek
Tomas Petricek

Reputation: 243041

If you need to calculate the new value based on some information from the past values, you would essentially do the same thing as what you're doing now - instead of passing ingle last value in previous, the previous parameter could be a list of past values that you recalculate as you go.

I think it is difficult to give a better answer without knowing a specific example. However, say you wanted to calculate floating average - for that, you need the count and the sum of all previous values. You could encode that directly using recursion, or you can use Seq.scan:

[ 1.0 .. 100.0 ] 
|> Seq.scan (fun (count, sum) elem -> count + 1, sum + elem) (0, 0.0)
|> Seq.map (fun (count, sum) -> sum / float count)

Upvotes: 2

sepp2k
sepp2k

Reputation: 370112

In case of the average function you could pass the partial sum and the number of processed items around and use that calculate the average.

For a general solution, you can take the list of previous results as an argument, prepend the next result to it using :: and reverse the whole thing when you're done. This has the added benefit of making your function tail-recursive.

Upvotes: 0

Related Questions