1 people like it.

Combinator for tail-recursive functions

The snippet defines a combinator 'tailrec' that can be used to express tail-recursive functions. If you use 'tailrec' and do not mark your function as recursive, then the function will be a tail-recursive one.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 

/// Implements a tail-recursive looping. The argument is a function
/// that returns either Choice1Of2 with the final result or 
/// Choice2Of2 with new set of arguments.
let rec tailrec args f = 
  match f args with
  | Choice1Of2 res -> res
  | Choice2Of2 newArgs -> tailrec newArgs f

/// Tail-recursive function to sum the list written using 'tailrec'
/// (note - this function is *not* marked as recursive itself)
let sumList list =
  tailrec (list, 0) (fun (list, acc) ->
    match list with 
    | [] -> Choice1Of2 acc
    | x::xs -> Choice2Of2 (xs, x + acc))
val tailrec : args:'a -> f:('a -> Choice<'b,'a>) -> 'b

Full name: Script.tailrec


 Implements a tail-recursive looping. The argument is a function
 that returns either Choice1Of2 with the final result or
 Choice2Of2 with new set of arguments.
val args : 'a
val f : ('a -> Choice<'b,'a>)
union case Choice.Choice1Of2: 'T1 -> Choice<'T1,'T2>
val res : 'b
union case Choice.Choice2Of2: 'T2 -> Choice<'T1,'T2>
val newArgs : 'a
val sumList : list:int list -> int

Full name: Script.sumList


 Tail-recursive function to sum the list written using 'tailrec'
 (note - this function is *not* marked as recursive itself)
Multiple items
val list : int list

--------------------
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val acc : int
val x : int
val xs : int list

More information

Link:http://fssnip.net/jm
Posted:11 years ago
Author:Tomas Petricek
Tags: tail recursion , recursion , combinators

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.