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

    Когда мне впервые задали вопрос о том может ли существовать функция вида Func<Func<T,T>,T> без использования конструкций вида 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

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 10

      +4
      На шарпе функция выглядит аццким матаном, который в первый момент не знаешь, куда приложить :) Все же чистый (извините за каламбур) ФП — не для мейнстрима
        +3
        Забавно, если нужна анонимная рекурсия.
        Но в C# это несложно обойти, просто объявив переменную заранее.
        Так что это становится просто интересным упражнением.

        Мне лично больше нравится arguments.callee в JS, он одновременно и понятнее и проще.
          0
          В c# теоретически может быть полезно для того, чтобы вообще избежать объявления переменной, а, если не ошибаюсь, в 4-й версии можно будет немного сократить запись за счёт улучшенного вывода типов. Хотя выглядеть менее матаном от этого не будет.

          За arguments.callee спасибо, раньше этого не знал.
            0
            Сократить объявление, но добавить кучу плохочитабельного кода. Не готов C# к этому, да и не надо оно.
              0
              var же всё-таки появился, и весьма активно используется. =)
              Так что читабельность скорее зависит от привычки.
          0
          Долго думал… Зачем это нужно, можно пример?
            +3
            Вопрос «Зачем это нужно?» в программировании — в корне неправильный (независимо от предмета обсуждения). Правильный вопрос — «Как это можно использовать?».
              +2
              Психологи также регомендуют заменять «почему?» и «зачем?» на «как?» :)
            +1
            > Когда мне впервые задали вопрос о том может ли существовать функция вида Func без использования конструкций вида default(T) он поверг меня в глубокий когнитивный диссонанс.

            Фигня вопрос:
            T Fix(Func func){
            throw new Exception(":)");
            }
              0
              Как обычно. На элементарных примерах привели цепочку вычислений. А на более интересном — нет.

              Only users with full accounts can post comments. Log in, please.