Back to Questions
1.0k
views7
comments
Recursive function error
f#

I am working on a recursive function that takes in a a list of strings and gives back a sentence with all words starting with a capitalized letter.

The code looks like this:

//Recursively captialize every string in the list and combine them back into a sentence

let private RecursiveCapitalize (words : string list) =
if( words.Length = 0) then
""
elif (words.Length = 1) then
words |> List.hd |> CapitalizeWord
else
( words |> List.hd |> CapitalizeWord ) + " " + ( words |> List.tl |> RecursiveCapitalize )

However, I get an error when I call RecursiveCapitalize on the else, it says that RecursiveCapitalize is not defined. But wouldn't it have to be defined since I am inside of RecursiveCapitalize?

.

You might want to take a look at how you can pattern match over list, reducing your code to:

1
2
3
4
5

let rec private RecursiveCapitalize words = 
    match words with
    | [] -> ""
    | [word] -> word |> CapitalizeWord
    | word::tail -> word |> CapitalizeWord + " " + (RecursiveCapitalize tail)

Now, it it is a big list, you might also want to make it tail recursive:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

let rec private RecursiveCapitalizeHelper prevwords words = 


    match words with


    | [] -> prevwords


    | [word] -> prevwords + " " + (word |> CapitalizeWord)


    | word::tail -> RecursiveCapitalize (CapitalizeWord word + " ") tail

let private RecursiveCapitalize =
    RecursiveCapitalizeHelper ""
By on 12/22/2008 10:30 AM ()

What benefit does using pattern match give me? I know my code looks like I'm coming at it like C# (which is where I'm coming from). Is there any significant boost to using Match over a if else chain?

By on 1/6/2009 9:45 PM ()

In this example the match version can make a big difference. Every call to List.length traverses the entire list so the if version doesn't scale.

Secondly, the if version tests the validity of an operation (

1

List.length words = 1

) and performs the operation (

1

List.hd words

) as separate pieces of code, which makes the logic harder to maintain and keep correct. Whereas the match version does this all at once (

1

match words with word :: _ -> ...

).

Thirdly, pattern matching is the fundamental way to analyse data. 

1

List.length

, List.hd, List.tl are all written using pattern matching so you should use it too!

By on 1/7/2009 9:19 PM ()

That makes sense, thanks for the info guys!

By on 1/11/2009 12:59 PM ()

Looks like I'm a little late to the party, but I wanted to comment on the code above (quoted below)

1
2
3
4
5
6
7

let rec private RecursiveCapitalizeHelper prevwords words =
    match words with
    | [] -> prevwords
    | [word] -> prevwords + " " + (word |> CapitalizeWord)
    | word::tail -> RecursiveCapitalize (CapitalizeWord word + " ") tail
let private RecursiveCapitalize =
    RecursiveCapitalizeHelper ""

This is an extremely common pattern in F# due to the frequency of recursion. You want to call a function, which then delegates the work to a recursive function with an additional argument which the function supplies with an initial default value. The best way I've seen of doing this is to declare the helper function locally, private to the function that the user is going to call. The function the user calls is not marked with rec, the helper function is marked with rec. You can give them exactly the same name, it's smart enough to realize that you can't possibly be referring to the outside function again since it isn't labelled with rec, so it correctly calls the helper function.

Above code re-written:

1
2
3
4
5
6
7

let RecursiveCapitalize words =
    let rec RecursiveCapitalize prevwords words =
        match words with
        | [] -> prevwords
        | [word] -> prevwords + " " + (word |> CapitalizeWord)
        | word::tail -> RecursiveCapitalize (CapitalizeWord word + " ") tail
    RecursiveCapitalize "" words

This also has the benefit of not polluting the global namespace (I say namespace for lack of a better word), and giving the user less choices in what function to call when really most of the time that's exactly how they're going to use it.

By on 1/16/2009 7:06 PM ()

It depends what you mean by boost, I believe most patterns are compiled to an if then else chain of sorts, so perf won't be significantly different.

However pattern match let's just write the type of literal you're looking for, so generally leads much shorter and aesthetically pleasing code.

Cheers,

Rob

By on 1/7/2009 1:31 AM ()

However, I get an error when I call RecursiveCapitalize on the else, it says that RecursiveCapitalize is not defined. But wouldn't it have to be defined since I am inside of RecursiveCapitalize?

F# requires that one explicitly declare a function as recursive. So, give this a try:

let rec private RecursiveCapitalize (words : string list) =

By on 12/21/2008 11:51 PM ()

    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