Какова основная идея chainRec? - PullRequest
Новая
       30

Какова основная идея chainRec?

0 голосов
/ 27 мая 2018

[EDIT]

Это дополнительный вопрос Как реализовать безопасный для стека оператор chainRec для монады продолжения?

Данный тип chainRec 

chainRec :: ChainRec m => ((a -> c, b -> c, a) -> m c, a) -> m b

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

const chainRec = f => x => join(f(chainRec(f), of, x));

Далее я хочу применить его к рекурсивному действию: 

const map = f => g => x => f(g(x));
const join = f => x => f(x) (x);
const of = x => y => x;

const chainRec = f => x => join(f(chainRec(f), of, x));

const repeat = n => f => x => 
  chainRec((loop, done, args) =>
    args[0] === 0
      ? done(args[1])
      : loop([args[0] - 1, map(f) (args[1])])) ([n, of(x)]);

const inc = x => of(x + 1);

repeat(10) (inc) (0) (); // error

Я полагал, что, поскольку в определении chainRec есть join, в реализации repeat должен быть map, так чтоесть два вложенных функториальных контекста, чтобы разрушиться.Тем не менее, это не работает, и я понятия не имею, как это исправить.

1 Ответ

0 голосов
/ 27 мая 2018

Не зная, что делает ваша repeat функция, я предполагаю, что ваш вызов repeat(10)(inc)(0) должен расшириться до 

map(inc)(
 map(inc)(
  map(inc)(
   map(inc)(
    map(inc)(
     map(inc)(
      map(inc)(
       map(inc)(
        map(inc)(
         map(inc)(
          of(0)
         )
        )
       )
      )
     )
    )
   )
  )
 )
)

Поскольку ваш inc по какой-то причине возвращает функцию _ => Int вместо простого Int, это вызовет x + 1 для функции x, что приведет к строковому определению этой функции (y => x становится "y => x1"), что вызовет исключение при попытке вызова.

После исправления const inc = x => x + 1; ваша функция repeat по-прежнему не работает.Это должна быть простая рекурсия, с 

const id = x => x
// rec :: ((a -> c, b -> c, a) -> c) -> a -> b
// here with c == b, no trampoline
const rec = f => x => f(rec(f), id, x) // a bit like the y combinator

const repeat = n => f => x => 
  rec((loop, done, [m, g]) =>
    m === 0
      ? done(g)
      : loop([m - 1, map(f)(g)])
  )([n, of(x)]);

repeat(10)(inc)(0)() // 10 - works!

Монада не задействована вообще!

Если бы мы хотели использовать chainRec, нам нужно было бы ввести некоторую произвольную монаду (здесь: функция-монада) и обратный вызов f на chainRec должен будет возвращать экземпляр этого типа монады вместо loop / done: 

chainRec :: ChainRec m => ((a -> c, b -> c, a) -> m c, a) -> m b
//                                                ^

Мы могли бы сделать этопросто упаковав возвращаемое значение в of: 

const repeat = n => f => x => 
  chainRec((loop, done, [m, g]) =>
    of(m === 0
//  ^^
      ? done(g)
      : loop([m - 1, map(f)(g)])
     )
  )([n, of(x)]);

и, конечно, теперь получим m b, то есть все, что обернуто в еще одну функцию: 

repeat(10)(inc)(0)()() // 10
//                  ^^

// repeat(1)(inc)(0) expands to `of(map(inc)(of(0)))

Но я сомневаюсьэто то, что вы хотели.

...