Который языки поддерживают *рекурсивный* функциональные литералы / анонимные функции?

typedef typename Tail::inUnion dummy;

Однако я не уверен, что реализация inUnion верна. Если я правильно понимаю, этот класс не должен быть создан, поэтому вкладка «fail» никогда не будет автоматически терпеть неудачу. Возможно, было бы лучше указать, находится ли тип в объединении или нет с простым булевым значением.

template  struct Contains;

template 
struct Contains >
{
    enum { result = Contains::result };
};

template 
struct Contains >
{
    enum { result = true };
};

template 
struct Contains
{
    enum { result = false };
};

PS: Посмотрите на Boost :: Variant

PS2: посмотрите на typelists , особенно в книге Андрея Александреску: Modern C ++ Design

16
задан Josh Lee 29 January 2011 в 17:51
поделиться

14 ответов

Большинство языков поддерживает его посредством использования Y combinator. Вот пример в Python (от поваренная книга ):

# Define Y combinator...come on Gudio, put it in functools!
Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg)))

# Define anonymous recursive factorial function
fac = Y(lambda f: lambda n: (1 if n<2 else n*f(n-1)))
assert fac(7) == 5040
16
ответ дан 30 November 2019 в 16:10
поделиться

Поскольку мне было любопытно, я на самом деле пытался придумать способ сделать это в MATLAB. Это может быть сделано, но это смотрит маленький Rube-Goldberg-esque:

>> fact = @(val,branchFcns) val*branchFcns{(val <= 1)+1}(val-1,branchFcns);
>> returnOne = @(val,branchFcns) 1;
>> branchFcns = {fact returnOne};
>> fact(4,branchFcns)

ans =

    24

>> fact(5,branchFcns)

ans =

   120
0
ответ дан 30 November 2019 в 16:10
поделиться

Дельфи включает анонимные функции с Примером версии 2009.

от http://blogs.codegear.com/davidi/2008/07/23/38915/

type
  // method reference
  TProc = reference to procedure(x: Integer);               

procedure Call(const proc: TProc);
begin
  proc(42);
end;

Использование:

var
  proc: TProc;
begin
  // anonymous method
  proc := procedure(a: Integer)
  begin
    Writeln(a);
  end;               

  Call(proc);
  readln
end.
0
ответ дан 30 November 2019 в 16:10
поделиться

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

(labels ((factorial (x) ;define name and params
    ; body of function addrec
    (if (= x 1)
      (return 1)
      (+ (factorial (- x 1))))) ;should not close out labels
  ;call factorial inside labels function
  (factorial 5)) ;this would return 15 from labels
0
ответ дан 30 November 2019 в 16:10
поделиться

Вы перепутали некоторую терминологию здесь, функциональные литералы не должны быть анонимными.

В JavaScript различие зависит от того, записана ли функция как оператор или выражение. Существует некоторая дискуссия о различии в ответах на этот вопрос .

Позволяет, говорят, что Вы передаете свой пример функции:

foo(function(n){if (n<2) {return 1;} else {return n * arguments.callee(n-1);}});

Это могло также быть записано:

foo(function fac(n){if (n<2) {return 1;} else {return n * fac(n-1);}});

В обоих случаях это - функциональный литерал. Но обратите внимание, что во втором примере имя не добавляется к окружающему объему - который может сбивать с толку. Но это широко не используется, поскольку некоторые реализации JavaScript не поддерживают это или имеют ошибочную реализацию. Я также считал, что это медленнее.

Анонимная рекурсия - что-то другое снова, это - когда функция рекурсивно вызывает, не имея ссылки на себя, Y Combinator был уже упомянут. На большинстве языков это не необходимо, поскольку лучшие методы доступны. Вот ссылка на реализация JavaScript .

2
ответ дан 30 November 2019 в 16:10
поделиться

F# "позволил rec"

2
ответ дан 30 November 2019 в 16:10
поделиться

В Perl 6:

my $f = -> $n { if ($n <= 1) {1} else {$n * &?BLOCK($n - 1)} }
$f(42);  # ==> 1405006117752879898543142606244511569936384000000000
4
ответ дан 30 November 2019 в 16:10
поделиться

Ну, кроме языка Common LISP (labels) и Схема (letrec), которую Вы уже упомянули, JavaScript также позволяет Вам называть анонимную функцию:

var foo = {"bar": function baz() {return baz() + 1;}};

, который может быть более удобным, чем использование callee . (Это отличается от function на верхнем уровне; последний заставил бы имя появляться в глобальной области видимости также, тогда как в бывшем случае, имя появляется только в пределах самой функции.)

4
ответ дан 30 November 2019 в 16:10
поделиться

Можно сделать это в Perl:

my $factorial = do {
  my $fac;
  $fac = sub {
    my $n = shift;
    if ($n < 2) { 1 } else { $n * $fac->($n-1) }
  };
};

print $factorial->(4);

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

5
ответ дан 30 November 2019 в 16:10
поделиться

C#

, Читая Wes Dyer блог, Вы будете видеть, что ответ @Jon Стрельбы по тарелочкам не полностью корректен. Я не гений на языках, но существует различие между рекурсивной анонимной функцией и" , функция выдумки действительно просто вызывает делегата что ссылки выдумки локальной переменной " для заключения в кавычки из блога.

фактический ответ C# выглядел бы примерно так:

delegate Func<A, R> Recursive<A, R>(Recursive<A, R> r);

static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f)
{
    Recursive<A, R> rec = r => a => f(r(r))(a);
    return rec(rec);
}

