Линеаризация списка функций — SWI Prolog

      Комментарии к записи Линеаризация списка функций — SWI Prolog отключены

В этой теме 5 ответов, 2 участника, последнее обновление  Васильев Владимир Сергеевич 2 года/лет, 2 мес. назад.

  • Автор
    Сообщения
  • #1740

    questioner
    Участник

    Здравствуйте!
    Помогите, пожалуйста, разобраться.
    На SWI-Prolog мне нужно линеаризировать список(структуру) и удалить оттуда головы вложенных списков. Иными словами, на вход подается структура вида:
    f (a, f1(b,c), f2( d, f3(e) ) )
    В процессе должен получиться список вида [f,a,[f1,b,c], [f2,d,[f3[e]]] ] , из которого мне нужно удалить головы f,f1,f2,f3 и выдать на выходе [a,b,c,d,e].
    Подскажите, пожалуйста, как лучше сделать, сначала линеаризировать, потом разбить на голову и хвост, далее с помощью append вычесть из всего списка эти головы или удалять их через delete? Или сначала разбивать на головы и хвосты и потом линеаризировать? Мне не очень понятно, как из структуры сделать список, если на вход мне подаются именно круглые скобки, а не квадратные, как у списка.
    Растолкуйте, пожалуйста.

  • #1741

    В SWI Prolog есть чудный оператор «=..», который надо использовать в твоей задаче (с ним она решается более чем тривиально).
    Оператор этот, преобразует список в функцию {функцию потом можно вызвать предикатом call}. Первым аргументом списка должно идти имя функции. Например список [f, g, h] он превратит в f(g, h).

    ?- X =.. [f, g, h].
    X = f(g, h).

    Но можно сделать и обратное действие, если поменять аргументы местами:

    ?- f(g, h) =.. X.
    X = [f, g, h].

    Но, именно это тебе и требуется, вроде бы.
    После первого применения этого оператора к функции твоего примера, картина будет такой:

    ?- f(a, f1(b,c), f2( d, f3(e))) =.. X.
    X = [f, a, f1(b, c), f2(d, f3(e))].

    Очевидно, тебе нужна штука, которая обходит список, ищет в нем функции (скорее всего поможет стандартный предикат callable), применяет к ним оператор «=..» и обрабатывает рекурсивно результат.

    • #1742

      questioner
      Участник

      Действительно, чудесный оператор «=..», спасибо большое!
      Только разъясните, пожалуйста, про call и callable. Мной было найдено следующее:

      all(Goal) выполняет Goal. call/1 выполняется успешно если Goal предоставляет запрос, являющийся истиной

      Я пытаюсь сделать следующее, поправьте, пожалуйста.

      struc(L,Y):- 
        L =.. Y, dev(Y).
      dev([]).
      dev([H|T]):- 
        write(H), remove([H|T],H,T), 
        write(T), struc(T,Y) .
       
      remove( [H|T],H,[H|R]):-
        remove( T, H, R ),!.

      • #1743

        Не понял я почему должен получиться именно такой список (особенно, почему там [e] написано).
        Вот такой код решает вашу задачу:

        f_to_list([], []):-!.
        f_to_list([H|T], R):-
          H =.. L, length(L, Len), Len > 1, !, f_to_list(L, LR), f_to_list(T, TR), R = [LR|TR];
          f_to_list(T, TR), R = [H|TR].

        callable не помог. Я ошибся. Мы преобразуем функтор в список оператором «=..», а затем проверяем наличие аргументов. Если длина списка больше 1 — то аргументы есть, иначе — их нет. Если аргументы есть — надо их рекурсивно обработать.

        Пример вызова:

        ?- f_to_list([f(a, f1(b,c), f2(d, f3(e)))], [R]), write(R).
        [f,a,[f1,b,c],[f2,d,[f3,e]]]
        R = [f, a, [f1, b, c], [f2, d, [f3, e]]].

        Удалить первые элементы всех вложенных списков может такое правило:

        rem_heads([], []):-!.
        rem_heads([H|T], R):-
            is_list(H), !, H = [_|HT], rem_heads(HT, HTR), rem_heads(T, TR), R = [HTR|TR];
            rem_heads(T, TR), R = [H|TR].

        Для твоего примера я вызывал его следующим образом:

        ?- f_to_list([f(a, f1(b,c), f2(d, f3(e)))], L), rem_heads(L, R), write(L), nl, write(R), nl.
        [[f,a,[f1,b,c],[f2,d,[f3,e]]]]
        [[a,[b,c],[d,[e]]]]

        Линеаризовать результат может предикат flatten (стандартный):

        ?- f_to_list([f(a, f1(b,c), f2(d, f3(e)))], L), rem_heads(L, R), flatten(R, FR).
        L = [[f, a, [f1, b, c], [f2, d, [f3|...]]]],
        R = [[a, [b, c], [d, [e]]]],
        FR = [a, b, c, d, e].

        • #1744

          questioner
          Участник

          Не могли бы Вы пояснить, пожалуйста, как именно работает правило rem_heads? Как именно он идет по вложенным спискам и как вообще по ним ходить?
          И еще один вопрос, как найти количество списков и вложенных в него списков заданной длины (заданного количества элементов в списке/вложенном списке). Помогите, пожалуйста!

          • #1745

            % если исходный список пустой, то результат - пустой список
            rem_heads([], []):-!.
            % из непустого списка отделяется первый элемент (H), остается хвост(T)
            rem_heads([H|T], R):-
            % если H - тоже список (вложенный) - то:
            % от него отбрасывается первый элемент, остается HT
            % рекурсивно обрабатывается HT
            % рекурсивно обрабатывается T
            % результаты соединяются
                is_list(H), !, H = [_|HT], rem_heads(HT, HTR), rem_heads(T, TR), R = [HTR|TR];
            % если же H - не список - то первый элемент выкидывать не требуется
            % поэтому просто рекурсивно обрабатываем T, получаем TR
            % и для получения результата приделаем к этому TR наш H
                rem_heads(T, TR), R = [H|TR].

Для ответа в этой теме необходимо авторизоваться.