Рекурсивные лямбды в F # - PullRequest
Новая
       29

Рекурсивные лямбды в F #

7 голосов
/ 23 мая 2009

Возьмем этот пример кода (на данный момент игнорируем его ужасную неэффективность) 

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 ""

Это обычная схема, с которой я постоянно сталкиваюсь в F #, мне нужно иметь внутреннюю функцию, которая рекурсивно переходит к некоторому значению - и мне нужна эта функция только один раз, есть ли возможность вызвать лямбду из нее сам (какое-то волшебное ключевое слово или что-то)? Я хотел бы, чтобы код выглядел примерно так: 

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 ""

Но, как и следовало ожидать, нет способа ссылаться на анонимную функцию внутри себя, которая необходима там, где я поставил ## RECURSE ##

Ответы [ 2 ]

17 голосов
/ 23 мая 2009

Да, это возможно с использованием так называемых y-комбинаторов (или fixed-point combinators). Пример: 

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" *)

Я не знаю статей для F #, но эта запись в haskell также может быть полезна.

Но: я бы их не использовал, если бы была какая-то альтернатива - их довольно сложно понять.

Ваш код (здесь опущены аннотации типов) является стандартной конструкцией и гораздо более выразителен. 

let listToString lst =

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

    loop "" lst
1 голос
/ 24 мая 2009

Обратите внимание, что хотя вы говорите, что используете функцию только один раз, технически вы обращаетесь к ней по имени дважды, поэтому имеет смысл дать ей имя.

...