Recursive lambdas in F#

Question

Take this example code (ignore it being horribly inefficient for the moment)

let listToString (lst:list<'a>) = ;;' prettify fix

    let rec inner (lst:list<'a>) buffer = ;;' prettify fix
        match List.length lst with 
        | 0 -> buffer
        | _ -> inner (List.tl  lst) (buffer + ((List.hd lst).ToString()))

    inner lst ""

This is a common pattern I keep coming across in F#, I need to have an inner function who recurses itself over some value - and I only need this function once, is there in any way possible to call a lambda from within it self (some magic keyword or something) ? I would like the code to look something like this:

let listToString2 (lst:list<'a>) = ;;' prettify fix

    ( fun 
        (lst:list<'a>) buffer -> match List.length lst with ;;' prettify fix
                                 | 0 -> buffer
                                 | _ -> ##RECURSE## (List.tl lst) (buffer + ((List.hd lst).ToString())) 
    ) lst ""

But as you might expect there is no way to refer to the anonymous function within itself, which is needed where I put ##RECURSE##

Answer 1

Yes, it's possible using so called y-combinators (or fixed-point combinators). Ex:

let rec fix f x = f (fix f) x

let fact f = function
 | 0 -> 1
 | x -> x * f (x-1)


let _ = (fix fact) 5 (* evaluates to "120" *)

I don't know articles for F# but this haskell entry might also be helpful.

But: I wouldn't use them if there is any alternative - They're quite hard to understand.

Your code (omit the type annotations here) is a standard construct and much more expressive.

let listToString lst =

    let rec loop acc = function
        | []    -> acc
        | x::xs -> loop (acc ^ (string x)) xs

    loop "" lst

Answer 2

Note that although you say you use the function only once, technically you refer to it by name twice, which is why it makes sense to give it a name.