Функциональный C # и хвостовая рекурсия - PullRequest
Новая
       9

Функциональный C # и хвостовая рекурсия

1 голос
/ 16 июля 2011

У меня есть следующий код: 

public static IEnumerable<T> cons<T>(T y, IEnumerable<T> xs)
{
    yield return y;
    foreach (var x in xs) yield return x;
}

public static bool empty<T>(IEnumerable<T> xs)
{
    return !xs.GetEnumerator().MoveNext();
}

public static T head<T>(IEnumerable<T> xs)
{
    Debug.Assert(!empty(xs), "Prelude.head: empty list");
    var e = xs.GetEnumerator(); e.MoveNext();
    return e.Current;
}

// repeat x is an infinite list, with x the value of every element
public static IEnumerable<T> repeat<T>(T x)
{
    return cons(x, repeat(x));
}

Почему head(repeat(2)) не работает, но если я заменю реализацию repeat на: 

// repeat x is an infinite list, with x the value of every element
public static IEnumerable<T> repeat<T>(T x)
{
    for(;;) yield return x;
}

это работает?

Ответы [ 2 ]

3 голосов
/ 16 июля 2011

Ваша первая реализация не является хвостовой рекурсией. Последним, что нужно выполнить, будет вызов cons(), но для его выполнения необходимо оценить repeat(2). Для этого он должен (еще раз) оценить repeat(2). И так до тех пор, пока стек не переполнится.

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

2 голосов
/ 16 июля 2011

Судя по всему, ваш первый пример никогда не заканчивается, поэтому он просто перебивает стек. Ваш второй пример реализован как конечный автомат, который позволяет избежать переполнения стека.

...