static void Main(string[] args)
{
    Func<int,int> fib = Y<int,int>(f => n => n > 1 ? f(n - 1) + f(n - 2) : n);
    Func<int, int> fact = Y<int, int>(f => n => n > 1 ? n * f(n - 1) : 1);
    Console.WriteLine(fib(6));                          // displays 8
    Console.WriteLine(fact(6));
    Console.ReadLine();
} 
7
ответ дан 30 November 2019 в 16:10
поделиться

В C# необходимо объявить, что переменная содержит делегата и присваивает пустой указатель ему, чтобы удостовериться, что это определенно присвоено, тогда можно назвать его из лямбда-выражения, которое Вы присваиваете ему:

Func<int, int> fac = null;
fac = n => n < 2 ? 1 : n * fac(n-1);
Console.WriteLine(fac(7));

я думаю , я слышал слухи, что команда C# полагала, что изменение правил об определенном присвоении сделало отдельное объявление/инициализацию ненужным, но я не поклянусь ему.

Один важный вопрос для каждого из этих языков / среды выполнения - поддерживают ли они последние вызовы. В C#, насколько я знаю, компилятор MS не использует tail., код операции IL, но JIT может оптимизировать его так или иначе при определенных обстоятельствах . Очевидно, это может очень легко иметь значение между рабочей программой и переполнением стека. (Было бы хорошо иметь больше контроля над этим и/или гарантиями о том, когда это произойдет. Иначе программа, которая работает над одной машиной, может перестать работать на другом трудным к морской сажени способом.)

Редактирование: как FryHard, на который указывают, это - только псевдорекурсия. Достаточно простой сделать задание, но Y-combinator более чистый подход. Существует еще один протест с кодом, который я отправил выше: если Вы измените значение fac, что-нибудь, что пытается использовать старое значение, то начнет перестать работать, потому что лямбда-выражение получило fac сама переменная. (Который это имеет к тому, для работы правильно вообще, конечно...)

1
ответ дан 30 November 2019 в 16:10
поделиться

You can do this in Matlab using an anonymous function which uses the dbstack() introspection to get the function literal of itself and then evaluating it. (I admit this is cheating because dbstack should probably be considered extralinguistic, but it is available in all Matlabs.)

f = @(x) ~x || feval(str2func(getfield(dbstack, 'name')), x-1)

This is an anonymous function that counts down from x and then returns 1. It's not very useful because Matlab lacks the ?: operator and disallows if-blocks inside anonymous functions, so it's hard to construct the base case/recursive step form.

You can demonstrate that it is recursive by calling f(-1); it will count down to infinity and eventually throw a max recursion error.

>> f(-1)
??? Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N)
to change the limit.  Be aware that exceeding your available stack space can
crash MATLAB and/or your computer.

And you can invoke the anonymous function directly, without binding it to any variable, by passing it directly to feval.

>> feval(@(x) ~x || feval(str2func(getfield(dbstack, 'name')), x-1), -1)
??? Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N)
to change the limit.  Be aware that exceeding your available stack space can
crash MATLAB and/or your computer.

Error in ==> create@(x)~x||feval(str2func(getfield(dbstack,'name')),x-1)

To make something useful out of it, you can create a separate function which implements the recursive step logic, using "if" to protect the recursive case against evaluation.

function out = basecase_or_feval(cond, baseval, fcn, args, accumfcn)
%BASECASE_OR_FEVAL Return base case value, or evaluate next step
if cond
    out = baseval;
else
    out = feval(accumfcn, feval(fcn, args{:}));
end

Given that, here's factorial.

recursive_factorial = @(x) basecase_or_feval(x < 2,...
    1,...
    str2func(getfield(dbstack, 'name')),...
    {x-1},...
    @(z)x*z);

And you can call it without binding.

>> feval( @(x) basecase_or_feval(x < 2, 1, str2func(getfield(dbstack, 'name')), {x-1}, @(z)x*z), 5)
ans =
   120
1
ответ дан 30 November 2019 в 16:10
поделиться

'Похоже, вы неправильно поняли анонимные функции, дело не только в создании среды выполнения, но и в области видимости. Рассмотрим этот макрос схемы:

(define-syntax lambdarec
  (syntax-rules ()
    ((lambdarec (tag . params) . body)
     ((lambda ()
       (define (tag . params) . body)
        tag)))))

Такой, что:

(lambdarec (f n) (if (<= n 0) 1 (* n (f (- n 1)))))

Вычисляет истинную анонимную рекурсивную факториальную функцию, которая, например, может использоваться как:

(let ;no letrec used
    ((factorial (lambdarec (f n) (if (<= n 0) 1 (* n (f (- n 1)))))))
  (factorial 4)) ; ===> 24

Однако истинная причина, делающая ее анонимной, заключается в том, что если я это сделаю:

((lambdarec (f n) (if (<= n 0) 1 (* n (f (- n 1))))) 4)

Функция впоследствии удаляется из памяти и не имеет области видимости, поэтому после этого:

(f 4)

Будет либо сигнализировать об ошибке, либо будет привязана к тому, с чем f был связан ранее.

В Haskell специальный способ добиться того же был бы следующим:

\n -> let fac x = if x<2 then 1 else fac (x-1) * x
    in fac n

Разница опять же в том, что эта функция не имеет области видимости, если я ее не использую, поскольку Haskell является ленивым, эффект такой же, как и пустой строка кода, она действительно буквальна, поскольку имеет тот же эффект, что и код C:

3;

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

0
ответ дан 30 November 2019 в 16:10
поделиться

Анонимные функции существуют в C ++ 0x с лямбда-выражением, и они могут быть рекурсивными, хотя я не уверен анонимно.

auto kek = [](){kek();}
0
ответ дан 30 November 2019 в 16:10
поделиться
Другие вопросы по тегам:

Похожие вопросы: