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

Я пытался перевести эту рекурсивную реализацию Haskell футуморфизма, специализированного на Lists

futuL :: (a -> Maybe (b, ([b], Maybe a))) -> a -> [b]
futuL f x = case f x of
  Nothing -> []
  Just (y, (ys, mz)) -> y : (ys ++ fz)
    where fz = case mz of
      Nothing -> []
      Just z -> futuL f z

в императивный цикл Javascript. Это удивительно сложно (по крайней мере, для меня):

const None = ({type: "Option", tag: "None"});
const Some = x => ({type: "Option", tag: "Some", runOption: x});

const arrFutu = coalg => x => { // futuL f x
  const acc = []; // ~ fz

  while (true) {
    let optX = coalg(x); // f x

    switch (optX.tag) { // case
      case "None": return acc; // Nothing -> []

      case "Some": {
        let [y, [ys, optX_]] = optX.runOption; // Just (y, (ys, mz))

        switch(optX_.tag) {
          case "None": {
            arrPushFlat(acc) ((ys.unshift(y), ys)); // y : (ys ++ [])
            return acc;
          }

          case "Some": { // y : (ys ++ futuL f z)
            arrPushFlat(acc) ((ys.unshift(y), ys)); 
            x = optX_.runOption;
            break;
          }

          default: throw new UnionError("invalid tag");
        }

        break;
      }

      default: throw new UnionError("invalid tag");
    }
  }
};

Мне трудно мысленно разобрать код на Haskell, особенно часть where, содержащую рекурсивный вызов. Я предполагаю, что этот вызов не находится в хвостовой позиции, поэтому мне нужен явный стек (acc) для моего цикла JS.

Верен ли мой перевод?

Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
В настоящее время производительность загрузки веб-сайта имеет решающее значение не только для удобства пользователей, но и для ранжирования в...
Безумие обратных вызовов в javascript [JS]
Безумие обратных вызовов в javascript [JS]
Здравствуйте! Юный падаван 🚀. Присоединяйся ко мне, чтобы разобраться в одной из самых запутанных концепций, когда вы начинаете изучать мир...
Система управления парковками с использованием HTML, CSS и JavaScript
Система управления парковками с использованием HTML, CSS и JavaScript
Веб-сайт по управлению парковками был создан с использованием HTML, CSS и JavaScript. Это простой сайт, ничего вычурного. Основная цель -...
JavaScript Вопросы с множественным выбором и ответы
JavaScript Вопросы с множественным выбором и ответы
Если вы ищете платформу, которая предоставляет вам бесплатный тест JavaScript MCQ (Multiple Choice Questions With Answers) для оценки ваших знаний,...
4
0
172
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Поскольку Haskell ленив, можно начать использовать начало списка, возвращаемого "futu", до того, как будет вычислено остальное. В терминах Javascript это лучше всего моделируется с помощью генераторы.

Например (для простоты я использовал значения null для представления Nones):

const arrFutu = coalg => function*(seed) {
    while (true) {
        const next = coalg(seed);
        if (next) {
            // Maybe (b, ([b], Maybe a)), using null for None & flattening nested tuple   
            const [item, items, nextseed] = next; 
            yield item;
            yield* items;
            // Maybe a, using null for None 
            if (nextseed) { 
                seed = nextseed;
                continue; // Continue iterating if the seed isn't null.
            }
        } 
        return;
    }
}

С примером коалгебры, например:

const coalg1 = seed => {
    if (seed < 5) {
        return ['a', ['a','a'], seed + 1];
    } else if (seed < 10) {
        return ['b', ['b','b'], seed + 1];
    } else if (seed == 10) {
        return ['c', ['c'], null];
    }
    return null;
}

for (const x of arrFutu(coalg1)(0)) {
    console.info(x);
}

for (const x of arrFutu(coalg1)(20)) {
    console.info(x);
}

Было бы неплохо сделать футу рекурсивным вместо итеративного, но похоже Оптимизация хвостового вызова Javascript не работает с генераторами.


Между прочим, даже если код Haskell не является хвостовой рекурсией, рекурсия "охраняемый": рекурсивный вызов происходит внутри одного или нескольких конструкторов данных (здесь — конструкторов списка), и вызов может быть отложен до тех пор, пока конструкторы не будут «отклеены». " клиентом, когда он использует возвращенный список.

Спасибо за добавление примера - отличный ответ. Я предполагаю, что ленивая оценка также важна для понимания двойного футу, гисто.

Iven Marquardt 01.06.2019 18:19

К сожалению, в Javascript нет TCO, несмотря на то, что он является частью спецификации (ни один крупный поставщик браузеров не реализовал его и не будет реализовывать в ближайшее время. И да, я знаю минусы защищенной рекурсии/TCO по модулю, а также реализовал его в виде батут на JS.

Iven Marquardt 01.06.2019 18:20

@bob Ленивая оценка лучше подходит для футу, потому что футу - это развертывание, «анаморфизм», который создает значение из семени. Значение, которое создается, может быть даже бесконечным. Между тем гистос — это «катаморфимы», разрушающие существующее конечное значение. Здесь хорошо работает строгая оценка. Особенность гист по отношению к обычным катаморфизмам заключается в том, что на каждом этапе они имеют доступ к записи всех предыдущих промежуточных результатов.

danidiaz 01.06.2019 18:36

Звучит разумно. Я просто подумал, что для типа Listhisto кажется реализованным в терминах cata, что в данном контексте является просто foldr, то есть ленивым вычислением правой ассоциативной складки. Мне нужно провести небольшое исследование по этому вопросу. Лично для меня ленивые вычисления — один из самых сложных аспектов Haskell.

Iven Marquardt 01.06.2019 18:57

Другие вопросы по теме