CODEWITHSUNDEEP
f#functional-programming
Ryan
Ryan

Reputation: 2051

How to improve this F# function

I am experienced in C# but new to F# and Functional Programming. Now I am trying to implement a class library in F#. Here is one of the functions: It takes a list of integers <=9 and change consecutive 9 like 9,9,9,9 to 9, 10, 11, 12. For example [9;9;9;1;4;0;1;9;9;9;9] will be changed to [9; 10; 11; 1; 4; 0; 1; 9; 10; 11; 12].

C# function is trivial:

void ReleaseCap(List<int> items)
{
    for (int i = 1; i < items.Count; i++)
    {
        var current = items[i];
        var previous = items[i - 1];
        //If curernt value = 9 and previous >=9, then current value should be previous+1
        if (current == 9 && previous >= 9)
        {
            items[i] = previous + 1;
        }
    }
}

Now is my F# tail recursive one. Instead of loop the List by index, it recursively move item from an initial list to an processed list until everything in the initial list is gone:

let releaseCap items =
    let rec loop processed remaining = //tail recursion
        match remaining with
        | [] -> processed //if nothing left, the job is done.
        | current :: rest when current = 9 -> //if current item =9
            match processed with
            // previous value >= 9, then append previous+1 to the processed list
            | previous :: _ when previous >= 9 -> loop (previous+1 :: processed) rest 
            //if previous < 9, the current one should be just 9
            | _ -> loop (current :: processed) rest 
        //otherwise, just put the current value to the processed list
        | current :: rest -> loop (current :: processed) rest 
    loop [] items |> List.rev

While the C# version is trivial and intuitive, the F# code is verbose and not as intuitive. Is there any part of the F# code can be improved to make it more elegant?

Upvotes: 4

Views: 131

Answers (3)

Helge Rene Urholm
Helge Rene Urholm

Reputation: 1188

I thought fold was the important one! :-)

So:

let list = [9;9;9;1;4;0;1;9;9;9;9] 

let incr acc e =
    match acc, e with
    | h::t, e when e = 9 && h >= 9 -> (h + 1)::acc 
    | _ -> e::acc 


list 
|> List.fold incr []
|> List.rev

//val it : int list = [9; 10; 11; 1; 4; 0; 1; 9; 10; 11; 12]

Upvotes: 2

Gus
Gus

Reputation: 26174

You can reuse existing functions in order to simplify your code. Normally when you change items in a list you think of a map but in this case you have something to remember from your previous computation which should be passed for each item, so you should aim to fold related functions.

Here's one: List.scan

let releaseCap items =
    items
        |> List.scan (fun previous current -> 
            if current = 9 && previous >= 9 then previous + 1
            else current) 0  
        |> List.tail

FP is not just about using recursion instead of loops. Recursion is typically used in basic and reusable functions, then by combining those functions you can solve complex problems.

NOTE: You are comparing your C# solution with your F# solution, but did you notice that apart from the language there is an important difference between both solutions? Your C# solution uses mutability.

Upvotes: 5

Jakub Lortz
Jakub Lortz

Reputation: 14896

In your C# code you correctly assume that the 1st element of the list will never change and start with the 2nd element.

If you include this in the F# code you can skip the match on accumulator. The result will be a bit simpler.

   let reduceCap l = 
    let rec reduceCapRec acc l =
        let previous = List.head acc
        match l with
        | x::xs -> 
            if x = 9 && previous >= 9 
            then reduceCapRec ((previous+1) :: acc) xs
            else reduceCapRec (x :: acc) xs
        | [] -> acc

    reduceCapRec [List.head l] (List.tail l)
    |> List.rev

(Although Gustavo's solution is still much better - I'm also new to FP)

Upvotes: 2

Related Questions