Back to Questions
1.9k
views3
comments
Tail Recursion
f#functionalbook

I am an absolute beginner on F# and functional programming in general but getting curious. Loads of experience with .NET C# C++ Ada etc and have the book Expert F#.
I suspect that the following is not tail recursive even thougk I initially believed it was - how do I make it so?

// apply function 'fn' to all pair combinations in a list (recursive)
// returning a list of fn results

let rec iter lst fn =
match lst with
| [] -> []
| head :: tail -> List.map (fn head) tail @ iter tail f

John

.

It is not tail-recursive, since the last thing that executes is the append (@).

Below is a tail-recursive version, which uses the usual strategy for lists - add an 'accumulator' parameter, build the accumulated list in reverse, and then reverse the final result. And a third version that combines the append and initial reversal (I did not measure or think too hard to see if this is an important optimization or not).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#light

let rec iter lst fn =
    match lst with
    | [] -> []    
    | head :: tail -> List.map (fn head) tail @ iter tail fn 

let iterTR lst fn =
    let rec iter lst fn acc =
        match lst with
        | [] -> acc    
        | head :: tail -> iter tail fn ((List.map (fn head) tail |> List.rev) @ acc)
    iter lst fn [] |> List.rev

let iterTRfast lst fn =
    let rec revAppend revList l =
        // like "List.rev revList @ l", but faster
        match revList with
        | [] -> l
        | h :: t -> revAppend t (h :: l)
    let rec iter lst fn acc =
        match lst with
        | [] -> acc    
        | head :: tail -> iter tail fn (revAppend (List.map (fn head) tail) acc)
    iter lst fn [] |> List.rev

printfn "%A" (iter [1;2;3;4;5] (+))
printfn "%A" (iterTR [1;2;3;4;5] (+))
printfn "%A" (iterTRfast [1;2;3;4;5] (+))
By on 12/2/2008 4:59 PM ()

These are my attempts

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

let iter f l =
  let rec ht l o =
    match l with
    | [] -> o
    | h::[] -> o
    | h::t -> ht t ((h,t)::o)
    
  let rec zip l o =
    match l with
    |[] -> o
    |(x,l)::t -> zip t (List.fold_right (fun v a -> (f x v)::a) l o)

  zip (ht l []) []

let iter2 f l = 
  let rec _iter2 l o =
    match l with
    | [] -> o
    | h::t -> _iter2 t (List.fold_left (fun a v-> (f h v)::a) o t)
    
  _iter2 l [] |> List.rev
By on 12/3/2008 12:50 AM ()

Thanks for that - I figured that the second case was the 'standard' pattern for this type of recursion. BTW I can remove the List.rev s as the fn returns a tupple which needs to be unziped, sorted, remove duplicates ...

By on 12/2/2008 9:32 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