Комбинатор неподвижной точки

Когда мне впервые задали вопрос о том может ли существовать функция вида Func<Func<T,T&gt,T&gt без использования конструкций вида default(T) он поверг меня в глубокий когнитивный диссонанс.
Как может существовать функция у которой неоткуда взять значения? Об очевидном варианте

T Fix<T>(Func<T,T> func){
   return func(Fix(func));
}

я не мог даже подумать. Разве возможно делать такие функции? Она будет вызываться бесконечно и не даст результата. В языках типа C# такая конструкция и правда вызовет зацикливание, но вполне может работать в языках вроде питона или хаскеля. Сейчас будет немного кода на Haskell, надеюсь синтаксис будет более-менее понятен всем.
Самый простой пример:

fix f = f( fix f)
const42 x = 42
print(fix const42) -- Угадайте, что выведет эта конструкция?

Если разложить вызов, то мы увидим, чтo имеет место быть следующая цепочка вычислений:

fix const42 -> const42 ( fix const42) -> 42

Последний переход произойдёт из-за того, что нам не нужен аргумент функции, чтобы вычислить её значение.
Возникает вопрос: если же функция будет зависеть от своего аргумента то вычисление не остановится, то как нам быть?
Ну не остановиться, и ладно. Если значение не будет использоваться, то оно и не должно быть вычислено, за что спасибо ленивости Haskell.

: — это функция добавления элемента в голову списка. Например: 1:[2,3] = [1,2,3], n:[] = [n]

Рассмотрим функцию fix (1:). Она возвращает список, который, очевидно, будет бесконечным, но тем не менее его можно будет использовать.

take 3 (fix (1:)) -> take 3 (1:fix (1:)) -> 1:take 2 (fix (1:)) -> 1:(1:take 1 (fix (1:)))
-> 1:(1:(1:take 0 (fix (1:)))) -> 1:(1:(1:[])) -> 1:(1:[1]) -> 1:[1,1] -> [1,1,1]

Вот так просто мы получили результат от функции, которая использует свой параметр. Мы даже создали полезную вещь:
repeat n = fix (n:) — Порождение бесконечного списка из одного повторяющегося элемента.
Бесконечность это не порок, главное чтобы где-нибудь, всё равно внутри или снаружи, цепочка вычислений оборвалась. Какие конструкции могут прервать цепочку?
До этого момента мы предполагали, что тип функции для fix является значимым типом. Но почему бы нам не начать использовать функцию высшего порядка? Попробуем традиционный пример:

factCore f = \x -> if x == 0 then 1 else x * f (x-1)

Тогда функция fix factCore будет являться обыкновенным факториалом. По сути каждый раз вместо функции f будет подставляться функция factCore, из-за чего всё станет крайне похоже на обыкновенную рекурсию.

Давайте попробуем что-нибудь посложнее. Например создать все последовательности длинны k состоящие из чисел от 1 до n, притом чтобы не было двух рядом стоящих одинаковых чисел. Задача высосана из пальца, но тем не менее.

allDiffCore n f = \k cond -> if k == 1 then map (\x->[x]) $ filter cond [1..n] else concat $ map (\x -> map (x:) (f (k-1) (/=x)) ) (filter cond [1..n])
sequences n k = fix (allDiffCore n) k (\x->True)

Небольшие пояснения:

filter — функция, принимающая два параметра: условия и список. Возвращает список объектов, которые удовлетворяют условию.
/= — обыкновенное «не равно». Такая вот весьма математическая запись.
concat — функция, которая объединяет список списков в один список.

На каждом шаге мы берём несколько подходящих элементов и задаём функцию которая определит, подходит ли нам следующий элемент. При помощи такого шаблона можно генерировать много разнообразных последовательностей. Например, чтобы получить все возрастающие последовательности достаточно лишь поменять часть отвечающую за функцию фильтрации, то есть (/=x) заменить на (>x).

А теперь задача на подумать: как написать функцию, которая разрешит задачу о ферзях на шахматной доске размера n*n?
Как вы уже заметили, использование функции fix (кстати она является частным случаем комбинатора неподвижной точки), позволяет избежать прямой рекурсии в функциях, что может быть полезно, например, в лямбда исчислении, поскольку там нельзя использовать обыкновенную рекурсию.

Бонусом предлагаю некий, сильно урезанный комбинатор неподвижной точки, для c#:

public static Func<T1, T2> Fix<T1, T2>(Func<Func<T1, T2>, Func<T1, T2>> f)
{
   // Создание функции необходимо использовать, чтобы дальнейшие вызовы происходили непосредственно
   // во время передачи значения внутрь. Это позволяет избежать зацикливания
   return f(x => Fix(f)(x));
}

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

var fact = Fix<int, int>(self => x =>
   {
      if (x == 0)
         return 1;
      return x * self(x - 1);
   });
var result = fact(5);   // 120